재귀?

어떤 함수가 스스로를 호출하는 것

재귀가 유용한 상황

• 주어진 문제를 비슷한 구조로 작게 나눌 수 있는 경우
• 중첩된 반복문이 많거나 중첩 횟수를 예측하기 어려운 경우

모든 재귀 함수는 반복문으로 표현할 수 있다. 하지만 대부분의 경우에
재귀를 적용한 코드가 간결하고 이해하기 쉽다.

재귀적인 사고

재귀 함수의 입력값과 출력값 정의하기

문제를 추상적(간단하게)으로 정의한다.

문제를 쪼개고 경우의 수 나누기

입력값, 문제의 순서, 크기를 확인하고 순서를 명확하게 정한다.
문제를 푸는 방식이 순서나 크기에 관계없이 모두 같게한다.

단순한 문제 해결하기

문제를 여러 경우로 구분한 다음,
가장 쉬운 문제부터 해결한다. 이를 base case라 한다.
base case는 나중에 재귀의 탈출 조건을 구성한다.

복잡한 문제 해결하기

남아있는 복잡한 경우를 해결한다.
예를 들어 배열일 경우 head와 tail로 구분한다.

코드 구현하기

입출력예시

console.log(sumTo(4)) // 1 + 2 + 3 + 4 = 10

예시 코드

function sumTo(num){
  if (num <= 1){
    return num;
  }
  return num + sumTo(num - 1)
}

해석

function 재귀(인풋){
  if (문제를 더 이상 쪼갤 수 없을 경우){ // Base Case
    return 단순한 문제의 해답;
  }
  return 더 작은 문제로 정의된 문제 // Recursive Case
}

재귀 동작 순서

주어진 인자 number로 factorial값을 구하는 함수가 있다.

function factorial(number) {
  if(number <= 1){
    return 1;
  }
  return number * factorial(number - 1)
}

factorial(4)를 실행시키면

factorial(4)은 factorial(3)을 리턴
factorial(3)은 factorial(2)을 리턴
factorial(2)은 factorial(1)을 리턴
factorial(1)은 1을 리턴
factorial(1)의 결과는 1
factorial(2)의 결과는 1 * 2 = 2
factorial(3)의 결과는 2 * 3 = 6
factorial(4)의 결과는 6 * 4 = 24

factorial(4)의 실행 결과는 24이다