In this tutorial, we are going to learn about the fundamentals of recursion functions.

In C language it is possible for functions to call themselves.

C – Fundamentals of Recursion functions:

A function is called recursive if a statement within the body of the function calls the same function. This is also known as a circular definition or self-reference.

There is a distinct difference between the normal and recursive functions.

• A normal function will be invoked by another function.
• A recursive function is invoked by itself directly or indirectly as long as the given condition is satisfied.

Recursive functions are useful while constructing the data structures like stacks, queues, linked lists and trees.

Every recursive function must satisfy the following two criteria’s or properties.

1. Base criteria: There must be at least one base criteria or condition in the recursion process, such that, when this condition is met the function stops calling itself recursively.
2. Recursive step: The recursive calls should progress in such a way that each time a recursive call is made it comes closer to the base criteria.

A recursive function that satisfies the above two properties is said to be a well defined recursive function.

Recursion function calls can be classified into the below two types:

• When a function calls itself directly, it is called a direct recursion. In such cases, only one function is involved, which calls itself until the given condition is met.
• In indirect recursion two or more functions can be involved, where the recursive call be initiated by one of the intermediary functions.

// Direct recursion

int sum(int n) {
  .......	
  if (condition) {
    variable = sum(n-1);
  }
}

// Indirect recursion

int sum(int n) {
  .......	
  if (condition) {
    variable = total(n-1);
  }
}
int total(int n) {
  .......	
  if (condition) {
    variable = sum(n-1);
  }
}

While using recursion, programmers need to be careful to define an exit condition from the function, otherwise, the calls might result in an infinite loop.

Recursive functions are very useful to solve many mathematical problems like calculating factorial, generating Fibonacci series, etc.

Some of the important points to remember when writing a program involving recursion process.

• In recursion, it is essential for a function to call itself; otherwise, recursion will not take place.
• Only user-defined functions can be involved in the recursion. Library function cannot be involved in recursion because their source code cannot be viewed.
• To stop the recursive function it is necessary to base the recursion on test condition and proper terminating statement.
• During recursion, at each recursive call new memory is allocated to all the local variables of the recursive functions with the same name.
• When a recursive function is executed, all the recursive calls are pushed onto the stack until the terminating condition is not detected. When the terminating condition is detected, the recursive calls stored in the stack are popped and executed. The last call is executed first then second, then third and so on.

The below sample code is to find the factorial of a given number using recursion process.

First let us consider the mathematical solution of the factorial problem.

• The factorial of a number 3 can be calculated as 3! = 3 * 2 * 1
• The factorial of a number 4 can be calculated as 4! = 4 * 3 * 2 * 1
• The factorial of a number 5 can be calculated as 5! = 5 * 4 * 3 * 2 * 1
• In the similar way factorial of a number n can be calculated as n! = n * (n – 1) * (n – 2) *….3 * 2 * 1

The recursive formula for factorial is:

n! = n * (n - 1)!; if n > 0 (Recursive criteria)
n! = 1; if n = 0 (Base criteria)

In the factorial program write the main() and factorial() functions. In main() function read the input and send it to the factorial() function.

The factorial() function contains base and recursive criteria, where the base condition executes only when the value reaches zero (0).

#include <stdio.h>
long int factorial(long int);
void main() {
     long int n;
     printf("Enter an integer : ");
     scanf("%ld", &n);
     printf("Factorial of %ld is %ld\n", n, factorial(n));
}
long int factorial(long int n) {
     if (n <= 1) {
         return 1;
     } else {
         return n * factorial(n - 1);
     }
}

Output:

Enter an integer : 5
Factorial of 5 is 120

Advantages and Disadvantages of recursion:

Some of the advantages of using recursion are :

• Using recursion, code becomes more readable while implementing data structures like stacks, queues, linked lists and trees.
• Using recursion, a program can be written in a concise form (shorter way).

Some of the disadvantages of using recursion are :

• It requires extra storage space. The recursive calls and automatic variables are stored on the function call stack. For every recursive call, separate memory is allocated to automatic variables on the function call stack.
• The recursive functions are not always efficient in execution speed as they have to push and pop the data on the function call stack.

REFERENCES:

• Wiki – Recursion
• C Functions
• Microsoft – Recursive Functions

Happy Learning 🙂