recursive help!!

This is a discussion on recursive help!! within the C++ Programming forums, part of the General Programming Boards category; hi guys, I'm reaching to recursive function. Trying to digest such abstract concept. I'm doing couple examples in order to ...

  1. #1
    Registered User
    Join Date
    May 2008
    Posts
    43

    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!!!!
    Last edited by azsquall; 06-02-2008 at 08:03 PM.

  2. #2
    Registered User
    Join Date
    Oct 2001
    Posts
    2,129
    Code:
    void printNum(int ENDnum, int INITnum)
    {
    	cout << INITnum << setw(2);
    	if (INITnum < ENDnum)
    		printNum(ENDnum, INITnum+1);
    	cout << "Going out: " << INITnum << setw(2);
    }

  3. #3
    Registered User
    Join Date
    May 2008
    Posts
    43
    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!

    ( sorry..i'm newbie)

  4. #4
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    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
    Mac and Windows cross platform programmer. Ruby lover.

    Quote of the Day
    12/20: Mario F.:I never was, am not, and never will be, one to shut up in the face of something I think is fundamentally wrong.

    Amen brother!

  5. #5
    Registered User
    Join Date
    May 2008
    Posts
    43
    thanks!
    so. it's like rewinding the tape?

  6. #6
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,337
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  7. #7
    Registered User
    Join Date
    May 2008
    Posts
    43
    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?

  8. #8
    Registered User
    Join Date
    Apr 2006
    Posts
    2,012
    Quote Originally Posted by azsquall View Post
    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.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  9. #9
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    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
    Mac and Windows cross platform programmer. Ruby lover.

    Quote of the Day
    12/20: Mario F.:I never was, am not, and never will be, one to shut up in the face of something I think is fundamentally wrong.

    Amen brother!

  10. #10
    Registered User
    Join Date
    May 2008
    Posts
    43
    hey thanks!!
    I got it now!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. recursive function
    By technosavvy in forum C Programming
    Replies: 1
    Last Post: 02-29-2008, 04:42 AM
  2. difference between recursive and iterative
    By Micko in forum C Programming
    Replies: 33
    Last Post: 07-06-2004, 09:34 PM
  3. Algorithm help (Changing from Recursive to Non Recursive)
    By Thantos in forum C++ Programming
    Replies: 1
    Last Post: 04-25-2004, 07:27 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. How to change recursive loop to non recursive loop
    By ooosawaddee3 in forum C Programming
    Replies: 1
    Last Post: 06-24-2002, 08:15 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21