Tower of Hanoi: A Recursive Challenge

The Tower of Hanoi is a classic puzzle involving three pegs and a number of disks of different sizes. The objective is to move the entire stack to another peg, following these rules: only one disk can be moved at a time, and a larger disk cannot be placed on top of a smaller one. Solving this problem elegantly demonstrates the power of recursion.

Instead of trying to solve the entire problem at once, we break it down. The key insight is to focus on moving the top n-1 disks, then the largest disk, and finally the n-1 disks again. This creates a self-similar subproblem.

Consider moving 4 disks from peg A to peg C, using peg B as auxiliary:

1. Move the top 3 disks from A to B (using C as auxiliary).
2. Move the 4th (largest) disk from A to C.
3. Move the 3 disks from B to C (using A as auxiliary).

The subproblem of moving 3 disks is solved in the same recursive manner. This approach leads to the following JavaScript implementation:

// Calculates the minimum number of moves required
function calculateMoves(diskCount) {
  if (diskCount === 1) {
    return 1;
  }
  // Move n-1 disks, move the largest disk, then move n-1 disks again
  return 2 * calculateMoves(diskCount - 1) + 1;
}

// Prints the sequence of moves
function solveHanoi(disk, source, destination, auxiliary) {
  if (disk === 1) {
    console.log(`Move disk ${disk} from ${source} to ${destination}`);
    return;
  }
  // Move n-1 disks to the auxiliary peg
  solveHanoi(disk - 1, source, auxiliary, destination);
  // Move the largest disk to the destination peg
  console.log(`Move disk ${disk} from ${source} to ${destination}`);
  // Move the n-1 disks from the auxiliary peg to the destination peg
  solveHanoi(disk - 1, auxiliary, destination, source);
}

// Example: Solve for 3 disks
solveHanoi(3, 'A', 'C', 'B');

Climbing Stairs: A Recursive Path

Imagine you're climbing a staircase with n steps. You can take 1, 2, or 3 steps at a time. How many distinct ways can you reach the top? This problem is a variation of the Fibonacci sequence and is perfectly suited for a recursive solution.

The recursive thinking process is to consider the last move. To reach step n, your last move could have been from step n-1 (taking 1 step), step n-2 (taking 2 steps), or step n-3 (taking 3 steps). Therefore, the total number of ways to reach step n is the sum of the ways to reach these three preceding steps.

This logic translates directly into a recursive functon. Note that this naive implementation has exponential time complexity and is inefficient for large n due to repeated calculations. For practical applications, memoization or an iterative approach would be preferred.

// Counts the number of ways to climb 'steps' stairs
function countWays(steps) {
  // Base cases: 1 way to climb 1 step, 2 ways to climb 2 steps, 4 ways to climb 3 steps
  if (steps === 1) return 1;
  if (steps === 2) return 2;
  if (steps === 3) return 4;
  
  // Recursive case: sum of ways to reach the previous three steps
  return countWays(steps - 1) + countWays(steps - 2) + countWays(steps - 3);
}

// Example: Calculate ways to climb 5 steps
console.log(`Ways to climb 5 steps: ${countWays(5)}`); // Output: 13

Quicksort: Sorting with Recursion

Quicksort is a highly efficient sorting algorithm that uses a divide-and-conquer strategy. The core idea is to select a 'pivot' element and partition the array such that all elements less than the pivot come before it, and all elements greater come after it. This process is then recursively applied to the sub-arrays of lesser and greater elements.

The recursive breakdown is as follows:

1. Choose a pivot element from the array.
2. Partition the array into two sub-arrays: elements less than the pivot and elements greater than the pivot.
3. Recursively apply Quicksort to both sub-arrays.

The base case for the recursion is an array with zero or one element, which is already sorted. Here's a JavaScript implementation:

// Sorts an array using the Quicksort algorithm
function quicksort(array) {
  // Base case: an array with 0 or 1 element is already sorted
  if (array.length <= 1) {
    return array;
  }

  // Choose the first element as the pivot
  const pivot = array[0];
  const rest = array.slice(1);

  // Partition the rest of the array
  const lessThanPivot = rest.filter(element => element <= pivot);
  const greaterThanPivot = rest.filter(element => element > pivot);

  // Recursively sort the sub-arrays and combine the results
  return [...quicksort(lessThanPivot), pivot, ...quicksort(greaterThanPivot)];
}

// Example: Sort an array of numbers
const unsortedArray = [34, 7, 23, 32, 5, 62];
const sortedArray = quicksort(unsortedArray);
console.log(sortedArray); // Output: [5, 7, 23, 32, 34, 62]