What is Recursion?
Recursion is a process that occurs when a function calls a copy of itself to solve a small problem. A function that calls itself is called a recursive function, and the functions that are called are called recursive calls. Recursion consists of multiple callbacks. However, it is important to repeat the termination process. Recursive code is shorter than reverse code but harder to understand.
Recursion cannot be used for all problems, but it is useful for functions that can be defined as similar functions. For example, it can be used for recursion, analysis, search, and traversal problems.
In general, the iterative solution is more efficient than the iterative solution because the call always has overhead. Any problem that can be solved iteratively can also be solved backwards. However, Tower of Hanoi, Fibonacci Sequence, Factorial, etc. Some problems such as are best solved using iteration..
Example
#include <stdio.h>
// Recursive function to print numbers from 1 to n
void printNumbers(int n) {
// Base case: if n is less than 1, stop recursion
if (n < 1) {
return;
}
// Recursive case: print n and then call printNumbers with n-1
printNumbers(n – 1);
printf(“%d “, n);
}
int main() {
int num;
printf(“Enter a positive integer: “);
scanf(“%d”, &num);
if (num < 1) {
printf(“Please enter a positive integer.\n”);
return 1;
}
printf(“Numbers from 1 to %d are: “, num);
printNumbers(num);
printf(“\n”);
return 0;
}
Output
Enter a positive integer: 5
Numbers from 1 to 5 are: 1 2 3 4 5
Recursive Function
Recursive functions work by breaking them into subtasks. An interruption in the work is identified and some work is carried out accordingly. After that the iteration stops and the final result is returned by the function.
The state in which the task is not repeated is called the base state, while the state in which the task calls itself to perform subtasks is called the recurring state. All recursive functions can be written using this format.
Syntax
return_type function_name(parameters) {
// Base case(s)
if (base_case_condition) {
// Base case logic
// return base_case_value;
}
// Recursive case(s)
else {
// Recursive logic
// recursive_call(arguments);
}
}
Memory allocation of Recursive method
Each recursive call creates a new copy of the memory path. The output is removed from memory when the process returns some information. Since all variables and other elements declared in a function are grouped, a separate group is maintained for each callback. The stack is destroyed when the value is returned by the relevant function. Recursion poses many challenges in defining and tracking the results of each callback. Therefore we need to control the group and track the results of the changes defined in the group.
Syntax
return_type function_name(parameters) {
// Base case(s)
if (base_case_condition) {
// Base case logic
// return base_case_value;
}
// Recursive case(s)
else {
// Recursive logic
// recursive_call(arguments);
return recursive_call_result;
}
}
Example
#include <stdio.h>
// Recursive function to calculate the sum of numbers from 1 to n
int sum(int n) {
// Base case: when n is 0, return 0
if (n == 0) {
return 0;
}
// Recursive case: add n to the sum of numbers from 1 to n-1
else {
return n + sum(n – 1);
}
}
int main() {
int num;
printf(“Enter a positive integer: “);
scanf(“%d”, &num);
// Check if num is positive
if (num < 1) {
printf(“Please enter a positive integer.\n”);
return 1;
}
// Calculate the sum using the recursive function
int result = sum(num);
// Print the result
printf(“Sum of numbers from 1 to %d is: %d\n”, num, result);
return 0;
}
Type of Recursion in C
- Linear Recursion
- Tail Recursion
- Binary Recursion
- Nested Recursion
- Indirect Recursion
- Multiple Recursion
-
Linear Recursion:
In linear recursion, the function is just one callback at each step. A recursive array or up to root state is called an array.
Syntax
return_type function_name(parameters) {
// Base case
if (base_case_condition) {
// Base case logic
// return base_case_value;
}
// Recursive case
else {
// Recursive logic
// recursive_call(arguments);
}
}
-
Tail Recursion:
Tail recursion is a special form of linear recursion in which the recursive call is the last function in the function. In other words, callback is the end of the function.
Syntax
return_type function_name(parameters) {
// Base case
if (base_case_condition) {
// Base case logic
// return base_case_value;
}
// Recursive case
else {
// Recursive logic
// return function_name(arguments); // Tail recursion
}
}
-
Binary Recursion:
In binary iteration, the function makes two callbacks at each step. Each callback usually represents a smaller or simpler problem.
Syntax
return_type function_name(parameters) {
// Base case(s)
if (base_case_condition) {
// Base case logic
// return base_case_value;
}
// Recursive case(s)
else {
// Recursive logic
// recursive_call1(arguments);
// recursive_call2(arguments);
}
}
-
Nested Recursion:
Nested recursion occurs when a function calls itself recursively and the arguments passed to the recursive call are evaluated by the recursive function call.
Syntax
return_type function_name(parameters) {
// Base case
if (base_case_condition) {
// Base case logic
// return base_case_value;
}
// Recursive case
else {
// Recursive logic
// recursive_call(function_name(arguments));
}
}
-
Indirect Recursion:
Indirect recursion occurs when two or more functions are called in a loop. Each function in the loop can call one or more functions in the loop.
-
Multiple Recursion:
Multiple repetition involves performing multiple repetitions of each step. This can make the tree look like a repeating pattern.