Recursive c++ function

Question

I am trying to create a recursive function as follows.

The function takes a counter k and as long that the counter is larger than zero I would like to call it recursively so that in the end I end up with something like this:

result = 2(2(2n+1)+1)+1

where the last n (when k=0) should be zero.

int pass(int k, int n)
{
    if(k==0)
    {
        n = 0;
    }
    else
    {
        k--;
        return pass(k, 2*n+1);
    }
}

Can someone give me a hint as on how to do it?

Answer 1

Currently the behaviour of your code is undefined since you don't explicitly return a value on all control paths.

Your code can simplify down to:

int pass(int k, int n)
{
    return k ? 2 * pass(k - 1, n) + 1 : 1;
}

Here I've used the ternary conditional operator. 2 * pass(k - 1, n) + 1 is returned if k is non-zero, 1 is returned otherwise.

Take care not to overflow your int in this case. Note that the maximum size of an int can be as small as 32767. Consider using a long type instead.

Also, note that recursion is not normally a good way of solving O(n) type problems; you could get errors at runtime due to a function call stack limit being exceeded: consider folding to a loop instead.

Answer 2

Change

n = 0;

To

return n;

To return the result.

The rest of the code is fine