Recursion Basics
What is Recursion
Recursion is a technique where a function solves a problem by calling itself on a smaller version of the same problem, until the pieces become simple enough to answer directly. It mirrors how many problems are naturally defined, like a folder that contains files and other folders.
Example: What is Recursion
#include <iostream>
using namespace std;
int factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
int main() {
cout << "factorial(5): " << factorial(5) << endl;
return 0;
}public class Main {
static int factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
public static void main(String[] args) {
System.out.println("factorial(5): " + factorial(5));
}
}def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)
print("factorial(5):", factorial(5))#include <stdio.h>
int factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
int main() {
printf("factorial(5): %d\n", factorial(5));
return 0;
}Login to try C/C++/Java code in the editor
Base Case
The base case is the simplest version of the problem that the function can answer immediately without recursing further. Every recursive function needs at least one base case, or it will call itself forever until it crashes.
Example: Base Case
#include <iostream>
using namespace std;
int countdown(int n) {
if (n <= 0) return 0; // base case: stops the recursion
cout << n << " ";
return countdown(n - 1);
}
int main() {
countdown(5);
cout << "done" << endl;
return 0;
}public class Main {
static int countdown(int n) {
if (n <= 0) return 0; // base case: stops the recursion
System.out.print(n + " ");
return countdown(n - 1);
}
public static void main(String[] args) {
countdown(5);
System.out.println("done");
}
}def countdown(n):
if n <= 0: # base case: stops the recursion
return
print(n, end=" ")
countdown(n - 1)
countdown(5)
print("done")#include <stdio.h>
void countdown(int n) {
if (n <= 0) return; /* base case: stops the recursion */
printf("%d ", n);
countdown(n - 1);
}
int main() {
countdown(5);
printf("done\n");
return 0;
}Login to try C/C++/Java code in the editor
Recursive Step
The recursive step is where the function calls itself with an input that's guaranteed to move closer to the base case, such as n-1 instead of n, or a smaller slice of an array. Getting this step wrong is the most common source of recursion bugs.
Example: Recursive Step
#include <iostream>
using namespace std;
int sumDigits(int n) {
if (n == 0) return 0;
return (n % 10) + sumDigits(n / 10); // moves closer to base case each call
}
int main() {
cout << "sumDigits(1234): " << sumDigits(1234) << endl;
return 0;
}public class Main {
static int sumDigits(int n) {
if (n == 0) return 0;
return (n % 10) + sumDigits(n / 10); // moves closer to base case
}
public static void main(String[] args) {
System.out.println("sumDigits(1234): " + sumDigits(1234));
}
}def sum_digits(n):
if n == 0:
return 0
return (n % 10) + sum_digits(n // 10) # moves closer to base case
print("sum_digits(1234):", sum_digits(1234))#include <stdio.h>
int sumDigits(int n) {
if (n == 0) return 0;
return (n % 10) + sumDigits(n / 10); /* moves closer to base case */
}
int main() {
printf("sumDigits(1234): %d\n", sumDigits(1234));
return 0;
}Login to try C/C++/Java code in the editor
Call Stack
Each recursive call adds a new frame to the call stack, holding that call's local variables and its return address, and the frames unwind in reverse order as calls return. This is why deep recursion can be memory-hungry and, in extreme cases, cause a stack overflow.
Example: Call Stack
#include <iostream>
using namespace std;
int trace(int n) {
cout << "entering trace(" << n << ")" << endl;
if (n == 0) return 0;
int result = n + trace(n - 1);
cout << "returning from trace(" << n << ")" << endl;
return result;
}
int main() {
cout << "Total: " << trace(3) << endl;
return 0;
}public class Main {
static int trace(int n) {
System.out.println("entering trace(" + n + ")");
if (n == 0) return 0;
int result = n + trace(n - 1);
System.out.println("returning from trace(" + n + ")");
return result;
}
public static void main(String[] args) {
System.out.println("Total: " + trace(3));
}
}def trace(n):
print(f"entering trace({n})")
if n == 0:
return 0
result = n + trace(n - 1)
print(f"returning from trace({n})")
return result
print("Total:", trace(3))#include <stdio.h>
int trace(int n) {
printf("entering trace(%d)\n", n);
if (n == 0) return 0;
int result = n + trace(n - 1);
printf("returning from trace(%d)\n", n);
return result;
}
int main() {
printf("Total: %d\n", trace(3));
return 0;
}Login to try C/C++/Java code in the editor
Simple Recursive Problems
Recursion shines on problems that are naturally self-similar or nested, like tree traversal, divide-and-conquer algorithms, and backtracking, where expressing the solution recursively is often far shorter and clearer than writing it with explicit loops and a manual stack.
Example: Simple Recursive Problems
#include <iostream>
using namespace std;
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2); // naturally self-similar problem
}
int main() {
cout << "fib(6): " << fib(6) << endl;
return 0;
}public class Main {
static int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2); // naturally self-similar problem
}
public static void main(String[] args) {
System.out.println("fib(6): " + fib(6));
}
}def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2) # naturally self-similar problem
print("fib(6):", fib(6))#include <stdio.h>
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2); /* naturally self-similar problem */
}
int main() {
printf("fib(6): %d\n", fib(6));
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 6 topics to unlock
0/6 topics done
Complete these topics first: