Programming Forums > Application Development > C++

DaWei · Jul 27th, 2007, 6:41 AM

As I said, get your debugger fired up and single-step through the code. Replace this statement,

return number * factorial(number - 1);

with this:

(Toggle Plain Text)

x = number * factorial (number - 1);
return x;

That will give you a variable to watch (x) as you step through function repeatedly, then begin to back out.

lectricpharaoh · Jul 27th, 2007, 7:01 AM

Perhaps this pseudo-flowchart makes it easier to understand:

The key thing to understand is that the calls higher up do not return until the more recently-invoked calls return. Thus, factorial(2) does not return until factorial(1) returns the value 1. Then factorial(2) can calculate 2 * factorial(1), or 2 * 1, or 2. The values return to successively higher-level calls up the call stack.

357mag · Aug 3rd, 2007, 4:28 PM

Well I tried adding the two lines of code:

(Toggle Plain Text)

x = number * factorial (number - 1);
return x;

All that tells me is that the value of number starts at 4, then goes to 3, then goes to 2, then goes to 1 where the programs stops. The second return statement seems to do nothing. My debugger I can't get to go on that line at all. I set I think three breakpoints. The first right next to the if( ) statement, the second on the first return statement, and the third breakpoint on the second return statement. But when I run the program, my debugger just skips over the last return statement.

357mag · Aug 3rd, 2007, 9:46 PM

I could see when I was looking at the output from my debugger that it said factorial returned 1, then later it would say factorial returned 2, then later it would say factorial returned 6, and so on until it finally said factorial returned 24. But there still are some things which I don't understand, like how the variable x goes from having a value of 1 to having a value of 2. It's almost like something is changing the value of the x variable but I don't see how it's being changed. If I ever take another class, I'm going to ask the teacher to explain this whole deal.

DaWei · Aug 3rd, 2007, 10:29 PM

Yeah, the function is changing the value. It's not really that difficult. If you add 1 to 1 you get 2. If you add 56 to 2 you get 58. It isn't mysterious at all. The "mystery" is that the function is calling itself from within. It's no different from writing 47 identical procedure that each call the next, except there is no numerical limit except what the resources of your particular system can provide.

Given the length of this thread, I don't think that the very clear explanations are having an impact. You'll need to have a flash of inspiration, or fahgeddaboud it.

Bench · Aug 4th, 2007, 11:56 AM

Look at this (contrived) program ... do you understand how this works?

(Toggle Plain Text)

#include <iostream>

int factorial_one( int n )
{
    return n;
}

int factorial_two( int n )
{
    return n * factorial_one( n - 1 );
}

int factorial_three( int n )
{
    return n * factorial_two( n - 1 );
}

int factorial_four( int n )
{
    return n * factorial_three( n - 1 );
}

int factorial_five( int n )
{
    return n * factorial_four( n - 1 );
}

int factorial_six( int n )
{
    return n * factorial_five( n - 1 );
}

int main()
{
    std::cout << factorial_six( 6 );
}

Its not recursive, but its doing essentially the same thing as your recursive program.

lectricpharaoh · Aug 4th, 2007, 4:58 PM

Quote:

Originally Posted by DaWei

Given the length of this thread, I don't think that the very clear explanations are having an impact. You'll need to have a flash of inspiration, or fahgeddaboud it.

Given that a week went by since my pseudo-flowchart post, I'd held out hope that it was clear now. Ahh well. I agree with you; there's not really any other way to explain it.

@357mag: Maybe, if you don't get it, you should give it a break and move to something else. Come back to it later, and it might make more sense. If it's critical you learn this now (ie, it's part of a class, and finals are approaching), then you really should talk to your teacher. There's only so much that can be said on forums, so a more realtime communication might be appropriate.

[edit]

Quote:

Originally Posted by kruptof

And also try to read up and understand how the stack works and how it's used in recursion.

Yeah, I was thinking one last desperate attempt could be a diagram of subsequent stack frames showing recursive calls. I have a nagging feeling that the OP is having trouble is because he's unclear on this, particularly the idea that the same local variable in the same function can have multiple different (and differently-scoped) instances simultaneously, when that function is called recursively (directly or indirectly). [/edit]

kruptof · Aug 4th, 2007, 5:11 PM

And also try to read up and understand how the stack works and how it's used in recursion.

Arevos · Aug 7th, 2007, 9:39 AM

Quote:

Originally Posted by 357mag

If I ever take another class, I'm going to ask the teacher to explain this whole deal.

An alternative approach, which I don't think anyone has covered, is to think of it in similar terms to a mathematical equation.

I'm sure you know that:

4! = 4 * 3 * 2 * 1

And likewise, 3! is:

3! = 3 * 2 * 1

So another way of writing 4! is:

4! = 4 * (3 * 2 * 1)
4! = 4 * 3!

Likewise:

5! = 5 * 4!
7! = 7 * 6!
10! = 10 * 9!

Generalising this:

n! = n * (n - 1)!

And there's your recursion. Well, almost: in order for the computer to know where to stop, we need to define a base case:

1! = 1
n! = n * (n - 1)!

In fact, in highly mathematical languages like Haskell, this mathematical notation is almost exactly how you code it. Here's some Haskell code:

(Toggle Plain Text)

factorial 1 = 1
factorial n = n * factorial (n - 1)

In languages like C, you need an if statement, but it's much the same idea:

(Toggle Plain Text)

int factorial(int n) {
    if (n == 1)
        return 1;
    else
        return n * factorial(n - 1);
}

Jul 27th, 2007, 6:41 AM	#11
DaWei Resident Grouch Join Date: Jun 2005 Posts: 6,453 Rep Power: 10	As I said, get your debugger fired up and single-step through the code. Replace this statement, (Toggle Plain Text) return number * factorial(number - 1); return number * factorial(number - 1); with this: (Toggle Plain Text) x = number * factorial (number - 1); return x; x = number * factorial (number - 1); return x; That will give you a variable to watch (x) as you step through function repeatedly, then begin to back out. __________________ 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 27th, 2007, 7:01 AM	#12
lectricpharaoh Caffeinated Neural Net Join Date: Jun 2005 Location: Dry west coast of Canada Posts: 1,034 Rep Power: 5	Perhaps this pseudo-flowchart makes it easier to understand: The key thing to understand is that the calls higher up do not return until the more recently-invoked calls return. Thus, factorial(2) does not return until factorial(1) returns the value 1. Then factorial(2) can calculate 2 * factorial(1), or 2 * 1, or 2. The values return to successively higher-level calls up the call stack. __________________ And once again, Probability proves itself willing to sneak into a back alley and service Drama as would a copper-piece harlot. - Vaarsuvius, Order of the Stick

Aug 3rd, 2007, 4:28 PM	#13
357mag Hobbyist Programmer Join Date: Mar 2005 Posts: 148 Rep Power: 4	Well I tried adding the two lines of code: (Toggle Plain Text) x = number * factorial (number - 1); return x; x = number * factorial (number - 1); return x; All that tells me is that the value of number starts at 4, then goes to 3, then goes to 2, then goes to 1 where the programs stops. The second return statement seems to do nothing. My debugger I can't get to go on that line at all. I set I think three breakpoints. The first right next to the if( ) statement, the second on the first return statement, and the third breakpoint on the second return statement. But when I run the program, my debugger just skips over the last return statement.

Aug 3rd, 2007, 10:29 PM	#15
DaWei Resident Grouch Join Date: Jun 2005 Posts: 6,453 Rep Power: 10	Yeah, the function is changing the value. It's not really that difficult. If you add 1 to 1 you get 2. If you add 56 to 2 you get 58. It isn't mysterious at all. The "mystery" is that the function is calling itself from within. It's no different from writing 47 identical procedure that each call the next, except there is no numerical limit except what the resources of your particular system can provide. Given the length of this thread, I don't think that the very clear explanations are having an impact. You'll need to have a flash of inspiration, or fahgeddaboud it. __________________ 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

Aug 4th, 2007, 11:56 AM	#16
Bench Newbie Join Date: Feb 2006 Posts: 20 Rep Power: 0	Look at this (contrived) program ... do you understand how this works? (Toggle Plain Text) #include <iostream> int factorial_one( int n ) { return n; } int factorial_two( int n ) { return n * factorial_one( n - 1 ); } int factorial_three( int n ) { return n * factorial_two( n - 1 ); } int factorial_four( int n ) { return n * factorial_three( n - 1 ); } int factorial_five( int n ) { return n * factorial_four( n - 1 ); } int factorial_six( int n ) { return n * factorial_five( n - 1 ); } int main() { std::cout << factorial_six( 6 ); } #include <iostream> int factorial_one( int n ) { return n; } int factorial_two( int n ) { return n * factorial_one( n - 1 ); } int factorial_three( int n ) { return n * factorial_two( n - 1 ); } int factorial_four( int n ) { return n * factorial_three( n - 1 ); } int factorial_five( int n ) { return n * factorial_four( n - 1 ); } int factorial_six( int n ) { return n * factorial_five( n - 1 ); } int main() { std::cout << factorial_six( 6 ); } Its not recursive, but its doing essentially the same thing as your recursive program.

Aug 3rd, 2007, 9:46 PM	#14
357mag Hobbyist Programmer Join Date: Mar 2005 Posts: 148 Rep Power: 4	I could see when I was looking at the output from my debugger that it said factorial returned 1, then later it would say factorial returned 2, then later it would say factorial returned 6, and so on until it finally said factorial returned 24. But there still are some things which I don't understand, like how the variable x goes from having a value of 1 to having a value of 2. It's almost like something is changing the value of the x variable but I don't see how it's being changed. If I ever take another class, I'm going to ask the teacher to explain this whole deal.

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