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.

Why not use a pencil and a sheet of paper and write out the steps of power with the values of x and n for a new values of x and n to get an idea of what is going on — Ed Heal
– Ed Heal, Commented Jan 6, 2016 at 22:02
Ask your lecturer/teacher, they'll be able to explain to you. — AStopher
– AStopher, Commented Jan 6, 2016 at 22:06
The teacher does not seem to directly address the issue at hand and the book falls short of explaining it I feel. I have found much better answers and understanding from this website. — Eric Wood
– Eric Wood, Commented Jan 6, 2016 at 22:14
As another strategy for gaining more understanding: use your debugger to step through the code line by line (stepping into the function calls). If you don't know how to do that: now is a good time to learn how to use your debugger. Hint: if your debugger supports it (e.g. Visual Studio) also have it show the call stack and note how it changes. — CompuChip
– CompuChip, Commented Jan 6, 2016 at 22:18
@jxh - "Explain this code to me" questions are off-topic on Programmers. — user1345223
– user1345223, Commented Jan 6, 2016 at 22:18

Christophe · Accepted Answer · 2016-01-06 22:34:04Z

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.

Pete Becker · Accepted Answer · 2016-01-06 22:14:03Z

1

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.

answered Jan 6, 2016 at 22:14

Pete Becker

77.2k8 gold badges82 silver badges171 bronze badges

Collectives™ on Stack Overflow

Using recursive functions in C++

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related