[Topic #자료구조 05] Recursion 대표 4가지 유형 구현 with JavaScript

// 재귀 유형 01 - Factorial

// Iterative
// T.C: O(n)
// S.C: O(1)
function factorialIterative(n) {
  let result = 1;
  for (let i = 1; i <= n; i += 1) {
    result *= i;
  }
  return result;
}

// Recursive
// T.C: O(n)
// S.C: O(1) // O(n)
function factorialRecursive01(n) {
  if (n === 0) return 1;
  return n * factorialRecursive01(n - 1);
}

// 참고
function factorialRecursive02(n) {
  return n > 0 ? n * factorialRecursive02(n - 1) : 1;
}

function factorialRecursive03(n) {
  return (n > 0 && n * factorialRecursive03(n - 1)) || 1;
}

// Simple test cases
for (let i = 0; i <= 6; i += 1) {
  console.log(`${i}! = ${factorialIterative(i)}`);
}
console.log('---------------------');
for (let i = 0; i <= 6; i += 1) {
  console.log(`${i}! = ${factorialRecursive01(i)}`);
}
console.log('---------------------');
for (let i = 0; i <= 6; i += 1) {
  console.log(`${i}! = ${factorialRecursive02(i)}`);
}
console.log('---------------------');
for (let i = 0; i <= 6; i += 1) {
  console.log(`${i}! = ${factorialRecursive03(i)}`);
}

 

// 재귀 유형 02 - Power

// Iterative
// T.C: O(n)
// S.C: O(1)
function powerIterative(x, n) {
  let result = 1;
  for (let i = 1; i <= n; i += 1) {
    result *= x;
  }
  return result;
}

// Recursive 1
// T.C: O(n)
// S.C: O(1) // O(n)
function powerRecursive01(x, n) {
  if (n === 0) return 1;
  return x * powerRecursive01(x, n - 1);
}

// Recursive 2
// T.C: O(lnN)
// S.C: O(1) // O(lnN)
function powerRecursive02(x, n) {
  if (n === 0) return 1;
  else if (n % 2 === 0) {
    return powerRecursive02(x, n / 2) * powerRecursive02(x, n / 2);
  }
  return x * powerRecursive02(x, n - 1);
}

// Simple test cases
for (let i = 0; i <= 10; i += 1) {
  console.log(`2의 ${i}제곱 = ${powerIterative(2, i)}`);
}
console.log('-------------------');
for (let i = 0; i <= 10; i += 1) {
  console.log(`2의 ${i}제곱 = ${powerRecursive01(2, i)}`);
}
console.log('-------------------');
for (let i = 0; i <= 10; i += 1) {
  console.log(`2의 ${i}제곱 = ${powerRecursive02(2, i)}`);
}

 

// 재귀 유형 03 - Fibonacci

// Iterative
// T.C: O(n)
// S.C: O(1)
function fibonacciIterative(n) {
  let [a, b] = [0, 1];
  for (let i = 1; i <= n; i += 1) {
    [a, b] = [b, a + b];
  }
  return a;
}

// Recursive 1
// T.C: O(2^n)
// S.C: O(1) // O(2^n)
function fibonacciRecursive01(n) {
  if (n === 0 || n === 1) return n;
  return fibonacciRecursive01(n - 1) + fibonacciRecursive01(n - 2);
}

// Recursive 2 - using memoization (dynamic programming)
// T.C: O(n)
// S.C: O(n)
const cacheArray = Array.from({ length: 100 });
function fibonacciRecursive02(n) {
  let result;
  if (cacheArray[n]) return cacheArray[n];
  if (n === 0 || n === 1) result = n;
  else result = fibonacciRecursive02(n - 1) + fibonacciRecursive02(n - 2);
  cacheArray[n] = result;
  return result;
}

for (let i = 0; i <= 10; i += 1) {
  console.log(`n=${i}\t==>\t${fibonacciIterative(i)}`);
}
console.log('--------------------------');
for (let i = 0; i <= 10; i += 1) {
  console.log(`n=${i}\t==>\t${fibonacciRecursive01(i)}`);
}
console.log('--------------------------');
for (let i = 0; i <= 10; i += 1) {
  console.log(`n=${i}\t==>\t${fibonacciRecursive02(i)}`);
}

 

// 재귀 유형 04 - Hanoi

// Recursive
// T.C: O(2^n)
// S.C: O(1)

let count = 0;

function move(plate, src, des) {
  console.log(`${plate} move from ${src} to ${des}`);
  count += 1;
}

function hanoiRecursive(n, src, des, tmp) {
  if (n > 0) {
    hanoiRecursive(n - 1, src, tmp, des);
    move(n, src, des);
    hanoiRecursive(n - 1, tmp, des, src);
  }
}

hanoiRecursive(3, 'A', 'C', 'B');
console.log(count);

---

자세한 내용은 추후 업데이트 하겠습니다