# recursive help!!

• 06-02-2008
azsquall
recursive help!!
hi guys,
I'm reaching to recursive function. Trying to digest such abstract concept.
I'm doing couple examples in order to see how recursive func. work and how to come up with the recursion

One example is this: use recursion to print out
123456789
then modify the function to print out
123456789987654321

Code:

```#include <iostream> #include <iomanip> using namespace std; void printNum(int ENDnum, int INITnum); int main() {         int end;         cout << "where to end: ";         cin >> end;         cout << endl;         printNum(end, 1);         return 0; } void printNum(int ENDnum, int INITnum) {         cout << INITnum << setw(2);         if (INITnum < ENDnum)                 printNum(ENDnum, INITnum+1);         cout << INITnum << setw(2); }```
I got the first part okay, but the 2nd part is quite confusing as I got hints from a friend.
Please correct me if my understanding is wrong
• when printNum is called for the first time --> print out "1" --> call itself again printNum(9, 1+1) --> print out "2" --> so on so forth

• as the func. reaches 8 --> print out "8" --> call itself printNum(9, 8+1) --> print out 9 --> "if" statement failed, for 9 < 9 is FALSE --> print out INITnum --> print out "9"
SHOULD THE FUNCTION STOP RECURSING RIGHT THERE?
thus the out should ONLY be 1234567899 ?

yet it's 123456789987654321
any insight will be great!!!!
• 06-02-2008
robwhit
Code:

```void printNum(int ENDnum, int INITnum) {         cout << INITnum << setw(2);         if (INITnum < ENDnum)                 printNum(ENDnum, INITnum+1);         cout << "Going out: " << INITnum << setw(2); }```
• 06-02-2008
azsquall
thanks!
that segment certainly indicate clearly that 987654321 is generated after the recursion.

My question is that: when the "if" failed, the recursion should have stopped? then the output will be "1234567899" ? Unless, I misconcept somewhere?
I just don't understand why as the recursion has stopped (printNum didn't call itself after the "if" statement), yet, the series of 987654321 appears!

(:D sorry..i'm newbie)
• 06-02-2008
Dino
The recursion does stop, but the stack is loaded with calls to the function that are 9 deep, and it has to "unwind" all 9 times.

If you would have had a "exit()" call when the "if" failed, then the program would have exited immediately and not unwound.

Todd
• 06-02-2008
azsquall
thanks!
so. it's like rewinding the tape?
• 06-02-2008
Salem
More like counting the branches of a tree by climing it.
Once you get to the top (and you have your answer), you then climb all the way back down again.
• 06-02-2008
azsquall
thanks!
I'm a bit concerned about what actually happen inside the comipler
As Todd said, C++ will load (recursed) the function 9 time and save each result in 9 stacks (memory spaces)?
when the execution stops, the function calls still exit memory spaces, thus C++ compiler will flush those memory stacks and display the reversed results?
• 06-03-2008
King Mir
Quote:

Originally Posted by azsquall
thanks!
I'm a bit concerned about what actually happen inside the comipler
As Todd said, C++ will load (recursed) the function 9 time and save each result in 9 stacks (memory spaces)?
when the execution stops, the function calls still exit memory spaces, thus C++ compiler will flush those memory stacks and display the reversed results?

No, thats not what's happening.

Recursive function are just like regular functions; there's no automatic reversal.

One way to think of it is like a pyramid of disks, each disk representing a call to the recursive function. First the bottom disk is called, with 1 as INITnum. It prints that out. Then it calls itself again with INITnum = 2. This is represented by another disk. Eventually you get to the condition that ENDnum = INITnum. This prints the number twice. Then it returns to the disk under it -- this is akin to taking that top INITnum=9 disk off. The disk under is had INITnum = 8. It prints that. Then you take the 8 disk off. In this way, you "pop" disks off the "stack" of disks, one by one untill you get to the bottom disk.
• 06-03-2008
Dino
Winding and unwinding, climbing a tree and climbing back own, adding disks and removing disks, we're all saying the same thing.

Yes azsquall, you understand the concept now. Just the as the name implies, the "stack" gets deeper (grows) one level at a time, and shrinks one level at a time.

Todd
• 06-06-2008
azsquall
hey thanks!!
I got it now!