In C, recursion refers to a function calling itself in order to solve smaller instances of the same problem. It's like breaking a complex task into simpler, identical tasks. While recursion is powerful, it's important to have a base case to prevent infinite loops!
Recursion is a method where the solution to a problem depends on solutions to smaller instances of the same problem. Every recursive function has two parts:
Let's compute the factorial of a number using recursion. The factorial of a number n
is defined as:
int factorial(int n) { if (n == 0 || n == 1) { return 1; // Base case } return n * factorial(n - 1); // Recursive case } int main() { int result = factorial(5); // 5! = 120 printf("Factorial of 5 is: %d\n", result); return 0; }
factorial()
calls itself with n-1
until n
reaches 1 or 0, where it returns 1 (base case). Then the function starts returning the multiplied values back up the call stack.
The Fibonacci sequence is a series where each number is the sum of the two preceding ones. The sequence starts as 0, 1, 1, 2, 3, 5, 8, 13, and so on.
#includeint fibonacci(int n) { if (n <= 1) { return n; // Base case } return fibonacci(n - 1) + fibonacci(n - 2); // Recursive case } int main() { int result = fibonacci(6); // 8 (0, 1, 1, 2, 3, 5, 8) printf("Fibonacci of 6 is: %d\n", result); return 0; }
fibonacci()
function computes the n
th Fibonacci number by adding the previous two numbers. The recursion continues until the base case is reached.
factorial(5)
. How do the recursive calls break down? Here's what happens:
Test your understanding! Try solving this challenge:
base^exponent
.
Help others discover Technorank Learning by sharing your honest experience.
Your support inspires us to keep building!