Using recursive functions in C++

Question

// Ex5_15.cpp (based on Ex5_01.cpp)
// A recursive version of x to the power n
#include <iostream>
using std::cout;
using std::endl;
double power(double x, int n); // Function prototype
int main(void)
{
    double x(2.0); // Different x from that in function power
    double result(0.0);
    // Calculate x raised to powers -3 to +3 inclusive
    for(int index = -3; index <= 3; index++)
    cout << x << “ to the power “ << index << “ is “ << power(x, index)  <<  endl;
    return 0;
}
// Recursive function to compute integral powers of a double value
// First argument is value, second argument is power index
double power(double x, int n)
{
    if(n < 0)
    {
        x = 1.0/x;
        n = -n;
    }
    if(n > 0)
        return x*power(x, n-1);
    else
        return 1.0;
    }

I am in school taking classes for programming. This is an example for recursive functions given in the book. I don't quite see what they are doing and the techniques involved. I was just wondering if anyone can explain this to me or at least point me in the right direction so I can better understand this technique.

Answer 1

Let's have a look what happens when you call power(2,3) :

double power(double x, int n) { // x = 2, n=3; 
   if (n<0) {...}  // false, so skip the brackets  
   if (n>0)        // true
      return x*power (x; n-1);  // call power() again, with different paraleters
   ...             // the rest is skipped
}

So it returns 2 * power(something). Before being able to compute the return value, power() has to call itself again. It's a recursive call. You can see this as if another copy of the function that would be executed, with its own variables (i.e. without touching the local variables of calling instance).

• So now power() is called with the parameters x=2 and n=2. The flow of execution is similar and it will return 2 * power(x, n-1) but n-1 being now 1. So here a recursion again.

  • Now power() is called with x=2 and n=1. This will return 2 * power(x, n-1), but n-1 being now 0. And a recursion again;

    • Finally, power will be called with x=2 and n=0. Here the flow of execution will skip the two ifs and will end up execcuting the elese branch because n is 0. It will return 1.

      Now we have all the elements, for computing the value by winding up these successive calls

All this can be shown graphically:

power(2,3) 
   |
   +--> 2 * power(2,2)
              |
              +--> 2* power(2,1) 
                        |
                        +--> 2* power(2,0) 
                                  |
                                  1

So in the end it returns 2*2*2*1 which is 2^3, the intended result.

By generalizing further this reasoning, you may use mathematical induction to prove that for any n>=0, power (x, n) will return x^n. I let you finish the exercise by looking yourself at what happens when n is negative.

And here some furhter reading that could help with some graphical explanations under different perspecives.

Answer 2

There are always two parts to a recursive function: the recursion and the bottom. Recursion simply means computing the result in terms of a somewhat smaller version of the same problem. The bottom is the final case, where the recursion stops. In the example code, the bottom occurs when n is 0, and the result for that case is 1.0. The recursion occurs when n is greater than 0; it multiplies x by the smaller case of power(x, n-1). Since each recursion reduces n by 1, eventually you hit the bottom, get the result there of 1.0, and return up the chain of calls doing the multiplications until you hit the top-level call, which gives the result. As Ed Heal suggested in his comment, try it with pencil and paper.