How to accurately understand the recursion function?

Question

I am currently programming some division-conquest algorithms where recursion functions are used everywhere, but I have a very vague idea of ​​how this works and why I post it here and hope you don't mind the main one either.

For example, if we have the following code:

#include<iostream> using namespace std; void Recursion(int n) { cout << n << endl; if(n > 0) { Recursion(n-1); } cout<<n<<endl; } int main() { Recursion(3); return 0; } 

I tested recursion (3) and the printout in the terminal:

 3 2 1 0 0 1 2 3 

I can understand the concept of a recursive function call, but I don’t understand how it works. For example, what will they do after they cannot call the function again? For example, here I can understand that it prints from 3 to 0, but why does it also print from 0 to 3 again? I heard this because the recursion function is stored on the stack for one recursion, and when it reaches the "bottom", it must also be deleted.

But anyway, I don’t know about it. So, can someone help me and clearly tell me what happened here and the exact flow of the function call?

Thank you for your help!

Answer 1

The key to understanding recursion is the call stack concept. The call stack consists of "frames". The stack frame contains local function variables and an invisible return address. The classic physical analogy is a stack of plates. When you call a function call, a label (frame pile) is added to the top of the stack. When you return from a function, the top plate (freeze frame) is deleted. You can only use the plate (frame stack) that is on top.

Recursive functions work just like regular functions. They are a bit complicated because you can have multiple instances of your local variables on the stack at a given time. However, like other functions, a function refers only to the stack stack, which is located at the top of the stack.

To illustrate how this works, go through your program, showing how the call stack grows and contracts.

Let's start with the base case: 0. Recursion(0);

• Type main: the stack is empty: the bottom of the stack → || <-Top of stack
• Recursion(0); Enter the recursion in which the stack grew: the bottom of the stack-> | 0 | <-Top of stack
• cout << n << endl; The value of n is 0, so the output is "0"
• if (n > 0) . 0 is not greater than 0, so Recursion (-1) is not called.
• cout << n << endl; The value of n is 0, so the output is "0"
• Return to main (), the stack is empty again: the bottom of the stack-> || <-Top of stack

The output will be

 0 0 

Simple enough, there was no recursion. Let's take the next step. Recursion(1);

• Type main: Bottom of stack-> || <-Top the stack
• Recursion(1); Type Recursion: Bottom of stack-> | 1 | <-Top of stack
• cout << n << endl; The value of n is 1, so the output is "1"
• if (n > 0) . 1 is greater than 0, so Recursion(0); is called Recursion(0); .
• Enter recursion: bottom of stack → | 1,0 | <-Top of stack
• cout << n << endl; The value n in this stack frame is 0, so the output is "0"
• if (n > 0) . 0 is not greater than 0, so the function does not recurs.
• cout << n << endl; The value of n is 0, so the output is "0"
• Returns to the first call of Recursion. The bottom of the stack → | 1 | <-Top of stack
• cout << n << endl; The value of n is 1, so the output is "1"

Exit

 1 0 0 1 

Go through execution one last time with n == 2

• Type main: Bottom-> || <-Top
• Recursion(2); Enter Recursion: Bottom-> | 2 | <-Top
• cout << n << endl; "2"
• if (n > 0) . 2 is greater than 0, therefore Recursion(1); called out.
• Enter Recursion: Bottom-> | 2.1 | <-Top
• cout << n << endl; "one"
• if (n > 0) . 1 is greater than 0, so Recursion(0); is called Recursion(0); .
• Enter Recursion: Bottom-> | 2,1,0 | <-Top
• cout << n << endl; "0"
• if (n > 0) . 0 is not greater than 0, so the function is not overwritten again.
• cout << n << endl; "0"
• Return. Bottom-> | 2.1 | <Rasteryaev
• cout << n << endl; "one"
• Return. Bottom-> | 2 | <Rasteryaev
• cout << n << endl; "2"
• Return to main (). Bottom-> || <Rasteryaev

Exit

 2 1 0 0 1 2 

Answer 2

You are right, I also think that recursive functions are hard to understand. Here is what I do if I see a recursive function: run all the code step by step in your mind. This tip may seem trivial, but most of the time it works for me. Look at your code: you call the Recursion () function with parameter 3. It prints n and n> 0, so it calls Recursion (2) (note that we did not return from the call to Recursion (3), which we are still in mute, and now we are also in Recursion (2), the same for recursion (1) and 0. Now n> 0 is conditional false. It prints 0. and we return from recursion (0). We print 1 and return from recursion (1) and it goes on recursion (3)

 Recursion(3) Recursion(2) Recursion(1) Recursion(0) return from Recursion(0) return from Recursion(1) return from Recursion(2) return from Recursion(3) 

Answer 3

The function that calls itself does not differ from the function that calls another function: before continuing, it must wait for the called function to return.

By the way, recursion may look elegant, but in general this is not the most efficient way of programming: for example, it is impossible for built-in functions, so the overhead for the context switch is guaranteed. There is always a more efficient way to get the same result from a recursive function. But for some problems, the recursive implementation is more intuitive and does not slow down in any significant way. The example you gave in the comments sorts sorting is a good one.

Some interesting discussions about this:
The way to go from recursion to iteration
Is it possible to convert each recursion into an iteration?

My last piece of advice: do not switch to recursion when the problem does not require this approach, for example, when calculating factorial.

Answer 4

It is sometimes easier to understand recursion by starting in the base case, that is, one that does not recurs. In your example, when n <= 0, the call is resolved without additional calls. Let's start with this.

If you call Recursion (0), the expected result is to print zero twice, one before and one after if. The code inside the if is not executed.

Now Recursion (1) does the first printing of the value one, then calls Recursion (0), which in turn prints 0 twice as before, then execution returns to Recursion (1), which prints 1 again, after executing the Recursion ( 0). That's why you see 1 0 0 1. The same goes for recursion (2), which wraps the result of recursion (1) around two.