재귀 복습

Recursion

Recursion은 Function이 스스로를 내부에서 부르게 하여 문제를 해결하는 기술이다. 이렇게 하면 소량의 처리만 완료하고 나머지 문제를 재귀 호출에 위임할 수 있다.

• 함수를 스스로 호출하는 것
• 재귀는 반복할 구문을 함수 단위로 분리해, 특정 조건이 만족할 때 까지 실행하는 패턴으로 볼 수 있습니다.
• 재귀는 무한 반복을 방지하기 위해 탈출 조건이 있어야 합니다.

function eat(food) {
  console.log('먹기 전 음식 리스트 => ', food);
  console.log('지금 먹고있는 음식 ? ', food.pop());
  if(food.length) { // 탈출 조건
    eat(food);
  } else {
    console.log('먹을 음식이 없습니다.')
  }
}

▶ 결과

eat(['피자','치킨','족발'])
VM552:2 먹기 전 음식 리스트 =>  (3) ["피자", "치킨", "족발"]
VM552:3 지금 먹고있는 음식 ?  족발
VM552:2 먹기 전 음식 리스트 =>  (2) ["피자", "치킨"]
VM552:3 지금 먹고있는 음식 ?  치킨
VM552:2 먹기 전 음식 리스트 =>  ["피자"]
VM552:3 지금 먹고있는 음식 ?  피자
VM552:7 먹을 음식이 없습니다.

재귀의 장, 단점

1. 장점

• 알고리즘이 재귀로 표현하기에 자연스러울 경우, 프로그램의 가독성이 좋다

2. 단점

• 값이 리턴되기 전까지 호출마다 call stack을 새로 생성하므로, 메모리를 많이 사용한다.

재귀로 피보나치수열을 표현했을 경우 : callCount ? 177

let callCount = 0;

function fibonacci(num) {
  callCount ++;
  if(num < 2) {
    return num;
  }

  return fibonacci(num - 1) + fibonacci(num - 2);
}

let result = fibonacci(10);
console.log('callCount ? ', callCount); // callCount ?  177
console.log(result); // 55

재귀의 단점 보안 ( 메모이제이션(memoization) ) : callCount ? 19

• memo 배열에 계산한 값을 저장
• 다시 계산하지 않고 사용하도록 기억시킨다

// 피보나치 수열
let callCount = 0;
let fibonacci = (function() {
    let memo = [0,1];
    let fib = function(n) {
      callCount++;
      let result = memo[n];
      if(typeof result !== 'number') {
        // 없으면 계산해서 넣어라
        result = fib(n - 1) + fib(n - 2);
        memo[n] = result;
      }
      // 값이 저장되어있으면 있는거 사용
      return result;
      }

    return fib;
}());
let result = fibonacci(10);
console.log('callCount ? ', callCount); // callCount ?  19
console.log(result); // 55

// 팩토리얼
let factorial = (function() {
  let save = {};
  let fact = function(number) {
    console.log(save)
    if(number > 0) {
      let saved = save[number - 1] || fact(number - 1);
      let result = number * saved;
      save[number] = result;
      return result;
    } else {
      return 1;
    }
  }
  return fact;
}) ();
factorial(3);
factorial(4); // save = {1: 1, 2: 2, 3: 6}
factorial(5) // save = {1: 1, 2: 2, 3: 6, 4: 24}

참고글
https://www.zerocho.com/category/JavaScript/post/579248728241b6f43951af19