Recursion in JavaScript

// Basic recursion
function countdown(n) {
  if (n <= 0) {
    console.log('Done!');
    return;
  }
  console.log(n);
  countdown(n - 1);
}

countdown(5); // 5, 4, 3, 2, 1, Done!

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

console.log(factorial(5)); // 120

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

console.log(fibonacci(10)); // 55

// Optimized with memoization
function fibMemo(n, memo = {}) {
  if (n in memo) return memo[n];
  if (n <= 1) return n;
  
  memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  return memo[n];
}

// Array sum
function sumArray(arr) {
  if (arr.length === 0) return 0;
  return arr[0] + sumArray(arr.slice(1));
}

console.log(sumArray([1, 2, 3, 4, 5])); // 15

// Reverse string
function reverseString(str) {
  if (str === '') return '';
  return reverseString(str.substr(1)) + str[0];
}

console.log(reverseString('hello')); // 'olleh'

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

console.log(power(2, 5)); // 32

// Flatten array
function flatten(arr) {
  const result = [];
  
  for (const item of arr) {
    if (Array.isArray(item)) {
      result.push(...flatten(item));
    } else {
      result.push(item);
    }
  }
  
  return result;
}

console.log(flatten([1, [2, [3, 4], 5], 6])); // [1, 2, 3, 4, 5, 6]

// Tree traversal
class TreeNode {
  constructor(value) {
    this.value = value;
    this.children = [];
  }
}

function traverseTree(node) {
  console.log(node.value);
  for (const child of node.children) {
    traverseTree(child);
  }
}

// Binary search tree
function searchBST(node, target) {
  if (!node) return null;
  if (node.value === target) return node;
  
  if (target < node.value) {
    return searchBST(node.left, target);
  } else {
    return searchBST(node.right, target);
  }
}

// Tower of Hanoi
function hanoi(n, from, to, aux) {
  if (n === 1) {
    console.log(`Move disk 1 from ${from} to ${to}`);
    return;
  }
  
  hanoi(n - 1, from, aux, to);
  console.log(`Move disk ${n} from ${from} to ${to}`);
  hanoi(n - 1, aux, to, from);
}

hanoi(3, 'A', 'C', 'B');

// Permutations
function permutations(str) {
  if (str.length <= 1) return [str];
  
  const result = [];
  for (let i = 0; i < str.length; i++) {
    const char = str[i];
    const remaining = str.slice(0, i) + str.slice(i + 1);
    const perms = permutations(remaining);
    
    for (const perm of perms) {
      result.push(char + perm);
    }
  }
  
  return result;
}

console.log(permutations('abc')); // ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

// Tail recursion (optimized in some engines)
function factorialTail(n, acc = 1) {
  if (n <= 1) return acc;
  return factorialTail(n - 1, n * acc);
}

// Avoid stack overflow
// Max call stack ~10,000 in most browsers
// Use iteration for deep recursion