Recursion
1. What is Recursion?
In programming, Recursion is a technique where a function calls itself in order to solve a problem.
Simple Analogy: Russian Nesting Dolls
Imagine you have a set of Russian nesting dolls. You open the first, largest doll, and inside you find... another doll, just slightly smaller. You open *that* doll, and inside you find another, smaller doll. This continues until you open a tiny, solid doll that doesn't open. This tiny, solid doll is your "stop" condition.
Recursion works the same way:
· The "problem" is the large, outer doll.
· The function "solves" a small piece of the problem, and then "calls itself" to open the next smaller doll.
· This continues until the function hits the "stop" condition (the smallest doll).
2. The Two Parts of a Recursive Function
Every recursive function MUST have two parts, or it will run forever (until your program crashes).
1. Base Case:
· This is the "stop" condition. It's the smallest, simplest version of the problem that can be solved directly.
· In our analogy, it's the tiny, solid doll.
· It does not make another recursive call.
· If you forget the base case, you will get an infinite recursion (a "Stack Overflow").
2. Recursive Step:
· This is the part where the function calls itself.
· It breaks the current problem down into a slightly smaller, simpler version.
· The function calls itself to solve that *smaller* problem.
· It then uses the result of the smaller problem to solve its current problem.
3. Example 1: Factorial
The classic
example is calculating the factorial of a number (n!).
·
5! =
5 * 4 * 3 * 2 * 1 = 120
·
4! =
4 * 3 * 2 * 1 = 24
Notice the
pattern: 5! is just 5 * 4!. And 4! is just 4 * 3!. This is a recursive relationship!
·
Problem: factorial(n)
·
Recursive Step: n * factorial(n-1)
·
Base Case: What's the simplest
case? factorial(0) is 1. This is our stop condition.
/* * Example 1: Factorial using Recursion*/
#include <stdio.h>
// Prototype for our recursive function
long long factorial(int n);
int main() {
int number = 5;
printf("The factorial of %d is %lld\n", number, factorial(number));
number = 0;printf("The factorial of %d is %lld\n", number, factorial(number));
return 0;
} /* * Recursive definition of factorial*/
long long factorial(int n) {
// 1. BASE CASE: The "stop" condition.
if (n == 0) {
printf(" (Base Case: n=0, returning 1)\n");
return 1;
}// 2. RECURSIVE STEP: Call self with a smaller problem.
else {
printf(" (Recursive Step: n=%d, calling factorial(%d))\n", n, n - 1);
return n * factorial(n - 1);
}}4. How Recursion *Actually* Works (The Call Stack)
This is the most important part to understand. How does the computer keep track of all these function calls? It uses a special area of memory called the "Call Stack."
Think of the Call Stack like a stack of plates. When you call a function, you place its information (its local variables) on top of the stack. When a function returns, you take its plate off the top.
Let's trace factorial(3):
1.
main() calls factorial(3).
o Stack:
[factorial(3)]
2.
factorial(3) runs. n is 3. It's not the base case. It
needs to call factorial(2) to
get its answer. It "pauses" and waits.
o Stack:
[factorial(3), factorial(2)]
3.
factorial(2) runs. n is 2. It's not the base case. It
needs to call factorial(1). It
"pauses" and waits.
o Stack:
[factorial(3), factorial(2), factorial(1)]
4.
factorial(1) runs. n is 1. It's not the base case. It
needs to call factorial(0). It
"pauses" and waits.
o Stack:
[factorial(3), factorial(2), factorial(1), factorial(0)]
5.
factorial(0) runs. n is 0. This is the BASE
CASE! It does not call itself. It just returns 1.
o factorial(0) finishes and is popped
off the stack.
6.
We're back in factorial(1). It
was "paused," waiting for factorial(0) to
return. It got the value 1. Now
it can finish its calculation: return
1 * 1; (which is 1).
o factorial(1) finishes and is popped
off the stack.
7.
We're back in factorial(2). It
was "paused," waiting for factorial(1). It
got the value 1. Now
it can finish: return
2 * 1; (which is 2).
o factorial(2) finishes and is popped
off the stack.
8.
We're back in factorial(3). It
was "paused," waiting for factorial(2). It
got the value 2. Now
it can finish: return
3 * 2; (which is 6).
o factorial(3) finishes and is popped
off the stack.
9.
We're back in main(),
which receives the final answer: 6.
5. Recursion vs. Iteration (Loops)
You can solve *any* recursive problem with a loop (iteration). For example, here is factorial with a loop:
long long factorial_loop(int n) {
long long result = 1;
for (int i = 1; i <= n; i++) {
result = result * i; }return result;
}So, which is better?
|
Recursion |
Iteration (Loops) |
|
Often simpler, more elegant code for problems that are "naturally recursive." (e.g., sorting, trees) |
Code can be longer and more complex to write. |
|
Slower. Every function call adds overhead (pushing to the stack). |
Faster. No function call overhead. |
|
Uses more memory. Every call adds to the stack. |
Uses less memory. Just a few variables. |
|
Risk of Stack Overflow if
the recursion is too deep (e.g., |
No risk of stack overflow. Can run forever (infinite loop) but won't crash the program. |
Conclusion: For simple problems like Factorial, loops are more efficient. We use Factorial to *teach* recursion because it's easy to understand. Recursion is *truly* powerful for complex problems like Merge Sort or searching a file system, where the loop-based solution is very complicated.
6. Example 2: Fibonacci Series
The Fibonacci
series is 0, 1, 1, 2, 3, 5, 8, ... where each number is the sum of the
two preceding ones.
·
Problem: fib(n) (the
n-th number)
·
Recursive Step: fib(n-1) + fib(n-2)
·
Base Cases: We need two! fib(0) = 0 and fib(1) = 1.
/* * Example 2: Fibonacci Series using Recursion*/
#include <stdio.h>
int fibonacci(int n);
int main() {
int count = 10;
printf("First %d Fibonacci numbers:\n", count);
for (int i = 0; i < count; i++) {
printf("%d ", fibonacci(i));
}printf("\n");
return 0;
} int fibonacci(int n) {
// Base Case 1
if (n == 0) {
return 0;
}// Base Case 2
else if (n == 1) {
return 1;
}// Recursive Step
else {
return fibonacci(n - 1) + fibonacci(n - 2);
}}Note on Fibonacci: This recursive solution is elegant, but extremely
inefficient. To calculate fib(5), it must
calculate fib(4) and fib(3). But to
calculate fib(4), it recalculates fib(3) and fib(2). It re-calculates the same values over and over. A loop is much,
much faster.
7. Example 3: Ackerman Function (Advanced)
This function (from your syllabus) is a famous example of a function that is defined recursively and is *not* a simple loop. It grows extremely fast, much faster than factorials or exponents.
It's defined as:
· A(m, n) = n + 1, if m = 0
· A(m, n) = A(m-1, 1), if m > 0 and n = 0
· A(m, n) = A(m-1, A(m, n-1)), if m > 0 and n > 0
/* * Example 3: Ackerman Function (Advanced) * WARNING: Do not try large numbers! A(4, 2) is 2^65536 - 3.*/
#include <stdio.h>
int ackerman(int m, int n);
int main() {
// Try only VERY small numbers.
int m = 2, n = 1;
printf("Ackerman(%d, %d) = %d\n", m, n, ackerman(m, n)); // A(2, 1) = 5
m = 3; n = 0;printf("Ackerman(%d, %d) = %d\n", m, n, ackerman(m, n)); // A(3, 0) = 5
return 0;
} int ackerman(int m, int n) {
// Base Case 1
if (m == 0) {
return n + 1;
}// Recursive Case 1
else if (m > 0 && n == 0) {
return ackerman(m - 1, 1);
}// Recursive Case 2 (nested recursion)
else if (m > 0 && n > 0) {
return ackerman(m - 1, ackerman(m, n - 1));
} // Default case (shouldn't be reached)
return 0;
}