알고리즘 - 재귀(Recursion)

재귀 : 어떤 함수가 스스로를 호출

동일한 구조의 더 작은 문제를 해결함으로써 주어진 문제를 해결하는 방법

재귀함수(Recursive Function)

모든 재귀함수는 반복문 사용을 통해 표현할 수 있지만 재귀 용법을 적용해 코드를 간결하고 이해하기 쉽게 만드는 것이 목적이다.

재귀함수 구성

• base case : 재귀 탈출 조건
• recursive case : 반복 조건

재귀적 사고 연습

1. 입력값과 출력값 정의
   • 문제를 추상적 혹은 가장 단순하게 정의
2. 문제를 기준에 따라 경우의 수 나누기
   • 입력값과 문제의 순서와 크기에 따라 문제를 쪼갤 기준 구분
3. 단순한 문제 해결 - 재귀의 기초(base case)
   • 재귀의 탈출 조건 구성
4. 복잡한 문제 해결
   • 남아있는 복잡한 문제 해결
5. 코드 구현

재귀 문제 풀이

문제 : 하노이탑

문제 출처

https://programmers.co.kr/learn/courses/30/lessons/12946

풀이

const answer = [];

const hanoi = (n, src, dst, mid) => {
  //base case
  if (n === 1) answer.push([src, dst]);
  else {
    // recursive case
    hanoi(n - 1, src, mid, dst);
    answer.push([src, dst]);
    hanoi(n - 1, mid, dst, src);
  }
};

function solution(n) {
  hanoi(n, 1, 3, 2);
  return answer;
}

let output = solution(2);
console.log(output); // [ [1,2], [1,3], [2,3] ]