Recursion Examples

Recursion Examples

Let's see recursion in action with some classic examples. First up: factorial. The factorial of n (written as n!) is n × (n-1) × (n-2) × ... × 1. So 5! = 5 × 4 × 3 × 2 × 1 = 120. Notice how factorial(n) = n × factorial(n-1)? That's the recursive definition right there.

Next: Fibonacci sequence. You know, 0, 1, 1, 2, 3, 5, 8, 13... Each number is the sum of the two before it. Fibonacci(0) = 0, Fibonacci(1) = 1, Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2). Simple to write, but incredibly inefficient without memoization. We'll get to that later.

Then there's Tower of Hanoi - the classic puzzle. Move n disks from source to target using an auxiliary peg. Rules: only move one disk at a time, never put a larger disk on a smaller one. The recursive solution is elegant - move n-1 disks to auxiliary, move largest disk to target, move n-1 disks from auxiliary to target. Beautiful.

Power Function

Here's another useful one: calculating powers. Instead of using Math.pow(), write your own recursive power function. base^exp = base × base^(exp-1). Base case: anything to the power of 0 is 1. Simple, clean, recursive.

Remember, recursion isn't always the most efficient solution. Sometimes it leads to repeated calculations (like in naive Fibonacci). But it's a powerful tool to have in your toolbox. Use it wisely, and always think about whether iteration might be simpler for your specific problem.

function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}

function fibonacci(n) {
  if (n <= 0) return 0;
  if (n === 1) return 1;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

function power(base, exp) {
  if (exp === 0) return 1;
  return base * power(base, exp - 1);
}

console.log(factorial(5));
console.log(fibonacci(7));
console.log(power(2, 10));