1

I have the following task:

Write a program that asks for a number and a power. Write a recursive function that takes the number to the power. For example, if the number is 2 and the power is 4, the function will return 16.

I wrote a program and there are no errors when I compile it, but when I start the program and enter a value gives an error saying "Stack Overflow". I suppose my recursive function became infinite but I have no idea how to write it in other way.

This is my code:

#include <iostream>
using namespace std;
int powpow(int number);

int main(){
    cout<<"Enter number:";
    int x;
    cin>>x;
    cout<<"The result of ("<<x<<" * "<<x<<") * "<<x*x<<" is: "<<powpow(x);
    system("pause");
    return 0;
}
int powpow(int number){
    int result = number*number;
    return powpow(result);
}
Improve this question
6
  • 2
    Your recursive function has no stop condition. Commented May 28, 2012 at 22:34
  • considering the task I'm given, what should be the stop condition? Commented May 28, 2012 at 22:35
  • You should step through this in the debugger (or add useful print statements), and the problem should become obvious. Commented May 28, 2012 at 22:35
  • 3
    @WindomEarle: What sounds like a reasonable stop condition? If you had to calculate this with pen and paper, when would you stop? Commented May 28, 2012 at 22:35
  • 1
    Your function only takes a number and keeps squaring it. You should be taking both a base and a power. Commented May 28, 2012 at 22:35

3 Answers 3

Reset to default
9

You have no terminating condition for your recursion, so it runs forever.

It sounds like maybe you don't have a good grasp of recursion, so I'd like to start with something a little simpler, the Fibonacci sequence.

Any time we define a function in terms of recursion, we need to first define a base case(s). In the case of Fibonacci, we have 2 base cases:

F(0) = 0
F(1) = 1

That says, in english, "F of 0 is 0, F of 1 is 1". Or even more simply, if we pass 0 to function F, we will get 0 back. If we pass 1, we will get 1 back.

Once we have the base cases defined, then we need to look for a recurrence relation. In the case of Fibonacci, we have the following recurrence:

F(n) = F(n-1) + F(n-2)

So for n >= 2, we can use the above recurrence. Why? Well, lets try it for n = 2.

F(2) = F(n-1) + F(n-2)
     = F(1) + F(0)
     = 1    + 0
     = 1

So now we know that the answer to F(2) is 1. And what's more, we can now compute the answer to F(3). Why? Well, what do we need to compute F(3)? We need F(2) and F(1). We now have both of those answers since F(1) is a base case, and we just solved F(2) above.

So, now let's try to write a piece of pseudo code to solve F.

function F(int n) {
  // handle base cases
  if (n equals 0)
    return 0
  if (n equals 1)
    return 1

  // recurrence
  return F(n-1) + F(n-2);
}

Note that in a recursive function, we always handle the base cases at the beginning of the function. We cannot define this recurrence if we don't have base cases in place, otherwise, we will have no terminating condition for our recurrence. So that's why you always put the base cases at the beginning of the function.

Now, given the above explanation, another good exercise would be to write a recursive function for the factorial function. So, follow these steps:

1. Define the base case (use wikipedia article for hints).
2. Define recurrence in terms of base case
3. Write pseudo code to solve the recurrence, and be sure to put base case(s) at beginning of function, and recurrence at end.

Once you grasp these steps, then moving on to the power recurrence should make much more sense to you.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Thank you very much for the effort. I'll try the factorial function and read some more on wikipedia. :)
@Windom Earle - Glad it helped :)
@WindomEarle - I gave a +1 to 'dcp' for his post. That said, do note that the examples (viz., Fibonacci and factorial) have only pedagogic value for recursion. You'd actually NOT want to use recursion to solve these problems. (This is very similar to you not wanting to use recursion to solve your own problem but do only because your homework requires you to).
@Happy Green Kid Naps - Thanks for the upvote. However, I don't really agree that "You'd actually NOT want to use recursion to solve these problems". These problems are classic examples of recursion, because the recurrence is simple and well defined. If you're worried about inefficiency since there will be many redundant calls, then you can add memoization (en.wikipedia.org/wiki/Memoization). And it's true you could also use bottom up dynamic programming to solve these examples as well. But there's certainly no reason to NOT want to use recursion to solve them.
3

Your function

  • does not what it should do
  • has no termination condition

Try to think about this: How can your function return x^y when it only takes one number as a parameter. Then, think about how you raise number to a power and the implementation should be obvious.

Improve this answer

Comments

2

Recursive routines always need a "trivial" or "base" case. Think about what you wrote, pass in 1 for x, what will the stop the recursion?

powpow(1)
  result = 1*1
  call powpow(1)
    result = 1*1
    call powpow(1)
      result = 1*1
      call powpow(1)

adinfinitum (or until you exeed the stack)

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.