void recursion ()
{
recursion(); // The recursive function calls itself inside the same function
}
int main ()
{
recursion (); // function call
}
In the provided syntax, the main function invokes the recursion function just once. Subsequently, the recursion function invokes itself until the specified condition is met. In cases where the condition is not explicitly defined by the user, the function will recur indefinitely.
Different types of the recursion
Following are the types of the recursion in C programming language, as follows:
- Direct Recursion
- Indirect Recursion
- Tail Recursion
- No Tail/ Head Recursion
- Linear recursion
- Tree Recursion
Direct Recursion
When a function invokes itself multiple times within its own body, it is termed as direct recursion.
Structure of the direct recursion
fun()
{
// write some code
fun();
// some code
}
In the above structure of the direct recursion, the outer fun function recursively calls the inner fun function, and this type of recursion is called the direct recursion.
Let's create a program to showcase direct recursion in the C programming language.
Program2.c
#include<stdio.h>
int fibo_num (int i)
{
// if the num i is equal to 0, return 0;
if ( i == 0)
{
return 0;
}
if ( i == 1)
{
return 1;
}
return fibo_num (i - 1) + fibonacci (i -2);
}
int main ()
{
int i;
// use for loop to get the first 10 fibonacci series
for ( i = 0; i < 10; i++)
{
printf (" %d \t ", fibo_num (i));
}
return 0;
}
Output
0 1 1 2 3 5 8 13 21 34
Indirect Recursion
When a function is called by another function, which in turn is also called by the original function, this scenario is known as indirect recursion.
Structure of the indirect recursion
fun1()
{
// write some code
fun2()
}
fun2()
{
// write some code
fun3()
// write some code
}
fun3()
{
// write some code
fun1()
}
In this arrangement, there exist four functions: fun1, fun2, fun3, and fun4. Upon running the fun1 function, it triggers the execution of fun2. Subsequently, fun2 commences its operation by invoking fun3. This sequential pattern continues where each function triggers the next one, forming a circular execution flow. Such a technique is known as indirect recursion.
Let's create a C program to showcase indirect recursion in the C programming language.
Program3.c
#include <stdio.h>
// declaration of the odd and even() function
void odd(); // Add 1 when the function is odd()
void even(); // Subtract 1 when the function is even
int num = 1; // global variable
void odd ()
{
// if statement check and execute the block till n is less than equal to 10
if (num <= 10)
{
printf (" %d ", num + 1); // print a number by adding 1
num++; // increment by 1
even(); // invoke the even function
}
return;
}
void even ()
{
// if block check the condition that n is less than equal to 10
if ( num <= 10)
{
printf (" %d ", num - 1); // print a number by subtracting 1
num++;
odd(); // call the odd() function
}
return;
}
int main ()
{
odd(); // main call the odd() function at once
return 0;
}
Output
2 1 4 3 6 5 8 7 10 9
Tail Recursion
A function is considered tail-recursive when it calls itself recursively, and this recursive call is the final action performed by the function. Subsequently, there are no further functions or statements that trigger the recursive function.
Let's create a C program to showcase tail recursion in the C programming language.
Program4.c
#include <stdio.h>
// function definition
void fun1( int num)
{
// if block check the condition
if (num == 0)
return;
else
printf ("\n Number is: %d", num); // print the number
return fun1 (num - 1); // recursive call at the end in the fun() function
}
int main ()
{
fun1(7); // pass 7 as integer argument
return 0;
}
Output
Number is: 7
Number is: 6
Number is: 5
Number is: 4
Number is: 3
Number is: 2
Number is: 1
Non-Tail / Head Recursion
A function is classified as non-tail or head recursive when it contains a recursive call as the initial statement within the function. This implies that no other operations are executed before the recursive call. In addition, the head recursive approach defers all operations until the return time, without performing any tasks during the recursive call itself.
Let's create a program to showcase Head/Non-Tail recursion in the C programming language.
Program5.c
#include <stdio.h>
void head_fun (int num)
{
if ( num > 0 )
{
// Here the head_fun() is the first statement to be called
head_fun (num -1);
printf (" %d", num);
}
}
int main ()
{
int a = 5;
printf (" Use of Non-Tail/Head Recursive function \n");
head_fun (a); // function calling
return 0;
}
Output
Use of Non-Tail/Head Recursive function
1 2 3 4 5
Linear Recursion
A function is classified as linearly recursive when it recursively calls itself once during each execution and scales in a linear manner relative to the input size.
Let's create a program to showcase linear recursion in the C programming language.
Program6.c
#include <stdio.h>
#define NUM 7
int rec_num( int *arr, int n)
{
if (n == 1)
{
return arr[0];
}
return Max_num (rec_num (arr, n-1), arr[n-1]);
}
// get the maximum number
int Max_num (int n, int m)
{
if (n > m)
return n;
return m;
}
int main ()
{
// declare and initialize an array
int arr[NUM] = { 4, 8, 23, 19, 5, 35, 2};
int max = rec_num(arr, NUM); // call function
printf (" The maximum number is: %d\n", max); // print the largest number
}
Output
The maximum number is: 35
Tree Recursion
A function known as tree recursion involves the function invoking itself multiple times within the recursive process.
Let's create a program to showcase tree recursion in the C programming language.
Program7.c
#include <stdio.h>
// It is called multiple times inside the fibo_num function
int fibo_num (int num)
{
if (num <= 1)
return num;
return fibo_num (num - 1 ) + fibo_num(num - 2);
}
void main()
{
int num = 7;
printf (" Use of Tree Recursion: \n");
// print the number
printf (" The Fibonacci number is: %d", fibo_num(7));
}
Output
Use of Tree Recursion:
The Fibonacci number is: 13