Common Algorithms
Recursion Introduction
Recursion lets a method solve a problem by calling itself with a smaller input. It is a natural fit for nested structures, divide-and-conquer algorithms, and mathematical definitions.
Key Components
Base Case
The condition where recursion stops, preventing infinite calls.
Recursive Case
The part of the method that calls itself with simpler input and moves toward the base case.
Classic Example: Factorial
Factorial.java
public class Factorial {
public static int factorial(int n) {
if (n <= 1) {
return 1;
}
return n * factorial(n - 1);
}
public static void main(String[] args) {
for (int i = 0; i <= 6; i++) {
System.out.println(i + "! = " + factorial(i));
}
System.out.println("\n10! = " + factorial(10));
}
}
Tracing Calls
The call trace shows the stack growing as recursive calls are made and shrinking as results return.
Trace.java
public class Trace {
private static int depth = 0;
public static int factorial(int n) {
String indent = " ".repeat(depth);
System.out.println(indent + "→ factorial(" + n + ")");
depth++;
int result;
if (n <= 1) {
result = 1;
System.out.println(indent + " Base case: return 1");
} else {
result = n * factorial(n - 1);
System.out.println(indent + " Return " + n + " * factorial(" + (n-1) + ") = " + result);
}
depth--;
System.out.println(indent + "← returning " + result);
return result;
}
public static void main(String[] args) {
int n = ;
System.out.println("Computing factorial(" + n + "):\n");
int result = factorial(n);
System.out.println("\nFinal result: " + result);
}
}
public class Trace {
private static int depth = 0;
public static int factorial(int n) {
String indent = " ".repeat(depth);
System.out.println(indent + "→ factorial(" + n + ")");
depth++;
int result;
if (n <= 1) {
result = 1;
System.out.println(indent + " Base case: return 1");
} else {
result = n * factorial(n - 1);
System.out.println(indent + " Return " + n + " * factorial(" + (n-1) + ") = " + result);
}
depth--;
System.out.println(indent + "← returning " + result);
return result;
}
public static void main(String[] args) {
int n = ;
System.out.println("Computing factorial(" + n + "):\n");
int result = factorial(n);
System.out.println("\nFinal result: " + result);
}
}
public class Trace {
private static int depth = 0;
public static int factorial(int n) {
String indent = " ".repeat(depth);
System.out.println(indent + "→ factorial(" + n + ")");
depth++;
int result;
if (n <= 1) {
result = 1;
System.out.println(indent + " Base case: return 1");
} else {
result = n * factorial(n - 1);
System.out.println(indent + " Return " + n + " * factorial(" + (n-1) + ") = " + result);
}
depth--;
System.out.println(indent + "← returning " + result);
return result;
}
public static void main(String[] args) {
int n = ;
System.out.println("Computing factorial(" + n + "):\n");
int result = factorial(n);
System.out.println("\nFinal result: " + result);
}
}
Call Stack
A memory structure that tracks active method calls. Recursive calls add stack frames until base cases return.
Recursion and Iteration
Some recursive algorithms can also be written as loops. Comparing both versions helps clarify the tradeoff.
VsIteration.java
public class VsIteration {
public static int sumRecursive(int n) {
if (n <= 0) {
return 0;
}
return n + sumRecursive(n - 1);
}
public static int sumIterative(int n) {
int sum = 0;
for (int i = 1; i <= n; i++) {
sum += i;
}
return sum;
}
public static int powerRecursive(int base, int exp) {
if (exp == 0) {
return 1;
}
return base * powerRecursive(base, exp - 1);
}
public static int powerIterative(int base, int exp) {
int result = 1;
for (int i = 0; i < exp; i++) {
result *= base;
}
return result;
}
public static void main(String[] args) {
System.out.println("Sum 1 to 10:");
System.out.println(" Recursive: " + sumRecursive(10));
System.out.println(" Iterative: " + sumIterative(10));
System.out.println("\n2^8:");
System.out.println(" Recursive: " + powerRecursive(2, 8));
System.out.println(" Iterative: " + powerIterative(2, 8));
int n = ;
int r1 = sumRecursive(n);
int r2 = sumIterative(n);
System.out.println("\nWork comparison (sum to " + n + "):");
System.out.println(" Recursive result: " + r1);
System.out.println(" Iterative result: " + r2);
System.out.println(" Both do " + n + " additions");
}
}
public class VsIteration {
public static int sumRecursive(int n) {
if (n <= 0) {
return 0;
}
return n + sumRecursive(n - 1);
}
public static int sumIterative(int n) {
int sum = 0;
for (int i = 1; i <= n; i++) {
sum += i;
}
return sum;
}
public static int powerRecursive(int base, int exp) {
if (exp == 0) {
return 1;
}
return base * powerRecursive(base, exp - 1);
}
public static int powerIterative(int base, int exp) {
int result = 1;
for (int i = 0; i < exp; i++) {
result *= base;
}
return result;
}
public static void main(String[] args) {
System.out.println("Sum 1 to 10:");
System.out.println(" Recursive: " + sumRecursive(10));
System.out.println(" Iterative: " + sumIterative(10));
System.out.println("\n2^8:");
System.out.println(" Recursive: " + powerRecursive(2, 8));
System.out.println(" Iterative: " + powerIterative(2, 8));
int n = ;
int r1 = sumRecursive(n);
int r2 = sumIterative(n);
System.out.println("\nWork comparison (sum to " + n + "):");
System.out.println(" Recursive result: " + r1);
System.out.println(" Iterative result: " + r2);
System.out.println(" Both do " + n + " additions");
}
}
Base Case Importance
Missing or unreachable base cases lead to stack overflow. Keep examples bounded for tracing.
BaseCase.java
public class BaseCase {
public static int infiniteRecursion(int n) {
return infiniteRecursion(n - 1);
}
public static int countdown(int n) {
if (n <= 0) {
System.out.println("Liftoff!");
return 0;
}
System.out.println(n);
return countdown(n - 1);
}
public static int badBaseCase(int n) {
if (n == 0) {
return 0;
}
return badBaseCase(n - 1);
}
public static void main(String[] args) {
System.out.println("Countdown with proper base case:");
countdown(5);
System.out.println("\nTrying infinite recursion with small depth:");
System.out.println("Skipped: calling infiniteRecursion would overflow the stack.");
System.out.println("\nWrong base case with positive input (safe):");
badBaseCase(3);
}
}
Fibonacci Example
Fibonacci shows how multiple recursive calls can grow quickly.
Fibonacci.java
public class Fibonacci {
public static int fibonacci(int n) {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
private static int callCount = 0;
public static int fibonacciCounted(int n) {
callCount++;
if (n <= 1) {
return n;
}
return fibonacciCounted(n - 1) + fibonacciCounted(n - 2);
}
public static void main(String[] args) {
int maxN = ;
int countedN = ;
System.out.println("Fibonacci sequence:");
for (int i = 0; i <= maxN; i++) {
System.out.println("fib(" + i + ") = " + fibonacci(i));
}
callCount = 0;
int result = fibonacciCounted(countedN);
System.out.println("\nfib(" + countedN + ") = " + result +
", required " + callCount + " calls");
}
}
public class Fibonacci {
public static int fibonacci(int n) {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
private static int callCount = 0;
public static int fibonacciCounted(int n) {
callCount++;
if (n <= 1) {
return n;
}
return fibonacciCounted(n - 1) + fibonacciCounted(n - 2);
}
public static void main(String[] args) {
int maxN = ;
int countedN = ;
System.out.println("Fibonacci sequence:");
for (int i = 0; i <= maxN; i++) {
System.out.println("fib(" + i + ") = " + fibonacci(i));
}
callCount = 0;
int result = fibonacciCounted(countedN);
System.out.println("\nfib(" + countedN + ") = " + result +
", required " + callCount + " calls");
}
}
public class Fibonacci {
public static int fibonacci(int n) {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
private static int callCount = 0;
public static int fibonacciCounted(int n) {
callCount++;
if (n <= 1) {
return n;
}
return fibonacciCounted(n - 1) + fibonacciCounted(n - 2);
}
public static void main(String[] args) {
int maxN = ;
int countedN = ;
System.out.println("Fibonacci sequence:");
for (int i = 0; i <= maxN; i++) {
System.out.println("fib(" + i + ") = " + fibonacci(i));
}
callCount = 0;
int result = fibonacciCounted(countedN);
System.out.println("\nfib(" + countedN + ") = " + result +
", required " + callCount + " calls");
}
}
public class Fibonacci {
public static int fibonacci(int n) {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
private static int callCount = 0;
public static int fibonacciCounted(int n) {
callCount++;
if (n <= 1) {
return n;
}
return fibonacciCounted(n - 1) + fibonacciCounted(n - 2);
}
public static void main(String[] args) {
int maxN = ;
int countedN = ;
System.out.println("Fibonacci sequence:");
for (int i = 0; i <= maxN; i++) {
System.out.println("fib(" + i + ") = " + fibonacci(i));
}
callCount = 0;
int result = fibonacciCounted(countedN);
System.out.println("\nfib(" + countedN + ") = " + result +
", required " + callCount + " calls");
}
}
Practical Tree Shape
Recursive code often maps cleanly to tree-like structures.
Practical.java
public class Practical {
public static void printStructure(String name, int depth) {
if (depth <= 0) {
return;
}
String indent = " ".repeat(4 - depth);
System.out.println(indent + "├── " + name);
if (depth > 1) {
printStructure("sub_" + name + "_1", depth - 1);
printStructure("sub_" + name + "_2", depth - 1);
}
}
public static int treeSize(int depth) {
if (depth <= 0) {
return 1;
}
return 1 + treeSize(depth - 1) + treeSize(depth - 1);
}
public static int findDepth(int nodeCount, int currentDepth) {
if (nodeCount <= 1) {
return currentDepth;
}
return findDepth(nodeCount / 2, currentDepth + 1);
}
public static void main(String[] args) {
System.out.println("Directory structure (depth 3):");
printStructure("root", 3);
System.out.println("\nTree sizes:");
for (int depth = 0; depth <= 4; depth++) {
System.out.println(" Depth " + depth + ": " + treeSize(depth) + " nodes");
}
System.out.println("\nDepth calculations:");
int[] nodeCounts = {1, 2, 4, 8, 16, 32};
for (int count : nodeCounts) {
System.out.println(" " + count + " nodes → depth " + findDepth(count, 0));
}
}
}
Exercise: Practical.java
Implement a recursive method to calculate the sum of digits in a positive integer