Recursion in C

Let us start with this —>

Commonly, a non-recursive solution to a programming problem is more efficient in both runtime and memory space basis than a recursive one.

Then ,

Why recursion?

• Recursive functions are relatively shorter and so they are easier to write and debug.

• If iterative solution is very complex,then recursion would be a good substitute.

• Useful if you are applying the same solution.

What is a recursive function?

1. A function calling itself

This can be shown by

Below is the code snippet

void rec_fn()                     
{
 ...
 rec_fn();
 ...
}

2. A function is in a cycle of function calls.

This can be shown by

Code snippet:

void rec_fn()
{
        fn1();
        return;
 }

        void fn1()
        {
            fn2();
            return ;
        }

            void fn2()
            {
                    rec_fn();
                    return;
            }

We are going to study only the 1st type of recursion.

• A program to calculate factorial of a number using recursion

#include<stdio.h>

int factorial(int);

void main()
{
    int fact,no;
    printf("Enter a number");
    scanf("%d",&no);
    fact=factorial(no);
    printf("\nFactorial = %d",fact);
}

int factorial(int num)
{
    if(num==1)
        return 1;
    else
        return num*factorial(num-1);
}

Now lets trace the above program for no=3.

 How is recursion implemented by compilers ?

Using a call stack.It is a data structure used by the program to store information about the active subroutines.

Call stack comprises of stack frames also called as activation records.

• For each activation of a function,a stack frame is pushed onto the call stack.

• When function is completely executed,its activation record is popped off from the stack.

Now lets see the structure of activation record —->

• Return value

• Return address——————>where to return after a function has executed.

• Actual parameters————–>parameters that are passed to the called procedure.

• Control link(Dynamic Link)—>points to activation record of calling procedure.

• Access Link(Static Link)

• Saved machine status

• Local variables——————->variables local to a function.

• Temporaries

Step by step view of call stack  for finding factorial of 3 in the above program is shown below.