• 재귀 적으로 사고하는법
  - 잘게 쪼개어 사고하는 법
  • 재귀적 사고
  • 함수 자신의 재귀적 호출
  • 탈출 조건
• 재귀함수의 활용 (트리구조)
  - 트리구조에 재귀함수를 활용
  • JSON구조에 재귀함수를 활용
  • DOM 구조에 재귀함수를 활용

재귀의 이해

문제 : 자연수의 리스트를 입력으로 받아 리스트의 합을 리턴하는 함수 'arrSum'을 작성

function arrSum(arr){
  let sum = 0;
  for(let i=0;i<arr.arr.length;i++){
    sum+= arr[i];
  }
  return sum;
}

[10,3,6,2]

의 합을 구한다고 생각해보자.

쪼개서 생각해보기

1. [10,3,6,2] 의 합을 구하는거보다 [3,6,2]의 합을 구하는 방법을 생각해본다.
   • [3,6,2]에 10을 더해주면 원래 배열의 합을 구할수있다.
2. [3,6,2]의 합을 구하는거보다 [6,2]의 합을 구하는방법을 생각해본다.
   • [6,2]에 3을 더해주면 [3,6,2]의 합을 구할수있다.
3. [6,2] => [2]
4. [2] => 2

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

쪼개서 생각하는 방법

이런 방법을 재귀(recursion)이라고 한다.

1. 원래문제에 서출발해서 더 작은 경우를 생각
2. 계속해서 문제가 더는 작아지지 않을 때까지 더 작은 경우를 생각한다.
3. 이렇게 문제풀기를 미루다가, 문제가 간단해져서 바로 풀 수 있게 되는 순간에 미뤄왔던 문제들을 차근차근 해결한다.

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, ...)
}