Thread: 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!!!!

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

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.

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.

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