1

I don't understand how recursion works too well.

void f(int n) { if (n == 1)cout<<1<<" "; else { f(n - 1); cout<<n<<" "; f(n - 1); }

If i let n = 4, this will output 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1. Why is that? First, n gets smaller and smaller until it gets to 1, and after that, what happens? I can't really understand what these 2 calls do, and why even the second one is there, since the first one gets called first.

Improve this question
8
  • 1
    It's pretty obvious once you get out your line by line debugger; not so obvious if you attempt to understand the code by inspection. Commented Aug 24, 2020 at 9:00
  • Additionally to a debugger, you can use pen and paper and write down how calls are sequenced and processed. Commented Aug 24, 2020 at 9:06
  • after that what happens? What happens is what happens when any function returns, control returns to the calling function, except that the calling function is the same as the called function. So control returns to the calling function f but now n equals 2. So 2 is printed (as you can see) and the f is called again with n equal 1, and so 1 is printed. Then f returns, twice this time and so n now equals 3 and so 3 is printed etc. etc. Really the trick is that there's nothing special about recursion, it's just regular function calls which work exactly the same as any function call. Commented Aug 24, 2020 at 9:11
  • I can't understand what those two function calls do, or why there are two at all. But then I don't know what the function is supposed to do, so I can only explain what it does, not why it does it. I expect that the function is only meant to explain the mysteries of recursion, and so you shouldn't think too hard about the why. Commented Aug 24, 2020 at 9:14
  • what i don't understand is , when it gets back to 2, why doesn't it take the first line f(n - 1),and goes straight to the second line,cout<<n<<" "; ? Commented Aug 24, 2020 at 12:29

3 Answers 3

Reset to default
6

Recursive functions work exactly like non-recursive functions.
In particular, when one returns it returns to its immediate caller.
That is, the call that had n == 1 will return to a call that had n == 2, which will return to a call that had n == 3, and so on, and the calling function keeps going in the regular way.

Your example works like these non-recursive functions, whose flow you can probably figure out:

void f_1() { cout << 1 << " "; } void f_2() { f_1(); cout << 2 << " "; f_1(); } void f_3() { f_2(); cout << 3 << " "; f_2(); } void f_4() { f_3(); cout << 4 << " "; f_3(); }
Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Ok but when it enters f_2(),doesn't it take the first line(f_1() ) over and over again infintely times?Does it just jump over it?
f_2 calls f_1. When f_1 returns, f_2 prints "2", then it calls f_1 again, and then it returns. Every time f_1 is called, it prints "1" and then returns. f_2 does not start over from the beginning when f_1 returns, and it does not jump over anything - it knows where it left off and continues with the next thing after the function call. It seems that you don't quite understand how non-recursive functions work yet, and if you don't do that, recursion is a complete mystery.
oh god,now i understand.i am so dumb.lol i love you.thank you so much.i know functions very well,i am just so TIRED of recursion that i can't think too good..thank you once again
0

The algorithm is, when reaches the end of recursion:

  • Print n
  • Return and print the n + 1 who called n
  • Print the first n again

Here, the n when the recursion ends is 1. That's why every other number in your sequence is 1 (corresponds to the 1st and 3rd points)

If you remove the 1's, your sequence is:

2 3 2 4 2 3 2

Now, the n when the recursion "ends" is 2 (obviosuly it ended on 1 but now we're going one level above), so we repeat the algorithm.

If you remove the 2s...

3 4 3

Again, 3 is the n... and your highest level is the remaining 4.

You see a symmetric sequence due to your symmetric algorithm:

 f(n - 1); cout<<n<<" "; f(n - 1);
Improve this answer

1 Comment

i get it now because of you guys.Thank you so much!1
0

Here below a recursive explanation of what is happening.

When n gets down to n=1 the if part kicks in, prints 1, then returns.

On return, we are brought back to the previous iteration of n, n = 2, that now moves out of the first line of the else statement down to the second, which prints 2, then on the third which is another recursive call that restarts the function with n = 2.

So we go through the first statement of else again, we get n = n - 1 = 1.

When n gets down to n = 1 the if part kicks in, prints 1, then returns.

On return, we are brought back to the previous iteration of n, n = 2, that now moves out of the third line of the else statement and returns.

On return, we are brought back to the previous iteration of n, n = 3, that now moves out of the first line of the else statement down to the second, which prints 3, then on the third which is another recursive call that restarts the function with n = n - 1 = 2.

So we go through the first statement of else again, we get n = n - 1 = 1.

When n gets down to n = 1 the if part kicks in, prints 1, then returns.

On return, we are brought back to the previous iteration of n, n = 2, that now moves out of the first line of the else statement down to the second, which prints 2, then on the third which is another recursive call that restarts the function with n = n - 1 = 1.

When n gets down to n = 1 the if part kicks in, prints 1, then returns.

On return, we are brought back to the previous iteration of n, n = 4, that now moves out of the first line of the else statement down to the second, which prints 4, then on the third which is another recursive call that restarts the function with n = n - 1 = 3.

So we go through the first statement of else again, we get n = n - 1 = 2.

So we go through the first statement of else again, we get n = n - 1 = 1.

When n gets down to n = 1 the if part kicks in, prints 1, then returns.

On return, we are brought back to the previous iteration of n, n = 2, that now moves out of the first line of the else statement down to the second, which prints 2, then on the third which is another recursive call that restarts the function with n = n - 1 = 1.

When n gets down to n = 1 the if part kicks in, prints 1, then returns.

On return, we are brought back to the previous iteration of n, n = 3, that now moves out of the first line of the else statement down to the second, which prints 3, then on the third which is another recursive call that restarts the function with n = n - 1 = 2.

So we go through the first statement of else again, we get n = n - 1 = 2.

So we go through the first statement of else again, we get n = n - 1 = 1.

When n gets down to n = 1 the if part kicks in, prints 1, then returns.

On return, we are brought back to the previous iteration of n, n = 2, that now moves out of the first line of the else statement down to the second, which prints 2, then on the third which is another recursive call that restarts the function with n = n - 1 = 1.

When n gets down to n = 1 the if part kicks in, prints 1, then returns.

Improve this answer

3 Comments

Thank you so much , now i understand its logic.What i didn't get,is how does the program automatically skip the lines that were already finished , like when n got to 2 , it skipped the first line of the else statement,and went straight to the cout<<n<<" ";
Oh ,i now finished it all,i still don't get why it jumps over some statements:(
Basically the only way to exit the recursive calling of f(x) is when n = 1. Only then the if statement commands to return, which means 'give back control to the function caller', which was f(n = 2) ! You can understand the f(x) recursions in your code as while (n != 1) {n--;} loops. Once n = 1, print 1 and step to the next line (which is either print n=2,3,4 or in case n was = 4, end program).