Recursion in Programming
What is Recursion?
Recursion is when a function calls itself to solve a smaller version of the problem.
This continues until the problem becomes small enough that it can be solved directly. That smallest case is called the base case.
Recursion Example
Adding two numbers together is easy to do, but adding a whole range of numbers can be tricky.
Recursion makes it simple: break it down into the task of adding one number at a time.
def sum_range(k):
if k > 0: # base case
return k + sum_range(k - 1)
else:
return 0
result = sum_range(10)
print(result) # 55function sumRange(k) {
if (k > 0) { // base case
return k + sumRange(k - 1);
} else {
return 0;
}
}
const result = sumRange(10);
console.log(result); // 55public class Main {
public static int sum(int k) {
if (k > 0) { // base case
return k + sum(k - 1);
} else {
return 0;
}
}
public static void main(String[] args) {
int result = sum(10);
System.out.println(result); // 55
}
}#include <iostream>
using namespace std;
int sum(int k) {
if (k > 0) { // base case
return k + sum(k - 1);
} else {
return 0;
}
}
int main() {
int result = sum(10);
cout << result; // 55
return 0;
}Example Explained
When sum(10) is called, it adds 10 to the sum of all smaller numbers, like this:
10 + sum(9)
10 + ( 9 + sum(8) )
10 + ( 9 + ( 8 + sum(7) ) )
...
10 + 9 + 8 + 7 + ... + 1 + sum(0)
10 + 9 + 8 + 7 + ... + 1 + 0Since sum(0) just returns 0, the recursion stops and the result is calculated.
Countdown Example
This example prints numbers down from 5 to 1, using recursion:
def countdown(n):
if n == 0: # base case
print("Done!")
else:
print(n)
countdown(n - 1) # recursive call
countdown(5)function countdown(n) {
if (n === 0) { // base case
console.log("Done!");
} else {
console.log(n);
countdown(n - 1); // recursive call
}
}
countdown(5);public class Main {
static void countdown(int n) {
if (n == 0) { // base case
System.out.println("Done!");
} else {
System.out.println(n);
countdown(n - 1); // recursive call
}
}
public static void main(String[] args) {
countdown(5);
}
}#include <iostream>
using namespace std;
void countdown(int n) {
if (n == 0) { // base case
cout << "Done!";
} else {
cout << n << endl;
countdown(n - 1); // recursive call
}
}
int main() {
countdown(5);
return 0;
}Factorial Example
The factorial of a number (n!) is the product of all numbers from 1 to n.
Example: 5! = 5 * 4 * 3 * 2 * 1 = 120
This can be solved naturally with recursion:
def factorial(n):
if n == 1: # base case
return 1
else:
return n * factorial(n - 1)
print(factorial(5))function factorial(n) {
if (n === 1) { // base case
return 1;
} else {
return n * factorial(n - 1);
}
}
console.log(factorial(5));public class Main {
static int factorial(int n) {
if (n == 1) { // base case
return 1;
} else {
return n * factorial(n - 1);
}
}
public static void main(String[] args) {
System.out.println(factorial(5));
}
}#include <iostream>
using namespace std;
int factorial(int n) {
if (n == 1) { // base case
return 1;
} else {
return n * factorial(n - 1);
}
}
int main() {
cout << factorial(5);
return 0;
}Summary
- Recursion is when a function calls itself.
- A base case is needed to stop the recursion.
- Recursion is useful for problems that break down into smaller, similar problems (like factorial, traversing folders, tree/graph algorithms).
Note: Recursion is powerful but can use a lot of memory if not carefully written. Always make sure you have a base case, or the recursion may go on forever!