How Recursion Works | Recursion Example in C Language | BitsOfCS

1. What is recursion? 

Any function(in your program) which calls itself is called a ‘recursive function’ and this process is known as ‘recursion‘. A recursive function solves a problem by calling a copy of itself, by working on a smaller distinct of the actual problem. The recursion step must be terminated at some point.

Example- 

We have two ways to track recursion-

1. Tracing the recursion using stack:

In order to trace the recursion ‘stack data structure’ is used.

Program Counter:

A program counter is a register in the processor that has the address of the instructions that are being executed currently. When any instruction completes its execution, the program counter increases its stored value (address or ID) by 1. This program counter helps to keep track of the address or ID of those instructions in the program, which were not executed due to the function calling. 

Let’s understand every step one by one.

Step-1: In our example we have the main() function, hence the first record of the stack, records the main() function. Inside the main() function we call the user defined function fun() and value 3 passed to the variable n in the actual fun() function.  

Now due to the function calling, the program counter goes to the fun() function and remaining statements of the main() function will be executed after completion of the fun() function.

In the main() function, fun(3) appears at the line number 5, so that, the program counter of the first record of stack has ID as 6, that tells whenever we will complete the execution of fun() then we have to come back at line number 6 for remaining execution of the program.

Step-2:  Now fun() is a recursive function, because fun() calls itself. In fun(), n=3 and n>1 is true then it produces the output as 2 and again calls the fun() function with parameter n-1 i.e. 2. Here, the second record of the stack has program counter ID as 13.

Step-3: In the third record, n=2 and n>1 is true then it produces the output as 1 and again calls the fun() function with parameter n-1 i.e. 1. Here, the third record of the stack has program counter ID as 13.

Step-4: In the fourth record, n=1 and n>1 is false. Hence, if the condition is false. This is the base condition of the recursion.

Step-5: Now, the fourth stack record completed its execution and popped out from the stack. Then, in the third record of stack, the program counter went to the line number 13 and completed the execution of the remaining statements and popped out from the stack. Same for the second record. Then, in the first record of the stack, the program counter go to the line number 6 and complete the execution of the remaining statement in the main() function and popped out.

This is how recursion works using stack data structure.

2. Tracing the recursion using tree:

This is a theoretical method to trace the recursion.

Step-1: In the main() function, we have to call the fun() function and the fun(3) function contains two functions. 

1. printf(“%d”, n-1)           2. fun(n-1)

Here n=3 and n>1 hence condition true

Step-2: Now, again fun(2) function contains two functions. 

1. printf(“%d”, n-1)           2. fun(n-1)

Here n=2 and n>1 hence condition true

Step-3: Now, fun(1) function also contains two functions. 

1. printf(“%d”, n-1)           2. fun(n-1)

Here n=1 and n>1 hence the condition is false . So, we are not growing the tree further. Now, in order to produce the output, we have to scan the entire tree left to right. In the diagram, whenever a dot (•) comes that means function enters into stack record and whenever printf() function comes that will produce the output. And second dot (•) tells that function popped out from the stack record. Hence, this tree produces the output as 21.

This is how recursion works when we trace it using a tree.

Resources: Wikipedia 

If you find any problem related to this article, please comment below or contact me here.