I'm on chapter 9 of C Primer Plus where the author introduced the thing called recursion. I'm confused about the output of the sample program he presented. Need some help from your guys.
Below is the code
#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); // 1
if (n < 4)
up_and_down(n 1);
printf("LEVEL %d: n location %p\n", n, &n); // 2
}
Here is the output
- Level 1: n location 0x0012ff48
- Level 2: n location 0x0012ff3c
- Level 3: n location 0x0012ff30
- Level 4: n location 0x0012ff24
- LEVEL 4: n location 0x0012ff24
- LEVEL 3: n location 0x0012ff30
- LEVEL 2: n location 0x0012ff3c
- LEVEL 1: n location 0x0012ff48
No problem up till Level 4 where n = 4. At this point, the if statement fails and then the second printf function is executed. After the second printf print out Level 4: n location 0x0012ff24, shouldn't the control pass back to return 0 in the main function? Why does the second printf continue to printf out the other three n variables and specifically in the backward direction.
The author explains that it's becasue
control passes back to the function that called it (the Level 3 call). The last statement executed in the Level 3 call was the call to Level 4 in the if statement. Therefore, Level 3 resumes with the following statement, which is print statement #2. This causes LEVEL 3 to be printed. Then Level3 ends, passing control to Level 2, which prints LEVEL 2, and so on.
I understand each word he said, but together forming those sentences, I have no idea what he's talking about at all.
Why does the second printf continue to print 3,2 and 1? And particularly in that order. Does the second printf means to print out all the n variables? What's the logic behind the way the second printf behaves.
CodePudding user response：
shouldn't the control pass back to return 0 in the main function?
No, it shouldn't. Let me try to, well, convince you with an analogy.
Suppose you had four functions: up_and_down_1(), up_and_down_2(), up_and_down_3() and up_and_down_4(), each calling the next one inside.
Now if I'm in the body of up_and_down_1(), and I call up_and_down_2(), and that function concludes (never mind what it does) - control returns to the next line in up_and_down_1() after the call to up_and_down_2(). That's how functions call work in C (see also here for the low-level nitty-gritty).
Well, it's the same situation with the recursive calls to up_and_down(). It doesn't matter that the function being called happens to be the same function. The machine remembers that control needs to return to a certain line in up_and_down(), with the local variables set the way they were before the call - and that is not affected by the fact that there's an inner call to the same function. The inner call is its own context, has its own pass of control within the code of up_and_down(), and doesn't affect the outer call.
I can also suggest a short illustration video about how this works on typical machines:
What Are The Call Stack And Stack Frames In Recursive Programming?
CodePudding user response：
Because recursion is not special, and when a function returns (any function; including recursive function calls), execution picks up where it left off before the function was called. This means that when you're inside of the third-level, it makes a recursive call to the fourth-level. When the fourth-level call returns, execution goes back to where it was before the recursive function was called: the third level.
Forget about recursion for a second. Say you have a custom function of yours that contains a call to printf, and that custom function is called from within main. When printf returns, where does execution resume to? main, or inside your custom function where it left off? The latter. Your function needs to finish executing the code after the printf call, and then when it's finished execution returns back to main. It's the same with recursive functions.
CodePudding user response：
Its explained unneccessarily complicated. When you call a function you execute whatever code is in there. When a function calls another function it executes the code and then combes back to where it was. You can, for the sake of this example, imagine it like pasting the contents with the args replaced, so up_and_down(1) becomes:
printf("Level %d: n location %p\n", n, &n); // n = 1
if (n < 4) { // n = 1
printf("Level %d: n location %p\n", n, &n); // n = 2
if (n < 4) // n = 2
... paste again with n = 3
printf("LEVEL %d: n location %p\n", n, &n); // n = 2
}
printf("LEVEL %d: n location %p\n", n, &n); // n = 1
That very basically is:
print("enter 1")
if (...)
print("enter 2")
if (...)
print("enter 3")
if (...)
print("enter 4")
// if evaluates to false here, so we dont go deeper
print("exit 4")
print("exit 3")
print("exit 2")
print("exit 1")
CodePudding user response：
lets start from n=1 , it prints the first printf , then it goes inside the condition and calls the same function again, when that function finishs its job the program will move on to the next line which is the second printf, so really the second printf isnt skipped, its just waiting for the function call to finish, this happens in n=2 and n=3 etc,
CodePudding user response：
Each function call "blocks" until the invoked function returns.
Level 1 will call Level 2 before Level 1 reaches the second printf. However, Level 2 will call Level 3 before it reaches the second printf and finally returns.
This will continue for all levels until we reach level 4. At Level 4, the if statement evaluates to false, so up_and_down(n 1) is never reached and level 5 will thus never be a thing.
Therefore, Level 4 is the first Level to reach its implicit return. Level 4 held up Level 3, so with Level 4 out of the way, Level 3 can continue execution and the next instruction in line is printf("LEVEL %d......<something>", n, &n); where n = 3. After that, Level 3 reaches its return and unblocks Level 2, and so on.
Recursion works like a stack, not a queue.
void up_and_down(int n)
{
printf("Level %d: n location %p\n", n, &n); // 1
if (n < 4)
up_and_down(n 1);
printf("LEVEL %d: n location %p\n", n, &n); // 2
return; // Return and unblock the function level that invoked this level, which is level n - 1
}
If you still don't understand recursion, read this again.