Recursion... Help

[RabMac]

Hi,

I am having a number of issues with this program and was wondering if someone could please help.

The first issue is that I am trying to write the output to a file but it is not working. The file is being created but no data is being added.

Here is the code for the program.

#include <iostream>
#include <conio.h>
#include <fstream>

using namespace std;

typedef unsigned short USHORT;
typedef unsigned long ULONG;

ULONG GetPower (USHORT n, ULONG power);

int main ()
{
    USHORT number, power;
    ULONG answer;
    cout << "Enter a number: ";
    cin >> number;
    cout << "To what power: ";
    cin >> power;
    
    ofstream outputFile;
    outputFile.open("CalculatePower.txt");
    answer = GetPower (number, power);
    cout << number << " to the " << power << "th power is " << answer << endl;
    outputFile.close();
    _getch();
    return 0;
}

ULONG GetPower (USHORT n, ULONG power)
{
      cout << "Entering function " << n << " " << power << endl;
      if (power == 1)
         return n;
      else
          cout << (n * GetPower (n, (power - 1))) << endl;
          return (n * GetPower (n, (power - 1)));
}

[tipaye]

You're not actually trying to write to the file at all.

I imagine that where you do cout << number << " to the " << power << "th power is " << answer << endl;
You want to also dooutputFile << number << " to the " << power << "th power is " << answer << endl;

Or in place of it, whatever you like.

[RabMac]

I couldn't get it to work mate but don't worry I was only trying to use that so I could show you guys the output when I run my program.

My real problem with this program is understanding the output it produces. I have included a link showing the output from the program below. I don't understand how the function recursion is working and was wondering if someone could explain it to me please.

[IMG]http://i41.tinypic.com/rl9545.jpg[/IMG]

For example why is this line not producing output each time the function is called?

cout << (n * GetPower (n, (power - 1))) << endl;

How does the iteration know to stop when power = 1?

Any help would be greatly appreciated.

[tipaye]

Interesting, I actually get "CalculatePower.txt" with the proper text in it. If what you want is to see all the output not just the result in your file, then replace all the cout with outputFile, but remember you'll have to give GetPower a way of accessing outputFile.

$ ./a.exe
Enter a number: 2
To what power: 3
Entering function 2 3
Entering function 2 2
Entering function 2 1
4
Entering function 2 1
8
Entering function 2 2
Entering function 2 1
4
Entering function 2 1
2 to the 3th power is 8

$ cat CalculatePower.txt
2 to the 3th power is 8

As per the recursion:
Don't mix up the powers in the function you're calling, with the power in the current function.
Each time the function is recursively called, You are passing the value of (power - 1) to it, not power itself. Nothing that happens in the function you call, is going to change power in the function where you're calling from (in fact I rename the variables below just to highlight this). So as far as the function you have called is concerned, the parameter "power" that it receives, has nothing to do with the "power" in the function that called it.
You can see the values being passed each time in the printout.

ULONG GetPower (USHORT n, ULONG power)
{
      cout << "Entering function " << n << " " << power << endl;
      ULONG x = power - 1;
      if (power == 1)
         return n;
      else
          cout << (n * GetPower (n, x)) << endl;
          return (n * GetPower (n, x));
}

Eventually, you're going to call the function with a value of 1, then it will return. On it's way back out, all the multiplications happen, and are printed out.
The line does produce output each time it's called (except when n==1), you can see the output above.

[RabMac]

#include <iostream>
#include <conio.h>
#include <fstream>

using namespace std;

typedef unsigned short USHORT;
typedef unsigned long ULONG;

ULONG GetPower (USHORT n, ULONG power);

int main ()
{
    USHORT number, power;
    ULONG answer;
    cout << "Enter a number: ";
    cin >> number;
    cout << "To what power: ";
    cin >> power;
    
    answer = GetPower (number, power);
    cout << number << " to the " << power << "th power is " << answer << endl;
    _getch();
    return 0;
}

ULONG GetPower (USHORT n, ULONG power)
{
      cout << "Entering function " << n << " " << power << endl;
      ULONG x = power - 1;
      if (power == 1)
         return n;
      else
          cout << (n * GetPower (n,x))) << endl;
          return (n * GetPower (n, x));
}

This is my understanding of how the program works.

1. User inputs 2 numbers.
2. When the program reaches line 21 the function is called and the arguments passed in are n=2 and power = 3(assuming that is the values entered)
3. The program now jumps to the function and it first outputs the value of n and power.
4. It now tests if power ==1, which it isn't.
5. Program jumps to else statement.
6. It should now output the value of 4 and then return 4.

However, this isn't what is happening. Could you step through the code and explain why that isn't the case please.

As far as I can tell nothing is changing the value of power in the function so it will always go to the else statement

[tipaye]

Here's output from a cygwin run:

$ ./a.exe
Enter a number: 2
To what power: 3
Entering function 2 3
Entering function 2 2
Entering function 2 1
4
Entering function 2 1
8
Entering function 2 2
Entering function 2 1
4
Entering function 2 1
2 to the 3th power is 8

Walkthrough:
Remember that each function call gets it's own stack, the variables may have the same name, but they are not the same.
Local variables have their storage allocated for them on the stack (this is why too deep recursion can lead to stack overflow)
These variables are accessed by moving the stack pointer up and down, so they're really not the same.

The very first time we call GetPower(2, 3), let's say we're at level 1 as soon as we enter the function
line 29: prints out the "Entering function 2, 3" line
x = power - 1 = 2
power isn't 1, so we skip to line 34
line 34: IN order to get the second operand for cout <<, we call GetPower(2, 2) -> using level 1 x i.e power - 1
Let's say we're now at level 2
line 29 and "Entering function 2,2"
level 2 x = power - 1 = 1
line 34 and once again call GetPower(2, 1) -> using level 2 x i.e. power - 1
Now we're at level 3
line 29 and "Entering function 2, 1"
level 3 x = power - 1 = 0 -> this is never used
This time power == 1, so we return 2
Now we're back at the cout << statement in level 2 (line 34)
so we multiply 2 * 2 and cout << 4 (line 34)
then for our return value we call GetPower(2, 1) -> using level 2 x (line 35)
This takes us again to level 3, where we're back to line 29 and "Entering function 2, 1"
This immediately returns us back to level 2, with a return value of 2, since power == 1
We multiply 2 * 2 and return 4 to level 1 (line 35)
in level 1 we're back at the cout << statement and we multiply 2 * 4 so we cout << 8 (line 34)
For the return value we call GetPower(2, 2) -> using level 1 x (line 35)
We're now at level 2 again
line 29 and "Entering function 2,2"
line 34 and once again call GetPower(2, 1) -> using level 2 x
Now we're back at level 3
line 29 and "Entering function 2, 1"
This time power == 1, so we return 2
Back at level 2 line 34 this again does cout << 4
This then calculates the return value by doing n * GetPower(2, 1) -> using level 2 x (line 35)
In level 3, line 29 and "Entering function 2, 1"
Immediately returns us back to level 2, with a return value of 2, since power == 1
We multiply 2 * 2 and return 4 to level 1 (line 35)
in level 1 we return 2 * 4 back to main (line 35)

It might help to look at it as a series of independent functions, instead of the same function being recursively called. Here's a simulation that does exactly the same as your code (for n = 2, and power = 3), except that instead of calling itself (recursion), it calls another function, which calls another function, etc.

#include <iostream>
#include <conio.h>
#include <fstream>

using namespace std;

typedef unsigned short USHORT;
typedef unsigned long ULONG;

static ULONG GetPowerLevel1 (USHORT n, ULONG power);
static ULONG GetPowerLevel2 (USHORT n, ULONG power);
static ULONG GetPowerLevel3 (USHORT n, ULONG power);

int main ()
{
    USHORT number = 2, power = 3;
    ULONG answer;
    cout << "n == " << number << endl;
    cout << "power == " << power << endl;
    
    answer = GetPowerLevel1 (number, power);
    cout << number << " to the " << power << "th power is " << answer << endl;
    _getch();
    return 0;
}

ULONG GetPowerLevel1 (USHORT n, ULONG power)
{
      cout << "Entering function GetPowerLevel1 " << n << " " << power << endl;
      if (power == 1)
         return n;
      else
          cout << (n * GetPowerLevel2 (n, power - 1)) << endl;
          return (n * GetPowerLevel2 (n, power - 1));
}

ULONG GetPowerLevel2 (USHORT n, ULONG power)
{
      cout << "Entering function GetPowerLevel2 " << n << " " << power << endl;
      if (power == 1)
         return n;
      else
          cout << (n * GetPowerLevel3 (n, power - 1)) << endl;
          return (n * GetPowerLevel3 (n, power - 1));
}

ULONG GetPowerLevel3 (USHORT n, ULONG power)
{
      cout << "Entering function GetPowerLevel3 " << n << " " << power << endl;
      return n;
}

[RabMac]

Cheers mate, I think I have got it now. The missing link was that each function has its own stack and I did not realise that each time the function was called again it was doing n * function.

So if it was called 3 times it would be n * n * n.