# Recursive Function in C

In C, a function can call itself. This process is known as recursion. And a function that calls itself is called as the recursive function. At first recursive may appear a little tricky. Let's take a simple example:

``````int main()
{
callme();
...
return 0;
}

void rec()
{
statement 1;
...
rec();
}
``````

In the beginning `main()` function called `rec()`, then inside `rec()` function, it called itself again. As you can guess this process will keep repeating indefinitely. So, in a recursive function, there must be a terminating condition to stop the recursion. This condition is known as the base condition.

``````int main()
{
callme();
}

void callme()
{
if(base_condition)
{
// terminating condition
}
statement 1;
...
callme();
}
``````

Often recursion can be used where loops can be used. Generally, recursive solutions are elegant but less efficient than loop solutions. So why use recursion at all ? because some algorithms can be implemented more clearly and simply using recursion like quicksort.

The recursive function works in two phases:

1. Winding phase.
2. Unwinding phase.

Winding phase: In Winding phase the recursive function keeps calling itself. This phase ends when the base condition is reached.

Unwinding phase: When the base condition is reached Unwinding phase starts and control returns back to the original call.

OK Enough theory, Let's take an example:

Example 1:

``````#include<stdio.h>
void rec();

int main()
{
rec(1);

// signal to operating system program ran fine
return 0;
}

void rec(int n)
{
printf("Winding phase: Level = %d\n", n);

if(n<3)
{
rec(n+1);
}

printf("Unwinding phase: Level = %d\n", n);
}
``````

Expected Output:

``````Winding phase: Level = 1
Winding phase: Level = 2
Winding phase: Level = 3
Unwinding phase: Level = 3
Unwinding phase: Level = 2
Unwinding phase: Level = 1
``````

How it works

Winding phase 1:

First, `main()` calls the `rec()` function with an actual argument of 1. As a result, the formal argument of `rec()` function is initialized with the value of `1`. In line 14, `printf()` statement is executed and prints the value of `n`.

``````"Winding phase: Level = 1"
``````

Then the if condition (n < 3) or (1 < 3) is tested, since it is true, rec() level 1 called rec() level 2 with an actual argument of 2.

Winding phase 2:

Now control again passes to level 2 `rec()` function with a formal argument of `2`. The `printf()` statement in line 12 is again executed and prints.

``````"Winding phase: Level = 2"
``````

If condition `(n < 3)` i.e `(2 < 3)` is tested again, since it is true, level 2 `rect()` called level 3 `rec()` with an actual argument of `3`.

Winding phase 3:

Once again the control again passes to level 3 `rec()` function with a formal argument of `3`. The `printf()` statement in line 12 is again executed and prints.

``````"Winding phase: Level = 3"
``````

If condition `(n < 3)` i.e `(3 < 3)` is checked but this time it is false, as a result, call to rec() is skipped. Now our program has reached the base condition. This completes the winding phase.

Unwinding phase 1:

In this level 3 call, for the first time `printf()` statement in line 21 is executed and prints.

``````"Unwinding phase: Level = 3"
``````

As soon as `rec()` function in winding phase 3 ends, the control passes back to its caller (i.e the level 2 call) and execution resumes from there.

Unwinding phase 2:

Since the last statement executed in the level 2 call was the call to level 3 `rec()` function inside the if statement, Hence, level 2 `rec()` function resumes with the following statement, which prints.

``````"Unwinding phase: Level = 2"
``````

Then the level 2 `rec()` function ends, passing the control to level 1 `rec()` fuction.

Unwinding phase 3:

Just like in level 2 `rec()` call, execution in level 1 rec() resumes with the statement following if statement, which prints.

``````"Unwinding phase: Level = 1"
``````

Then the level 1 rec() ends, and control passes back to `main()` function.

Example 2:

The following program calculates the factorial of a number using recursion.

``````#include<stdio.h>
int factorial(int n);

int main()
{
int n;

printf("Enter a number: ");
scanf("%d", &n);

printf("%d! = %d", n, factorial(n));

// signal to operating system program ran fine
return 0;
}

int factorial(int n)
{
if(n == 0) // base condition
{
return 1;
}

else
{
return n * factorial(n-1);
}
}
``````

Expected Output:

``````Enter a number: 5
5! = 120
``````

How it works

Let's say we want to calculate factorial of `5`.

`main()` calls `factorial(5)`
since `5 != 0` - `factorial(5)` calls `factorial(4)`
since `4 != 0` - `factorial(4)` calls `factorial(3)`
since `3 != 0` - `factorial(3)` calls `factorial(2)`
since `2 != 0` - `factorial(2)` calls `factorial(1)`
since `1 != 0` - `factorial(1)` calls `factorial(0)`

When `factorial()` is called with `n = 0`, if condition becomes true and recursion stops and control returns to `factorial(1)`. From now on every called function will return a value to the previous function in reverse order of function calls.

Example 3:

The program to calculates the power of a number using recursion.

``````#include<stdio.h>
int power(int base, int exp);
int main()
{
int base, exp;

printf("Enter base: ");
scanf("%d", &base);

printf("Enter exponent: ");
scanf("%d", &exp);

printf("%d ^ %d = %d", base, exp, power(base, exp));

// signal to operating system everything works fine
return 0;
}

int power(int base, int exp)
{
if(exp == 0) // base condition
{
return 1;
}

else
{
return base * power(base, exp - 1);
}
}
``````

Expected Output:

``````Enter base: 4
Enter exponent: 3
4 ^ 3 = 64
``````