A recursive function performs the tasks by dividing it into the subtasks. There is a termination condition defined in the function which is satisfied by some specific subtask. After this, the recursion stops and the final result is returned from the function.
The case at which the function doesn't recur is called the base case whereas the instances where the function keeps calling itself to perform a subtask, is called the recursive case. All the recursive functions can be written using this format.
Pseudocode for writing any recursive function is given below.
if (test_for_base)
{
return some_value;
}
else if (test_for_another_base)
{
return some_another_value;
}
else
{
// Statements;
recursive call;
}
#include<stdio.h>
int fibonacci(int);
int main ()
{
int n,f;
printf("Enter the value of n?");
scanf("%d",&n);
f = fibonacci(n);
printf("%d",f);
}
int fibonacci (int n)
{
if (n==0)
{
return 0;
}
else if (n == 1)
{
return 1;
}
else
{
return fibonacci(n-1)+fibonacci(n-2);
}
}
Each recursive call creates a new copy of that method in the memory. Once some data is returned by the method, the copy is removed from the memory.
Since all the variables and other stuff declared inside function get stored in the stack, therefore a separate stack is maintained at each recursive call.
Once the value is returned from the corresponding function, the stack gets destroyed. Recursion involves so much complexity in resolving and tracking the values at each recursive call. Therefore we need to maintain the stack and track the values of the variables defined in the stack.
Let us consider the following example to understand the memory allocation of the recursive functions.
int display (int n)
{
if(n == 0)
return 0; // terminating condition
else
{
printf("%d",n);
return display(n-1); // recursive call
}
}