Programming Forums
Page 1 of 2 1 2 >
Show 40 post(s) from this thread on one page

Programming Forums (http://www.programmingforums.org/forumindex.php)
-   C++ (http://www.programmingforums.org/forum15.html)
-   -   Understanding Recursion (http://www.programmingforums.org/showthread.php?t=13637)

357mag Jul 26th, 2007 5:03 AM
Understanding Recursion
 
I'm trying to understand the classic compute the factorial of a number business using recursion. Let's say I want to compute the factorial of 4 so in my main function I have something like this:

:
int x = 4;

cout << factorial(x);

Then my function definition goes like this:
:
int factorial(int number)
{
  if (number <= 1)
      return 1;

  else
      return number * factorial(number - 1);
}

I guess the way I got it figured so far is this. The value of x which is 4 gets passed to number. Then we have a succession of function calls like this:

:
return 4 * factorial(3)
return 3 * factorial(2)
return 3 * factorial(1)

And I think then that would be all. But it's hard to see the intermediate results with all these successive function calls. One of my books does recommend putting in a statement that would print the level at which each call is and what the intermediate result is. In order for me to do that, would I just do this?

:
else
  cout << n * factorial(n - 1)

Let me know what the best way to understand this is.

Infinite Recursion Jul 26th, 2007 11:18 AM
Follow your books suggestion, so you can see the logic in the recursion.

:
int factorial(int number)
{
  if (number <= 1)

      return 1;

  else
  {
      std::cout << number << " * " << "factorial(" << number << " - 1)" << std::endl;
      return number * factorial(number - 1);
  }
}

The flow will be:

4 * factorial(4 - 1)
3 * factorial(3 - 1)
2 * factorial(2 - 1)
Answer: 24


Mathematically the factorial of 4, would equate to:

4 × 3 × 2 × 1 = 24

Do you see the pattern?

DaWei Jul 26th, 2007 2:03 PM
Following with a debugger can also be useful.

357mag Jul 26th, 2007 8:28 PM
All I see is a succession of function calls, over and over. What I don't see is where the actual calculations are carried out. The return statement does not say return 4 * 3, or return 3 * 2, or return 2 * 1, or whatever. It actually says return 4 * factorial(3). Then the function calls itself again, and it says return 3 * factorial(2). Then the function calls itself again, and it says return 2 * factorial(1). I realize that somehow it ends up as 4 * 3 * 2 * 1, but the code doesn't really look like that to me. How are the actual calculations carried out? All I see is just the function calling itself until we get down to where the value in number is 1, meaning the function terminates.

Jessehk Jul 26th, 2007 9:33 PM
Quote:
Originally Posted by 357mag (Post 131205)
All I see is a succession of function calls, over and over. What I don't see is where the actual calculations are carried out. The return statement does not say return 4 * 3, or return 3 * 2, or return 2 * 1, or whatever. It actually says return 4 * factorial(3). Then the function calls itself again, and it says return 3 * factorial(2). Then the function calls itself again, and it says return 2 * factorial(1). I realize that somehow it ends up as 4 * 3 * 2 * 1, but the code doesn't really look like that to me. How are the actual calculations carried out? All I see is just the function calling itself until we get down to where the value in number is 1, meaning the function terminates.
I think I see where you're misunderstanding it -- I had that same problem.
I'm going to try to explain.

Say you have the following code:
:
#include <iostream>

int square( int n ) {
    std::cout << "Hello! The program is in square()" << std::endl;
    return n * n;
}

int cube( int n ) {
    std::cout << "Hello! The program is in cube()" << std::endl;
    int s = square( n );
    std::cout << "Hello! The program has returned to cube()" << std::endl;
    return s * n;
}

int main() {
    std::cout << cube( 3 ) << std::endl;
}

And if you were to run it:
:
Hello! The program is in cube()
Hello! The program is in square()
Hello! The program has returned to cube()
27

As you can see, in order to figure out the cube of a number, first the square must be found. The cube() function won't be able to return a result until the square() function is complete because the result of square() is needed. When the square function finishes and returns its result, we are returned to the scope of the cube() function which then processes the result and returns its own. Makes sense?

Recursion is exactly the same, except that instead of calling another function, the same function is called again.

For example, consider that n is equal to 2.

:
return n  * factorial( n - 1);

In this example, the factorial function is called with an argument of 1. That call results in a 1 (1! = 1), and is multiplied by 2 to produce 2.

Recursion is just a chain of calls. The chain only ends when the last call completes. At that point, the calculated value trickles upward and is returned as a final result.

For example, here is the evaluation of factorial(4):

:
4 * factorial( 3 )
4 * 3 * factorial( 2 )
4 * 3 * 2 * factorial( 1 )
4 * 3 * 2 * 1
4 * 3 * 2
4 * 6
24

I hope that helped. :)

Bench Jul 26th, 2007 9:38 PM
Quote:
Originally Posted by 357mag (Post 131205)
All I see is a succession of function calls, over and over. What I don't see is where the actual calculations are carried out. The return statement does not say return 4 * 3, or return 3 * 2, or return 2 * 1, or whatever. It actually says return 4 * factorial(3). Then the function calls itself again, and it says return 3 * factorial(2). Then the function calls itself again, and it says return 2 * factorial(1). I realize that somehow it ends up as 4 * 3 * 2 * 1, but the code doesn't really look like that to me. How are the actual calculations carried out? All I see is just the function calling itself until we get down to where the value in number is 1, meaning the function terminates.
No, the function doesn't terminate, it returns a value to itself. What you have is essentially a function call within a function call within a function call within a function call...

If you were to roll it out, it might look something like this (psuedocode)
:
{
    number * function (number-1)
    {
        number-1 * function (number-2)
        {
            number-2 * function (number-3)
            {
                number-3 * function (number-4)
                {
                    1
                }
            }
        }
    }
}
Just remember that each call to "function" is replaced by ALL the successive blocks of code which stem from that call. Each call is an extra layer of indirection.

Since the function calls only provide indirection, and no actual calculation, the above "unrolling" ends up looking like this
:
{
    number *
    {
        number-1 *
        {
            number-2 *
            {
                number-3 *
                {
                    1
                }
            }
        }
    }
}

DaWei Jul 26th, 2007 9:52 PM
Quote:
No, the function doesn't terminate,
Well, yes it does, unless you're not worth a chit at programming it. Ask IR. Furthermore, I have an image posted in the last couple of weeks showing what happens if it doesn't terminate.

Any recursive function needs a condition that backs it out, eventually, to the original call.

Bench Jul 26th, 2007 10:21 PM
Quote:
Originally Posted by DaWei (Post 131213)
Well, yes it does, unless you're not worth a chit at programming it. Ask IR. Furthermore, I have an image posted in the last couple of weeks showing what happens if it doesn't terminate.

Any recursive function needs a condition that backs it out, eventually, to the original call.
In the context of the reply, I believe the OP was under the train of thought that 'return 1' was a direct return to the original call in main, rather than back to itself. Perhaps I should have used different wording.

stevengs Jul 26th, 2007 10:22 PM
Some folks... ya just can't reach.

357mag Jul 27th, 2007 5:52 AM
Difficult to see. Very. Since you really can't see the calculations. All I see is the chain of function calls. And someone posted:

:
4 * factorial( 3 )
4 * 3 * factorial( 2 )
4 * 3 * 2 * factorial( 1 )
4 * 3 * 2 * 1
4 * 3 * 2
4 * 6
24

4 * 3 is not the same as 4 * factorial(3). I see the compiler always calling the function but I don't see the 4 * 3 * 2 * 1.


All times are GMT -5. The time now is 3:05 AM.
Page 1 of 2 1 2 >
Show 40 post(s) from this thread on one page

Powered by vBulletin® Version 3.7.0, Copyright ©2000 - 2008, Jelsoft Enterprises Ltd.
Copyright ©2007 DaniWeb® LLC