Recursion is a programming technique where a function calls itself in order to solve a problem. The function typically works by breaking down a large problem into smaller, more manageable subproblems, which it solves by calling itself. This continues until a base case is met, which stops the recursion.
A recursive function generally has two main parts:
-
Base Case: This is the condition that stops the recursion and prevents the function from calling itself indefinitely. Without a base case, the recursion would continue forever.
-
Recursive Case: This is where the function calls itself with modified arguments to work towards the base case.
1.
Factorial Calculation
A function that calculates the
factorial of a number.
#include <stdio.h>
int
factorial(int n) {
if (n == 0)
return 1;
return n * factorial(n - 1);
}
int
main() {
int num = 5;
printf("Factorial of %d is %d\n",
num, factorial(num));
return 0;
}
2.
Fibonacci Sequence
A function that returns the nth
Fibonacci number.
#include <stdio.h>
int
fibonacci(int n) {
if (n <= 1)
return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
int
main() {
int num = 6;
printf("Fibonacci number at position
%d is %d\n", num, fibonacci(num));
return 0;
}
3.
Sum of Natural Numbers
A function to calculate the sum of
natural numbers up to a given number.
#include <stdio.h>
int
sumNaturalNumbers(int n) {
if (n == 0)
return 0;
return n + sumNaturalNumbers(n - 1);
}
int
main() {
int num = 5;
printf("Sum of natural numbers up to
%d is %d\n", num, sumNaturalNumbers(num));
return 0;
}
4.
Power of a Number
A function to compute the power of a
number.
#include
<stdio.h>
int
power(int base, int exp) {
if (exp == 0)
return 1;
return base * power(base, exp - 1);
}
int
main() {
int base = 2, exp = 3;
printf("%d raised to the power of %d
is %d\n", base, exp, power(base, exp));
return 0;
}
5.
Binary Search (Recursive)
A function that searches for an
element in a sorted array using recursion.
#include <stdio.h>
int
binarySearch(int arr[], int low, int high, int target) {
if (low > high)
return -1;
int mid = (low + high) / 2;
if (arr[mid] == target)
return mid;
if (arr[mid] > target)
return binarySearch(arr, low, mid - 1,
target);
return binarySearch(arr, mid + 1, high,
target);
}
int
main() {
int arr[] = {1, 3, 5, 7, 9, 11};
int target = 7;
int result = binarySearch(arr, 0, 5,
target);
if (result != -1)
printf("Element found at index
%d\n", result);
else
printf("Element not found\n");
return 0;
}
6.
Reverse a String
A function to reverse a string using
recursion.
#include
<stdio.h>
#include <string.h>
void
reverseString(char str[], int start, int end) {
if (start >= end)
return;
char temp = str[start];
str[start] = str[end];
str[end] = temp;
reverseString(str, start + 1, end - 1);
}
int
main() {
char str[] = "Hello";
reverseString(str, 0, strlen(str) - 1);
printf("Reversed string: %s\n",
str);
return 0;
}
7.
Finding GCD (Greatest Common Divisor)
A function to compute the greatest
common divisor of two numbers using recursion.
#include <stdio.h>
int
gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
int
main() {
int a = 56, b = 98;
printf("GCD of %d and %d is %d\n",
a, b, gcd(a, b));
return 0;
}
8.
Tower of Hanoi
A function to solve the Tower of
Hanoi problem.
#include <stdio.h>
void
towerOfHanoi(int n, char source, char target, char auxiliary) {
if (n == 1) {
printf("Move disk 1 from %c to
%c\n", source, target);
return;
}
towerOfHanoi(n - 1, source, auxiliary,
target);
printf("Move disk %d from %c to
%c\n", n, source, target);
towerOfHanoi(n - 1, auxiliary, target,
source);
}
int
main() {
int n = 3;
towerOfHanoi(n, 'A', 'C', 'B');
return 0;
}
9.
Count Digits of a Number
A function that counts the number of
digits in a number.
#include <stdio.h>
int
countDigits(int n) {
if (n
== 0)
return 0;
return 1 + countDigits(n / 10);
}
int
main() {
int num = 12345;
printf("Number of digits in %d is
%d\n", num, countDigits(num));
return 0;
}
10.
Print All Natural Numbers Up to n
A function that prints all natural
numbers from 1 to a given number.
#include <stdio.h>
void
printNumbers(int n) {
if (n == 0)
return;
printNumbers(n - 1);
printf("%d ", n);
}
int
main() {
int num = 5;
printf("Natural numbers from 1 to %d:
", num);
printNumbers(num);
printf("\n");
return 0;
}
