1: Understanding Recursive Functions
A recursive function is a function that calls itself either directly or indirectly. Recursive functions provide an elegant way to solve problems that can be broken down into smaller, similar subproblems.
- Example of Recursive Function:
int factorial(int n) {
if (n == 0 || n == 1) {
return 1;
} else {
return n * factorial(n - 1);
}
}
2: Recursion vs. Iteration
- Recursion:
- Uses function calls to solve a problem by breaking it down into smaller subproblems.
- May consume more memory due to function call overhead and maintaining a call stack.
- Iteration:
- Uses loop structures (e.g.,
for,while) to repeatedly execute a block of code until a condition is met. - Typically more efficient in terms of memory usage compared to recursion.
- Uses loop structures (e.g.,
3: Recursive Examples
Here are some examples of recursive functions:
-
Calculate Factorial:
int factorial(int n) {
if (n == 0 || n == 1) {
return 1;
} else {
return n * factorial(n - 1);
}
}
-
Compute Fibonacci Sequence:
int fibonacci(int n) {
if (n <= 1) {
return n;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
-
Find Greatest Common Divisor (GCD) using Euclid’s algorithm:
int gcd(int a, int b) {
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}
4: Practice and Examples
- Practice Exercise:
- Write a recursive function to calculate the sum of all natural numbers from 1 to
n. - Implement a recursive function to compute the power of a number (
base^exponent).
- Write a recursive function to calculate the sum of all natural numbers from 1 to
#include <stdio.h>
// Recursive function to calculate sum of natural numbers from 1 to n
int sumOfNaturalNumbers(int n) {
if (n == 0) {
return 0;
} else {
return n + sumOfNaturalNumbers(n - 1);
}
}
// Recursive function to compute power (base^exponent)
int power(int base, int exponent) {
if (exponent == 0) {
return 1;
} else {
return base * power(base, exponent - 1);
}
}
int main() {
int n = 5;
printf("Sum of natural numbers from 1 to %d: %dn", n, sumOfNaturalNumbers(n));
int base = 2, exp = 3;
printf("%d raised to the power %d: %dn", base, exp, power(base, exp));
return 0;
}
Recursive functions are powerful tools for solving problems that involve repetitive subproblems. Understanding recursion and its applications is important for writing elegant and efficient code in C. Practice implementing recursive functions to gain proficiency in this programming technique.