Help Understanding Recursion

[RabMac]

Hi,

I am trying to work out how this function works but feel I am missing something as I can't understand the output.

If I use number = 5 and power = 3, it returns "5 to the 3th power is 125", which is what I expect the answer to be but I don't understand how it is getting that answer.

I understand that a function can call itself and I think I can understand some of the steps which I will outline below.

When the program gets to line 21, the function is called. The starting values are number = 5 and power = 3. From my understanding number will never change in main or in the function. However, power will never change in main but will change in the function.

When the function starts it prints the value of power and then tests if power == 1 on line 30, as it is 3 it jumps to the else statement and prints power = 3.

It then jumps to line 37, where the function is called again. When the function is called here the program jumps back to line 29 and prints value of power = 2 and tests if power == 1, which it dosn't. Therefore, program jumps to line 36 and prints value of power = 2.Program now jumps to line 37 where the function is called again.

The program now jumps back to line 29 and prints value of power = 1 and tests if power == 1, which it does. A message is printed that we are in if and returns n, which is 5.

So on line 37 we now have 5 * 5 = 25 and this value is assigned to answer. So how come the answer outputed by program is actually 125?

What am I missing?

#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 - power is: " << " " << power << endl;
      if (power == 1)
         {cout << "\nIn if START... " << n << " " << power << endl;
         return n;}
      else
          //cout << "\nIn else START... Power is: " << power << endl;
          //cout << (n * GetPower (n, (power-1))) << endl;
          cout << "In else before return... Power is: " << power << endl;
          return (n * GetPower (n, (power-1)));
}

[Chervil]

You might look at the function as storing up an incomplete part of an expression on each call. It is only able to complete the expression and carry out the multiplication after returning from the function call.

5 *               // first time,  power = 3

    5 *           // second time, power = 2
    
        5         // third time,  power = 1 

[RabMac]

So the calculation it is doing is 5 * 5 * 5?

but the third time is the first time it returns a value?

so first time it is 5 * GetPower(n, (power-1)) - calls the function function

2nd time it is 5 * 5 * GetPower(n, (power-1)) - calls the function again

3rd time it is 5 * 5 * 5 - as power = 1 so it got 5 returned from if statement?

[Chervil]

That's more or less it. But it doesn't do the entire 5 * 5 * 5 in one go. It's more like this
return 5 from function 3rd call
return 5 * 5 from function 2nd call
return 5 * 25 from function 1st call
answer = 125 back in main()

[RabMac]

Thanks very much for taking time to answer my questions and explain it to me. I really don't like it when I don't understand something but I am glad I spent time reading about this and trying to figure things out.

I now feel like I have grasped it and intend on trying a few programs now to see if I have it figured right.

[RabMac]

I have just written a program that finds a numbers factoral using recursion.

Here is my function:

int calculate_factoral (int number)
{
    if (number == 1)
       return 1;
    else
        return (number * calculate_factoral (number - 1));
}

If the user enters number = 5, would the value being returned be:

5 * (number-1) * (number-2) * (number-3) * 1

I have the program working but just wanted to verify that my thought process was right.

[Chervil]

Yes, that seems ok. Though sometimes it is required to find the value of 0! which is defined as being 1.

What result does your function give? On my machine it crashed the program. The interesting part is is the reason why it crashed.

[RabMac]

Yes my compiler also crashed when I entered zero.

Have updated the if statement with an OR operator for 0 and 1 and it is working fine now.

[Chervil]

Well, to be precise, the compiler is the program which translates the source code (the stuff you type into the editor) into an executable program which the computer can understand. I don't think that is what crashed.

The point I was getting at is that each function is call takes up a few bytes of storage in a special area called the stack, to hold the return address, and the parameters, local variables etc. When a recursive function calls itself too many times, all of the available memory from the stack gets used up. That's what causes the crash.

[RabMac]

Cheers for the info Chervil.

I have not programmed since leaving university and even then the programming I did was very specialised and did not use a large part of the language.

I am currently trying to improve my programming skills and was just reading about the stack and the stack pointer but the book did not go too in depth but I am sure they will cover it again as I progress through the book.