#include<stdio.h>
void func1(int n)
{
if(n==0) return;
printf("%d",n);
func2(n-2);
printf("%d",n);
}
void func2(int n)
{
if(n==0) return;
printf("%d",n);
func1(++n);
printf("%d",n);
}
void main()
{
func1(5);
}
Output : 53423122233445
I don't understand the flow of control that is happening in this code leading to the above output. can someone please explain. Thank you in advance :)
I have found through teaching students how recursion works with local variables is that the easiest way to understand it is if you do exactly what the computer does, - process it step by step , and write down what gets called, and when variable values change
for example:
main
func1(5)
n=5
printf 5
func2(5-2)
n=3
print 3
++n
n=4
func1(4)
n=4
print 4
func2(4-2)
n=2
print 2
++n
n=3
func1(3)
n=3
print 3
func2(3-2)
n=1
print 1
++n
n=2
func1(2)
n=2
print 2
func2(2-2)
n=0
if n==0 => return
print 2
print 2
print 3
print 3
print 4
print 4
print 5
//done
You will also need to understand that within each function call, the changes to 'n' within a function do not change the earlier value from where it was called.
you can see this better if you imagine the computer doing something like this: where every function call creates a new set of variables on the a stack, and when a function returns, its variables are deleted off the stack.
stack: (empty)
main
func1(5) ==> push n='5' on stack, then jump to func1()
stack is now { n=5 }
so n is 5
print 5
func2(5-2) ==> push 'n=3' on stack, then jump to func2()
stack is now { n=3 } , { n=5 }
so n is 3
print 3
++n
stack is now { n=4 } , { n=5 }
func1(4) ==> push 'n=4' on stack then jump to func1()
stack is now { n=4} , { n=4 } , { n=5 }
so n is 4
print 4
func2(4-2) ==> push 'n=2' on stack then jump to func()
stack is now {n=2}, {n=4} , { n=4 } , { n=5 }
++n
stack is now {n=3}, {n=4} , { n=4 } , { n=5 }
...etc...
.....
....
stack is eventually {n=0} {n=2}, {n=2}, {n=2} ,{n=1} {n=3}, {n=3}, {n=4} , { n=4 } , { n=5 }
after func(2-2) is called
then:
if n==0 => return;
the return pops one item {n=0} off the stack, so
stack is then {n=2}, {n=2}, {n=2} ,{n=1} {n=3}, {n=3}, {n=4} , { n=4 } , { n=5 }
print 2
return (deletes {n=2})
stack is then {n=2}, {n=2} ,{n=1} {n=3}, {n=3}, {n=4} , { n=4 } , { n=5 }
print 2
return (deletes {n=2})
stack is then {n=2} ,{n=1} {n=3}, {n=3}, {n=4} , { n=4 } , { n=5 }
print 2
return (deletes {n=2})
stack is then {n=1} {n=3}, {n=3}, {n=4} , { n=4 } , { n=5 }
print 1
return (deletes {n=1})
stack is then {n=3}, {n=3}, {n=4} , { n=4 } , { n=5 }
print 3
and so on until it finishes and the last '5' is printed out.
This becomes easier to understand if we annotate each printf so we can tell what number is from what part of the program. I'm also going to change the starting condition to 3 so we can walk through the whole thing.
#include <stdio.h>
void func2(int);
void func1(int n)
{
if(n==0) return;
printf("func1 before: %d\n",n);
func2(n-2);
printf("func1 after: %d\n",n);
}
void func2(int n)
{
if(n==0) return;
printf("func2 before: %d\n",n);
func1(++n);
printf("func2 after: %d\n",n);
}
int main()
{
func1(3);
}
That produces:
func1 before: 3
func2 before: 1
func1 before: 2
func1 after: 2
func2 after: 2
func1 after: 3
Now we've hit the bottom of the recursion. At this point we've built up a stack of function calls.
Once func2(0) returns, the call to func1(2) picks up where it left off and we work through the stack from the bottom up.
