recursion

[SCRIPT_KITTEH]

Hi folks,

As usual, reading about C, have hit a wall that I'm struggling to overcome, "recursion." As I understand it, it's like a function calling itself. This is the short program the author of the book I'm reading used to demonstrate it:

/* recur.c -- recursion illustration */
#include <stdio.h>
void up_and_down(int);
int main(void)
{
        up_and_down(1);
        return 0;
}


void up_and_down(int n)
{
        printf("Level %d: n location %p\n", n, &n);

        if(n < 4)
                up_and_down(n+1);
        printf("LEVEL %d: n location %p\n", n, &n);
}

The output:

Level 1: n location 0x7fff63d2761c
Level 2: n location 0x7fff63d275fc
Level 3: n location 0x7fff63d275dc
Level 4: n location 0x7fff63d275bc
LEVEL 4: n location 0x7fff63d275bc
LEVEL 3: n location 0x7fff63d275dc
LEVEL 2: n location 0x7fff63d275fc
LEVEL 1: n location 0x7fff63d2761c

I understand the program up to the point of the LEVEL 4 message being printed. The boolean test is false so the function moves on to that statement. Where I get lost is the program "backing out of" the recursion, so to speak.

This is what the author had to say starting with where I get confused:

When Level 4 is reached, n is 4, so the if test fails. The up_and_down() function is not called again. Instead, the Level 4 call proceeds to print statement #2, which prints LEVEL 4, because n is 4. Then it reaches the return statement. At this point, the level 4 call ends, and control passes back to the function that called it (the Level 3 call).

I at least understand why only the second print statement happens "on the way back out", because the function isn't being technically called again. But what does he mean by "reaching the return statement" though? That function is type void, so the only return I see in this program is "return 0" at the very end of int main(). If that's the case, why isn't the program ending before the all caps messages are printed? Why does the function have to "pass back control to the function that called it" ?

Any clarification would be greatly appreciated.

[anduril462]

It's the implied return statement at the end of the function. After all the instructions are executed, that instance of the function is done, and returns. It doesn't return a value, but it still returns to where it left off (the previous instance of the function).

[MutantJohn]

Void functions do return. You just type it as :

return;

I think the C compiler now is smart in the sense that you don't have to explicitly tell a void function to return, instead it will use matching brackets to establish function scope or where the control of the function is.

So what's happening in this code is that it's printing the first value, calling the function which prints it again, calls function again, prints number, calls function again until the n<4 condition fails and then it continues, printing the number and returning which causes another return. Where does it return? It returns to right where the function that called it called it, if that's not worded too awkwardly. So it returns, prints, returns, prints, returns, prints, returns.

I don't know if that was the appropriate number of increments I wrote but you get the idea.

[SCRIPT_KITTEH]

It's the implied return statement at the end of the function. After all the instructions are executed, that instance of the function is done, and returns. It doesn't return a value, but it still returns to where it left off (the previous instance of the function).

Ohhh, I was not aware of void functions having an implied return. This is good to know! Thanks, anduril! I wish I could express my gratitude for y'all's help all the time in some way better than just saying thanks. Hopefully one day I will be knowledgeable enough to pay it forward.

[SCRIPT_KITTEH]

Void functions do return. You just type it as :

return;

I think the C compiler now is smart in the sense that you don't have to explicitly tell a void function to return, instead it will use matching brackets to establish function scope or where the control of the function is.

So what's happening in this code is that it's printing the first value, calling the function which prints it again, calls function again, prints number, calls function again until the n<4 condition fails and then it continues, printing the number and returning which causes another return. Where does it return? It returns to right where the function that called it called it, if that's not worded too awkwardly. So it returns, prints, returns, prints, returns, prints, returns.

I don't know if that was the appropriate number of increments I wrote but you get the idea.

Yeah, I think I got it. The implied return was never reached until n < 4 test failed, hence why that is the point it started "returning" back out Thank you!