SEB Section 2 Recursive

Recursion

• Recursion은 동일한 구조의 더 작은 문제를 해결함으로써 주어진 문제를 해결하는 방법인 재귀라고 한다.
• 자기 자신을 호출하는 방식을 재귀 호출이라 부른다.

재귀는 언제 사용하는게 좋을까?

1. 주어진 문제르 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
2. 중첩된 반복문이 많거나 반복문의 중첩 횟수를 예측하기 어려운 경우

• 하노이의 탑, 조합 문제 등에 쓰인다.

재귀함수의 구성

1. 탈출 조건
2. 실행 코드

Factorial

function fac(n) {
  if (n === 1) {
    return 1;
  }

  return n * fac(n - 1);
}

fibonacci

피보나치 수열은 알고리즘 공부를 하다가 알게되었다. 피보나치의 수열은 n번째 수 = n-1 번째 수 + n-2번째 수를 구하는 수열이다. 피보나치의 수열을 나열해 보면 0, 1, 1, 2, 3, 5, 8, 13, 21, … 이다. 이를 재귀함수를 써서 코드로 구현을 해보자.

구현

function fib(n) {
  if (n <= 1) return 1;

  return fib(n - 1) + fib(n - 2);
}

시간복잡도를 고려한 구현

이렇게 코드를 실행을 시키면 시간 복잡도가 높아지게 된다. 따라서 효율적인 코드를 찾아야한다. 피보나치 수열을 들여다 보면 트리구조로 되어 있다.

이렇게 코드를 들여다 보면 n이 0과 1이 될 때까지 fibo 함수의 재귀 호출이 되고 있다. 중복적인 부분, 즉 한번 구한 항들을 기록해 놓은 다음, 그 값이 필요할 때 쓰게 된다면 더욱 효율적이게 코드를 구현할 수 있지 않을까?

function fibonacci(n) {
  //일단 초기 배열이 [0, 1]에서 시작하여 배열의 요소를 누적해 나가는 방법
  //그리고 이미 구해놓은 것은 배열의 요소로 저장해놓기..!!! 그래야 런타임이 초과되지 않는다

  let newArr = [0, 1]; //0번째 1번째 요소는 고정시켜두고

  let fib = (n) => {
    //함수 한개를 선언해주고
    if (newArr[n] !== undefined) {
      return newArr[n]; //이미 있는 건 그대로 리턴
    }
    newArr[n] = fib(n - 1) + fib(n - 2); //없는 건 새로 만들어서 저장!!!*****
    return newArr[n];
  };

  return fib(n);
}

• 0, 1번째의 값은 미리 저장해 둔다.
• 이미 저장 되어 있는 값들은 그대로 리턴 하도록 한다.
• 없는 값들은 새로 만들어서 저장을 한다.

이렇게 저장을 하는 함수를 momorization이라 한다. 기억해 두었다가 나중에 써야 겠다.

하노이 탑

하노이 탑은 처음 들어본다. 하노이 탑의 지식이 없어 먼저 하노이 탑이 무엇인지 알아보겠다.

세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 서로 다른 원판들이 있다. 퍼즐을 시작하기 전에는 한 기둥에 원판들이 큰 것에서부터 작은 것 순서대로 큰 원판이 아래로 작은 원판이 위로 순서대로 쌓여있다. 이 원판을 다른 원판으로 옮겨야 한다.

문제는 그렇게 어렵게 보이진 않는다. 하지만 여기서 조건이 따르게 된다.

1. 한 번에 하나의 원판만 옮길 수 있다.
2. 큰 원판이 작은 원판 위에 있어서는 안된다.
3. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮겨야 한다.

여기서 중요한 키 포인트는

1. ‘시작 기둥, 중간 기둥, 도착 기둥’으로 구성 되어있다.
2. n개의 원반 구성은 ‘맨 밑 원반’과 ‘나머지 n-1개의 원반 묶음’ 이다.

따라서 n-1개의 원반 묶음을 다른 기둥으로 옮긴 뒤, 도착 기둥에는 맨 밑 원반이 먼저 옮겨져야 하는 것을 기억하자.

구현

function Hanoi(num, from, other, to) {
  if (num === 0) return;
  Hanoi(num - 1, from, to, other);
  console.log(`${num}을 ${from}에서 ${to}로 이동`);
  Hanoi(num - 1, other, from, to);
}

Hanoi(3, 1, 2, 3);

1을 1에서 3로 이동
2을 1에서 2로 이동
1을 3에서 2로 이동
3을 1에서 3로 이동
1을 2에서 1로 이동
2을 2에서 3로 이동
1을 1에서 3로 이동

코드를 실행 시키면 이렇게 작동을 한다.