recursive function question

This is a discussion on recursive function question within the C Programming forums, part of the General Programming Boards category; Okay, so I've got this recursive function. Here's the prototype: Code: void someFunction( const int b[], int startIndex, int size ...

  1. #1
    Registered User
    Join Date
    Aug 2009
    Posts
    15

    recursive function question

    Okay, so I've got this recursive function.
    Here's the prototype:
    Code:
    void someFunction( const int b[], int startIndex, int size );
    It takes as arguments an int array, a counter for the subscript (it's intiialized to 0 in main) and size, which is #DEFINE'd at 10 (the length of array b).

    Here's the function:

    Code:
    void someFunction( const int b[], int startIndex, int size ) {
    	
    	if(startIndex < size) {
    		someFunction(b, startIndex+1, size);
    		printf("%d ", b[startIndex]);
    	}
    } /* someFunction */
    Okay. So I get recursive functions, and I know what the function does, it counts up through startIndex to get to the end of the array, then counts back down and outputs the array's values in reverse order. I get the count up, but I'm having trouble understanding why/how the countdown works.
    Thanks,
    Colin

  2. #2
    Super Moderator
    Join Date
    Sep 2001
    Posts
    4,913
    Picture a stack of blocks or something (the word "stack" is actually the technical term here, when one function calls another function which calls another function, etc.... it's called a "call stack"). There's two parts to the function - the first part calls a function on the next element. That's kind of like adding a new block to the stack. That new block, now has IT'S two parts to execute, and the first thing it does is add another tile to the stack.

    Once there are no more blocks (i.e. the count "up" has finished), the block on top of the stack then executes it's second part, which is to print some data and return. When it returns, it's removed from the stack, and the next block down can execute IT'S second part. And so as each block executes the second part, one by one the blocks are removed.

    I hope that visual helps...

  3. #3
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    Inside your IF block, someFunction() is called, therefore delaying the printf() below it. The last time in the "upward direction", the IF fails, because startIndex is finally 10, so the function exits, doing nothing After it exits, it returns back up the call stack to the IF block for startIndex 9, and then continues with the next instruction after the call to someFunction(), which is the printf(). When it exists, it goes back in the call stack where startIndex is 8, does the printf(), and exits, etc., etc., etc.
    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!

  4. #4
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    Ah, you beat me to it Sean.
    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
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,494
    There is no counting down.

    As each recursive function ends, you get the old value (before you added one to it).
    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.

  6. #6
    Registered User
    Join Date
    Aug 2009
    Posts
    15
    Oh! So the repeated calls to the function are still waiting to finish because the if blocks haven't finished executing. It gets as far as counting up 0 through 9, but since all those previous function calls haven't finished, they still have to do their thing, they're just waiting for the looping function calls to get done. The most recent one to execute finishes first, and then they just go down the list. Is that it?
    Thinking of it as a stack helps a lot. I get how those work (FILO). It's amazing the simple things these books could say that would be so helpful that they leave out.

  7. #7
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,494
    You got it!
    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.

  8. #8
    Super Moderator
    Join Date
    Sep 2001
    Posts
    4,913
    It's amazing the simple things these books could say that would be so helpful that they leave out.
    That happens a lot. When I'm reading about something, I'll try read it from 3 different sources - they all seem to explain things differently, and one of them will have a writing style that just helps a certain concept click.

  9. #9
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    cosmic_cow - you made the list.
    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
    Aug 2009
    Posts
    15
    Ha! That's awesome.

  11. #11
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    It's a gift. Cherish it.
    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!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Function name basic question help
    By kenryuakuma in forum C++ Programming
    Replies: 7
    Last Post: 09-24-2008, 07:48 AM
  2. Need help designing a recursive function.
    By broli86 in forum C Programming
    Replies: 3
    Last Post: 07-24-2008, 12:45 PM
  3. dllimport function not allowed
    By steve1_rm in forum C++ Programming
    Replies: 5
    Last Post: 03-11-2008, 03:33 AM
  4. Including lib in a lib
    By bibiteinfo in forum C++ Programming
    Replies: 0
    Last Post: 02-07-2006, 01:28 PM
  5. Game Pointer Trouble?
    By Drahcir in forum C Programming
    Replies: 8
    Last Post: 02-04-2006, 01:53 AM

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