Recursive Function
Introduction
• Recursion is the process of a function calling itself repeatedly till the
given condition is satisfied.
• A function that calls itself directly or indirectly is called a recursive
function and such kind of function calls are called recursive calls.
Two cases
Base case:
• The condition in a recursive function that stops the recursion.
• Stopping point where the function no longer needs to call itself and can
provide a direct answer.
• Without a base case, the recursive function would keep calling itself
indefinitely, leading to a stack overflow error.
Example:
int factorial(int n) {
// Base case
if (n == 0 || n == 1) {
return 1; // Base case
}
Two cases
Recursive case:
• In C, a recursive case occurs when a function calls itself.
• Typically done to solve a smaller instance of the same problem as the current
function is solving.
• It’s like breaking down a big problem into smaller, more manageable pieces.
• Each time the function calls itself, it’s working on a smaller part of the original
problem, moving towards a solution step by step.
Example:
else {
return n * factorial(n - 1); // Recursive case
}
}
Syntax
returnType functionName(parameters) {
if (base_case_condition) {
// Base Case: defines when the recursion should stop
return value;
} else {
// Recursive Case: function calls itself with modified parameters
return functionName(updated_parameters);
}
}
Factorial of a number using recursion
#include <stdio.h>
int factorial(int n) {
if (n == 0) // Base case
return 1;
else
return n * factorial(n - 1); // Recursive case
} Output:
int main() {
int num;
Enter the number:5
printf("Enter the number:"); Factorial of 5 is 120
scanf("%d",&num);
printf("Factorial of %d is %d", num, factorial(num));
return 0;
}
Fibonacci Series
#include <stdio.h>
int fibonacci(int n) {
if (n == 0) return 0; // Base case
if (n == 1) return 1;
return fibonacci(n - 1) + fibonacci(n - 2); // Recursive calls
}
int main() {
int n; Output:
printf("Enter the number:");
Enter the number:5
scanf("%d",&n);
for (int i = 0; i < n; i++) { 01123
printf("%d ", fibonacci(i));
}
return 0;
}
GCD of two numbers
#include <stdio.h>
int gcd(int a, int b) {
if (b == 0)
return a;
else
return gcd(b, a % b);
} Output:
int main() { 48 12
int a, b;
scanf("%d%d",&a,&b); GCD = 12
printf("GCD = %d", gcd(a, b));
return 0;
}
Exponentiation of two number
#include <stdio.h>
int power(int base, int exponent) {
if (exponent == 0)
return 1;
else
return base * power(base, exponent - 1);
} Output:
int main() { 23
int base, exponent;
scanf("%d%d", &base, &exponent); Result = 8
printf("Result = %d", power(base, exponent));
return 0;
}
Types of Recursion
Direct Recursion:
• When the recursion functions in C call themselves directly, it is known as
direct recursion.
Example:
void directRecursion(int n) {
if (n > 0) {
printf("%d ", n);
directRecursion(n - 1); // Function calling itself directly
}
}
Types of Recursion
Indirect Recursion:
• When a function calls another function, and that function again calls the
first function, it’s called indirect recursion.
Example:
void functionA(int n);
void functionB(int n);
void functionA(int n) {
if (n > 0) {
printf("%d ", n);
functionB(n - 1); // Calls another function
}}
void functionB(int n) {
if (n > 0) {
printf("%d ", n);
functionA(n - 1); // Calls the first function again
}}
int main() {
functionA(5);
return 0;
}
Types of Recursion
Tail Recursion:
• A recursion is called tail recursion if the recursive call is the last
statement executed by the function.
• In tail recursion, the result is built up in the function arguments.
Example:
#include <stdio.h>
int tailFactorial(int n, int result) {
if (n == 0 || n == 1)
return result;
else
return tailFactorial(n - 1, n * result); // Tail call
}
int main() { Output:
int num;
5
scanf("%d", &num);
printf("Factorial = %d", tailFactorial(num, 1)); Factorial = 120
return 0;
}
Types of Recursion
Linear Recursion:
• In linear recursion, each function calls itself only once in each
activation.
Example-Sum of first N numbers
#include <stdio.h>
int linearSum(int n) {
if (n == 0)
return 0;
else
return n + linearSum(n - 1); // Only one recursive call
}
int main() {
int n;
scanf("%d", &n);
printf("Sum = %d\n", linearSum(n));
return 0;
}
Types of Recursion
Tree Recursion:
• In tree recursion, each function calls itself more than once, usually
twice or more, leading to a tree-like expansion.
• Example: Fibonacci Series