재귀(recursion) : 자기 자신을 호출하는 함수

//recursion() 함수를 계속해서 호출한다.
function recursion () {
  console.log("This is")
  console.log("recursion!")
  recursion()
}

재귀로 문제 해결하기

Q. 자연수로 이루어진 배열을 입력받고, 리스트의 합을 리턴하는 함수 arrSum을 작성하세요.

arr = [1,2,3,4,5]

1. 문제를 좀 더 작게 쪼갠다.

arrSum([1,2,3,4,5]) === 1 + arrSum([2,3,4,5])
arrSum([2,3,4,5]) === 2 + arrSum([3,4,5])

2. 1번과 같은 방식으로 문제가 더는 작아지지 않을 때까지 가장 작은 단위로 문제를 쪼갠다.

arrSum([3,4,5]) === 3 + arrSum([4,5])
arrSum([4,5]) === 4 + arrSum([5])
arrSum([5]) === 5 + arrSum([])

3. 가장 작은 단위의 문제를 풂으로써 전체 문제를 해결한다.

arrSum([]) === 0;
arrSum([5]) === 5 + arrSum([]) === 5 + 0 === 5;
arrSum([4,5]) === 4 + arrSum([5]) === 4 + 5 === 9;
arrSum([3,4,5]) === 3 + arrSum([4,5]) === 3 + 9 === 12;
arrSum([2,3,4,5]) === 2 + arrSum([3,4,5]) === 2 + 12 === 14;
arrSum([1,2,3,4,5]) === 1 + arrSum([2,3,4,5]) === 1 + 14 === 15;

함수의 리턴값이 나오면서 연쇄적으로 문제가 해결되고, 최종적으로는 문제 전체가 해결된다.

4. 최종적인 arrSum()

function arrSum(arr){
  if(arr.length === 0) {return 0;} 
  //1. 빈 배열일때 0,
  //2. 가장 작은 문제를 해결하는 코드 & 재귀를 멈추는 코드
  
  return arr.shift() + arrSum(arr)
  //배열의 첫요소 + 나머지 요소가 담긴 배열을 받는 arrSum함수
  //재귀를 통해 문제를 작게 쪼개나가는 코드
}

arr.shift()

배열에서 첫번째 요소를 체거하고 제거된 요소를 반환한다.

const arr = [1,2,3];
const firstele = arr.shift();

//arr: Array[2,3]
//firtstele: 1

재귀는 언제 어따쓰냐

1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우

2. 중첩된 반복문이 많거나 반복문의 중첩 횟수를 예층하기 어려운 경우

모든 재귀함수는 반복문으로 표현할 수 있다. 그러나 재귀를 적용할 수 있는 대부분의 경우 재귀를 적용한 코드가 훨 간결하고 쉽다.

재귀적으로 생각하는 연습을 하자

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

문제를 추상적으로, 단순하게 정의한다. 그를 위해 함수의 입출력값을 정의하는 것으로 출발한다. 재귀함수를 통해 풀고자 하는 문제, 도달하고자 하는 목표를 정의하는 데 도움이 된다.

arrSum()
입력: [number]
출력: number

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

어떻게 쪼갤것인가를 고민한다. 기준을 정하고, 그 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분할 수 있는지 확인한다. 일반적으로 입력값을 기준으로 한다. 이때 입력값이나 문제의 순서와 크기를 중점으로 보아야 한다.

arrSum()
1. 배열의 크기에 따라 더 작은 문제로 나눌 수 있다.
2. arrSum([1,2,3,4])를 구하는 방법과 arrSum([2,3,4])를 구하는 방법이 동일하다.
3. 빈 배열이 입력될 경우 / 빈 배열이 아닐 경우

3 단순한 문제(base case) 해결하기

재귀의 기초는 나중에 재귀함수를 구현할 때 재귀의 탈출 조건을 구성한다.

arrSum()을 더 쪼갤 수 없는 경우는 빈 배열일 경우이다.
이때 arrSum([])은 0이다.
arrSum([]) === 0 //입력값이 빈배열인 경우: 해결

4 복잡한 문제 해결하기

남아있는 복잡한 경우를 해결한다.
길이가 1 이상인 배열이 함수에 입력된 경우 입력된 배열을 배열의 첫 요소와 나머지 요소를 입력값으로 갖는 문제로 쪼개고 둘을 더한다.
배열을 첫 요소와 더 작은 문제로 쪼개는 방법만 알면 함수 arrSum을 재귀적으로 구현할 수 있다.

arrSum([el1, el2, ..., eln]) === el1 + arrSum([el2 + ..])

5 코드 구현하기: 재귀함수 템플릿

function recursive(input1, input2, ...) {
  // base case : 문제를 더 이상 쪼갤 수 없는 경우
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }
  // recursive case : 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
}