재귀(recursion)

재귀란?

• 간단하게 함수를 스스로 호출하는 것이다.
• 재귀는 반복할 구문을 함수 단위로 분리해, 특정 조건이 만족할 때 까지 실행하는 패턴
• 기본적으로 반복문(for문,while문)이므로, 모든 재귀는 반복문으로 표현할 수 있다.
• 재귀는 무한 반복을 방지하기 위해 반드시 탈출 조건이 있어야한다.

재귀 함수 이해하기

재귀는 자전거를 타는 것과 비슷하다. 자전거를 처음 배울 떄, 다른 사람이 타는 것을 보면 쉬워 보이지만 막상 내가 타려고 하면 잘 안되는 것을 경혐해 본적이 있다. 그래서 자전거를 잘 타려면 계속 자전거를 타는 연습을 시도하는 수 밖에 없다. 재귀도 마찬가지이다. 재귀적 사고를 더욱 쉽게 할 수 있게 연습을 계속 해야만 하는 것이다.

재귀적으로 사고하기

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

• 재귀 함수를 통해 풀고자 하는 문제, 즉 도달하고자 하는 목표를 정의하는 데 도움이 된다.
• 재귀 적으로 사고하는 데에 가장 먼저 해야 할 일은 문제를 가장 추상적으로 또는, 가장 단순하게 정의하는 것이다.

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

• 주어진 문제를 어떻게 쪼갤 것인지 고민을 해야한다.
• 문제를 쪼갤 기준을 정하고, 정한 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분할 수 있는지 확인 해야한다.
• 일반적인 경우, 입력값으로 이 기준을 정한다.
• 이때 중요한 관점은 입력값이나 문제의 순서와 크기 이다.
• 주어진 입력값 또는 문제 상황을 크기로 구분할 수 있거나, 순서를 명확하게 정할 수 있다면 문제를 구분하는 데 도움이 된다.

3. 단순한 문제 해결하기

• 문제를 여러 경우로 구분한 다음에는, 가장 해결하기 쉬운 문제부터 해결을 한다.
• 이를 재귀의 기초(bass case)라고 한다.
• 재귀의 기초는 나중에 재귀 함수를 구현할 때, 재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성한다.
• 가장 해결하기 쉬운 문제가 아닌 경우는 recursive case라 한다.

4. 복잡한 문제 해결하기

• 마지막으로 남아있는 복잡한 경우를 해결하면 된다.

코드 예시

function arrSum(arr) {
  //Base Case : 문제를 더 이상 쪼갤 수 없는 경우 (재귀의 기초)
  if (arr.length === 0) {
    return 0;
  }
  
  // Recursive Case : 그렇지 않은 경우
  // 문제를 더 이상 쪼갤 수 없는 경우
  const head = arr[0] // head: 배열의 첫 요소
  const tail = arr.slice(1)// tail: 배열의 첫 요소만 제거된 배열

  return head + arrSum(tail);
}

Factoial로 알아보는 재귀

재귀적 사고의 대표적인 예제인 Factoial 예제

예제
수를 입력받아 n-factorial(n!; 엔-팩토리얼) 값을 리턴해야 합니다.
n! 은 1부터 n까지 1씩 증가한 모든 값의 곱입니다.

function factorial(num) { 
  // 팩토리얼 0은 1
  if (num === 0) { // base case
    return 1;
  }
  return num * factorial(num - 1); // recursive case
}

재귀의 장점과 단점

장점

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

단점

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