Programming Forums > Application Development > C++

357mag · Jul 26th, 2007, 4:03 AM

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:

(Toggle Plain Text)

int x = 4;

cout << factorial(x);

Then my function definition goes like this:

(Toggle Plain Text)

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:

(Toggle Plain Text)

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?

(Toggle Plain Text)

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

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

Infinite Recursion · Jul 26th, 2007, 10:18 AM

Follow your books suggestion, so you can see the logic in the recursion.

(Toggle Plain Text)

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, 1:03 PM

Following with a debugger can also be useful.

357mag · Jul 26th, 2007, 7: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, 8:33 PM

Quote:

Originally Posted by 357mag

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:

(Toggle Plain Text)

#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:

(Toggle Plain Text)

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.

(Toggle Plain Text)

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):

(Toggle Plain Text)

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, 8:38 PM

Quote:

Originally Posted by 357mag

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)

(Toggle Plain Text)

{
    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

(Toggle Plain Text)

DaWei · Jul 26th, 2007, 8: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, 9:21 PM

Quote:

Originally Posted by DaWei

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, 9:22 PM

Some folks... ya just can't reach.

357mag · Jul 27th, 2007, 4: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:

(Toggle Plain Text)

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.

Jul 26th, 2007, 4:03 AM	#1
357mag Hobbyist Programmer Join Date: Mar 2005 Posts: 148 Rep Power: 4	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: (Toggle Plain Text) int x = 4; cout << factorial(x); int x = 4; cout << factorial(x); Then my function definition goes like this: (Toggle Plain Text) int factorial(int number) { if (number <= 1) return 1; else return number * factorial(number - 1); } 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: (Toggle Plain Text) return 4 * factorial(3) return 3 * factorial(2) return 3 * factorial(1) 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? (Toggle Plain Text) else cout << n * factorial(n - 1) else cout << n * factorial(n - 1) Let me know what the best way to understand this is.

Jul 26th, 2007, 10:18 AM	#2
Infinite Recursion Programming Guru Join Date: Jul 2004 Location: United States Posts: 3,467 Rep Power: 8	Follow your books suggestion, so you can see the logic in the recursion. (Toggle Plain Text) int factorial(int number) { if (number <= 1) return 1; else { std::cout << number << " * " << "factorial(" << number << " - 1)" << std::endl; return number * factorial(number - 1); } } 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? __________________ http://jasonpowers.net "There are a thousand hacking at the branches of evil to one who is striking at the root."

Jul 26th, 2007, 1:03 PM	#3
DaWei Resident Grouch Join Date: Jun 2005 Posts: 6,453 Rep Power: 10	Following with a debugger can also be useful. __________________ Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code. Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

Jul 26th, 2007, 9:22 PM	#9
stevengs Professional Programmer Join Date: May 2005 Location: Bad Nauheim, Germany Posts: 436 Rep Power: 4	Some folks... ya just can't reach. __________________ -Steven "Is this a piece of your brain?" - Basil Fawlty

Jul 27th, 2007, 4:52 AM	#10
357mag Hobbyist Programmer Join Date: Mar 2005 Posts: 148 Rep Power: 4	Difficult to see. Very. Since you really can't see the calculations. All I see is the chain of function calls. And someone posted: (Toggle Plain Text) 4 * factorial( 3 ) 4 * 3 * factorial( 2 ) 4 * 3 * 2 * factorial( 1 ) 4 * 3 * 2 * 1 4 * 3 * 2 4 * 6 24 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.

Jul 26th, 2007, 7:28 PM	#4
357mag Hobbyist Programmer Join Date: Mar 2005 Posts: 148 Rep Power: 4	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.

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Recursion Maze Question	afroboy0731	Java	8	Dec 18th, 2006 5:18 AM
Recursion and Scheme	Jessehk	Coder's Corner Lounge	8	Feb 4th, 2006 7:46 AM
Debug recursion method()	pr0gm3r	Java	3	Oct 11th, 2005 12:33 PM
Recursion	Mjordan2nd	Coder's Corner Lounge	22	Jul 7th, 2005 11:26 AM
Infinite Recursion	Cipher	Coder's Corner Lounge	3	Mar 9th, 2005 11:35 PM

Programming Forums > Application Development > C++

Understanding Recursion