재귀(recursion)

구조는 동일하지만 더 작은 경우를 해결함으로써 그 문제를 해결하는 방법

함수를 스스로 호출하는 것

function foo() {
  foo();
}  

주어진 문제가 (구조는 비슷하고) 더 작은 문제로 나뉘어 질 수 있는 경우
중첩된 루프가 많거나 중첩의 정도(number of loops)를 미리 알 수 없는 경우

재귀적으로 사고하는 법

잘게 쪼개어 사고하는 법
재귀적 사고
함수 자신의 재귀적호출
탈출 조건

1. 원래의 문제에서 출발하여 더 작은 경우를 생각합니다.

arrSum([10, 3, 6, 2]) = 10 + arrSum([3, 6, 2]);

2. 계속해서 문제가 더는 작아지지 않을 때까지 더 작은 경우를 생각합니다.

arrSum([3, 6, 2]) = 3 + arrSum([6, 2]);
arrSum([6, 2]) = 6 + arrSum([2]);
arrSum([2]) = 2 + arrSum([]);

3. 이렇게 문제 풀기를 미루다가, 문제가 간단해져서 바로 풀 수 있게 되는 순간에 미뤄왔던 문제들을 차근차근 해결합니다.

arrSum([]) = 0; // <-- 문제가 더는 작아지지 않는 순간
// 가장 작은 경우의 해결책을 적용한다.
arrSum([2]) = 2 + arrSum([]) = 2;
arrSum([6, 2]) = 6 + arrSum([2]) = 6 + 2 = 8;
arrSum([3, 6, 2]) = 3 + arrSum([6, 2]) = 3 + 8 = 11;
arrSum([10, 3, 6, 2]) = 10 + arrSum([3, 6, 2]) = 10 + 11 = 21;
--------------------------------------------------------------------
arrSum(arr)
1. arr이 빈 배열인 경우 = 0
2. 그 외의 경우 = arr[0] + arrSum(arr2)
   (arr2는 arr의 첫 요소를 제외한 나머지 배열)

재귀 호출 : arrSum은 (인자가 빈 배열이 아닌 경우) 실행과정 중에 자기 자신을 호출하기도 합니다. 이러한 호출 방식

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

number 타입을 요소로 갖는 배열을 입력으로 받아서 number를 리턴
arrSum: [number] => number

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

어떤 기준을 정하고 그 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분할 수 있는 지 , 일반적으로 입력값이 이 기준을 정하는 대상
중요한 관점은 순서와 크기

arrSum의 경우 입력값인 배열을 크기에 따라 구분가능
arrSum([1, 2, 3, 4])를 구하는 방법과 arrSum([2, 3, 4])을 구하는 방법은 동일할 것이므로 이 구분은 적절

문제의 입력값에 따라 경우의 수를 나눈다. -> 문제를 더 이상 쪼갤 수 없는 경우와 그렇지 않은 경우

arrSum은 입력값이 빈 배열인 경우와 그렇지 않은 경우, 각각의 경우는 다르게 처리되어야

arrSum: [number] => number
arrSum([ ])
arrSum([e1, e2, ... , en])

3. 단순한 문제 해결하기

재귀의 기초(base case)
-> 재귀 함수 구현 시 재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성

4. 복잡한 문제 해결하기

arrSum이 길이가 1 이상인 배열을 입력으로 받을 경우, 맨 앞의 요소를 따로 구하고(배열의 맨 앞의 요소이기 때문에 head라고 이름 붙이겠습니다.), 나머지 요소를 새로운 입력값으로 갖는 문제를 해결하여 얻은 결과를 head에 더합니다.
배열이 있을 때 head와 나머지 부분(tail)을 구분하는 방법만 안다면, arrSum을 해결

5. 코드 구현하기

function arrSum(arr) {
// 재귀의 기초 (base case)
// 문제를 더 이상 쪼갤 수 없을 경우
if (arr의 길이가 0인 경우) {
    return 0;
}
// recursive Case
// 그렇지 않은 경우
// head: 배열의 첫 요소
// tail: 배열의 첫 요소만 제거된 배열
return head + arrSum(tail);
}
아래는 일반적인 재귀 함수의 템플릿입니다. 재귀 함수 연습에 활용하시기 바랍니다.

function recursive(input1, input2, ...) {
  // 재귀의 기초 (base case)
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }
  // recursive Case
  // 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
  // 예1. someValue + recursive(input1Changed, input2Changed, ...)
  // 예2. someValue * recursive(input1Changed, input2Changed, ...)
}

☝자기자신 호출한것 주목

정리잘된블로그

문제를 나누어서 쪼개서 푼다
-> 순서대로
-> 순서는 입력의 크기, 반복문의 i 값