Syntax of Recursion in C
It has the following syntax:
return_type function_name(parameters) {
if (base_condition) {
// stop recursion
return result;
} else {
// recursive call
return function_name(modified_parameters);
}
}
In this syntax,
- return_type: It represents the data type that the function returns.
- function_name: It represents the name of the function.
- base_condition: It is a condition that is used to terminate the recursion.
- Recursive condition: It is the condition where the function calls itself with modified arguments, which is regularly approach the base case.
Factorial Example in C using Recursion
Let's consider an illustration to demonstrate the process of calculating factorial recursively in the C programming language.
Example
#include <stdio.h>
int fact (int);
int main()
{
int n,f;
printf("Enter the number whose factorial you want to calculate?");
scanf("%d",&n);
f = fact(n);
printf("factorial = %d",f);
}
int fact(int n)
{
if (n==0)
{
return 0;
}
else if ( n == 1)
{
return 1;
}
else
{
return n*fact(n-1);
}
}
Output:
Enter the number whose factorial you want to calculate?5
factorial = 120
Explanation:
In this instance, we determine the factorial of a specified number through recursive computation. Initially, the fact function iteratively multiplies the number by the factorial of a value that is one less than the current number until it descends to 1. Nonetheless, the base scenario if (n == 0) erroneously yields 0, whereas it should yield 1 since 0! equals 1.
Working of Recursion in C
In C programming, recursion operates based on two key components: the Base Case and the Recursion Condition.
1) Base Case
In C recursion, the base scenario acts as a stopping point for the recursive process. It represents the most basic form of the issue where the function refrains from invoking itself. This step is crucial in averting endless recursion and stack overflow, guaranteeing that the recursive operation concludes at some point.
2) Recursive Condition
In C programming, the recursive condition refers to when a function invokes itself with an altered parameter, progressing towards the base case. This mechanism enables the function to break down a complicated problem into more manageable sub-problems iteratively. By dividing the task into smaller subtasks, a recursive function effectively executes the overall operation. Within the function, a termination criterion is established, met by certain particular subtask. Subsequently, the recursion ceases, culminating in the function returning the ultimate outcome.
Syntax:
It has the following syntax:
if (test_for_base)
{
return some_value;
}
else if (test_for_another_base)
{
return some_another_value;
}
else
{
// Statements;
recursive call;
}
C Example to find nth term of Fibonacci Series using recursion
Let's consider an instance to demonstrate how to calculate the nth Fibonacci series term using recursion in the C programming language.
Example
#include<stdio.h>
int fibonacci(int);
void 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);
}
}
Output:
Enter the value of n: 12
144
Explanation:
In this instance, we determine the n-th Fibonacci value through recursive means. Here, we employ the fibonacci function that invokes itself with reduced values (n-1 and n-2) until it hits the fundamental scenarios (n == 0 or n == 1). Subsequently, every recursive invocation sums up the two previous Fibonacci digits to derive the outcome.
Memory Management in Recursive Function Call in C
In the realm of C programming, every recursive invocation generates a fresh instance of the function, containing its specific local variables, parameters, and return address. Upon completion of the function and the return of data, this instance is then eliminated from memory. Since all the function's variables and related entities are stored in the stack, a distinct stack is upheld for each recursive call.
After the value is retrieved from the relevant function, the stack is eliminated. Recursion presents a significant level of intricacy in managing and monitoring the values during each recursive invocation. Hence, it is essential to uphold the stack and monitor the variables' values stored within it.
C Example for Memory Management in Recursive Function Call
Let's explore the following instance to grasp how memory is allocated for recursive functions.
int display (int n)
{
if(n == 0)
return 0; // terminating condition
else
{
printf("%d",n);
return display(n-1); // recursive call
}
}
Explanation:
Let's analyze this recursive function with n = 4. Initially, the function maintains multiple stacks to display the value of n at each recursion until n reaches 0. Upon reaching the base case, the stacks are unwound gradually by returning 0 to each caller. Refer to the accompanying diagram for a detailed visualization of the stack trace during the recursive process.
Types of Recursions in C
There exist different forms of recursion in C programming based on the type of recursive case present. These include:
- Direct Recursion
- Indirect Recursion
Now, we will explore these varieties of recursive functions in the C programming language individually.
Direct Recursion
In C programming, direct recursion stands out as the most commonly employed recursion technique, wherein a function invokes itself directly within its own code. This recursive call may occur singularly or multiple times within the function, allowing for the possibility of further subdividing the direct recursion.
Direct Recursion Function Example
Let's consider an example to demonstrate direct recursion in the C programming language.
Example
#include <stdio.h>
int factorial(int n) {
if (n == 0)
return 1;
else
return n * factorial(n - 1);
}
int main() { //main function
int number = 4;
printf("Factorial of %d is %d\n", number, factorial(number));
return 0;
}
Output:
Factorial of 4 is 24
Explanation
In this illustration, we calculate the factorial of a specific number using direct recursive methodology. The factorial function repetitively invokes itself with n - 1 until it reaches the fundamental condition n == 0, where it then provides a return value of 1. Within the main function, the function is invoked with the parameter 4, and the output displays the outcome (4 × 3 × 2 × 1 = 24).
a) Head Recursion
Head recursion is a type of linear recursion where the single recursive call is positioned at the start of the function. Typically, it serves as the initial instruction within the function.
Head Recursion Example in C
Let's consider an example to demonstrate head recursion in the C programming language.
Example
#include <stdio.h>
void printNumbers(int n) {
if (n == 0)
return;
printNumbers(n - 1);
printf("%d ", n);
}
int main() { //main function
int num = 5;
printf("Numbers from 1 to %d:\n", num);
printNumbers(num);
return 0;
}
Output:
Numbers from 1 to 5:
1 2 3 4 5
Explanation:
In this instance, head recursion is employed to display the numbers ranging from 1 to 5. Initially, the printNumbers function recursively invokes itself with n - 1 until n reaches 0. Subsequently, it prints the numbers while returning, resulting in the sequential display of numbers from 1 to 5.
b. Tail Recursion
Tail recursion, akin to head recursion, follows a linear pattern where the recursive call is positioned at the function's conclusion. This characteristic allows for memory optimization by decreasing the stack memory usage. This optimization process is referred to as Tail Call Optimization.
Tail Recursion Example in C
Let's consider an example to demonstrate the concept of Tail Recursion in the C programming language.
Example
#include <stdio.h>
void printReverse(int n) {
if (n == 0)
return;
printf("%d ", n);
printReverse(n - 1);
}
int main() { //main function
int num = 6;
printf("Numbers from %d to 1:\n", num);
printReverse(num);
return 0;
}
Output:
Numbers from 6 to 1:
6 5 4 3 2 1
Explanation:
In this instance, we display numbers ranging from 1 to 6 employing tail recursion. The printReverse function showcases the present number before iteratively invoking itself with n - 1 until reaching 0, serving as the base case.
c. Tree Recursion
In tree recursion, the function body contains multiple recursive calls, leading to the formation of a tree-like structure when analyzing the program flow.
Tree Recursion Example in C
Let's consider an example to demonstrate tree recursion in C programming.
Example
#include <stdio.h>
void treeRec(int n) {
if (n <= 0)
return;
printf("%d ", n);
treeRec(n - 1);
treeRec(n - 1);
}
int main() {
int num = 4;
printf("Tree Recursion Output:\n");
treeRec(num);
return 0;
}
Output:
Tree Recursion Output:
4 3 2 1 1 2 1 1 3 2 1 1 2 1 1
Explanation:
In this instance, we showcase tree recursion by illustrating how the function invokes itself twice for each n value greater than 0. It displays the present value and subsequently triggers two new instances with n - 1, thereby creating a call stack that resembles a tree structure.
Indirect Recursion
In the realm of C programming, indirect recursion holds significance as a form of recursion where one function calls another, which then calls back the initial function or another in a series, creating a loop of function invocations. This iterative process involves multiple functions working together to address a specific problem.
Indirect Recursion Example in C
Let's consider an example to demonstrate indirect recursion in the C programming language.
Example
#include <stdio.h>
void printEven(int n);
void printOdd(int n);
void printEven(int n) {
if (n <= 0)
return;
if (n % 2 == 0) {
printf("Even: %d\n", n);
printOdd(n - 1);
} else {
printOdd(n);
}
}
void printOdd(int n) {
if (n <= 0)
return;
if (n % 2 != 0) {
printf("Odd: %d\n", n);
printEven(n - 1);
} else {
printEven(n);
}
}
int main() { //main function
int num = 4;
printEven(num);
return 0;
}
Output:
Even: 4
Odd: 3
Even: 2
Odd: 1
Explanation:
In this instance, we employ indirect recursion by utilizing two functions, displayEven and displayOdd, that recursively invoke each other to display even and odd integers in a descending order starting from 4. The output exclusively includes positive numbers, terminating the recursion when n reaches 0 or becomes negative, hence excluding the printing of zero.
Advantages and Disadvantages of Recursion in C
There are various benefits and drawbacks of Recursion in C. Here are some key advantages and disadvantages:
Advantages:
- Recursion helps to make easy code writing.
- It reduces the number of unnecessary function calls.
- It is very useful when the same solution is being used.
- It reduces the length of code.
- It is very helpful in solving the data structure problem.
- It helps to evaluate Infix, prefix, and postfix stack, etc.
- In general, recursive functions are slower than their non-recursive counterparts.
- A lot of memory may be required to store intermediate results on the system stacks.
- The code is hard to read or understand.
- It is not more efficient in terms of both time and space complexity.
- If the recursive calls are not properly checked, the machine can exhaust its memory.
Disadvantages:
Recursion vs Iteration
Iteration and recursion are both methods of repeating a sequence of commands. The key contrast between them is as follows: Recursion involves a function calling itself repeatedly, while iteration occurs as a loop runs over and over until the specified condition is no longer met. Recursion is primarily utilized within a function, while iteration is applied to a series of steps that need to be reiterated.
Binary Search with Recursion
The binary search algorithm checks if the position "start" exceeds the position "end". It then recursively invokes the function to search for the element based on the data stored in the variable "mid".
We possess a series of numbers arranged in ascending sequence. Following this, we determine the middle point of the series and restrict the examination to either the left or right side of the midpoint, depending on whether the desired number is smaller or larger than the number at the midpoint.
C Example to Binary Search using Recursion
Let's take an example to demonstrate the functionality of binary search using recursion in the C programming language.
Example
#include <stdio.h>
int binarySearch(int arr[], int left, int right, int target) {
if (left > right)
return -1;
int mid = left + (right - left) / 2;
if (arr[mid] == target)
return mid;
else if (arr[mid] > target)
return binarySearch(arr, left, mid - 1, target);
else
return binarySearch(arr, mid + 1, right, target);
}
int main() { //main function
int arr[] = {1, 3, 7, 11, 22, 64};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 22;
int result = binarySearch(arr, 0, n - 1, target);
if (result != -1)
printf("Element %d found at index %d.\n", target, result);
else
printf("Element %d not found in the array.\n", target);
return 0;
}
Output:
Element 22 found at index 4.
Explanation:
In this illustration, we execute a recursive binary search on an arranged array to locate a specific value. The algorithm identifies the midpoint index and checks it against the target value. If they match, the function returns the index; if the target value is lower, it explores the left section; if higher, the right section. This process persists until the target value is located or the subarray surpasses its limits, resulting in a -1 if the value is not found. The primary function assesses this by applying it to a sample array and displays the outcome.