재귀함수

recursion

재귀적으로 사고하기 위해서는 여러 조건을 고려해야 된다.

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

재귀 함수의 활용(트리 구조)

• 트리 구조에 재귀 함수를 활용
• JSON 구조에 재귀 함수를 활용
• DOM 구조에 재귀 함수를 활용

---

• 재귀의 의미를 이해하고, 자바스크립트에서 재귀 호출을 할 수 있어야 된다.
• 재귀함수를 base case와 recursive case로 나눠서 작성할 수 있어야 된다.
• 자료 구조 중 Tree 구조에 재귀 함수를 활용하여 모두 순회(traverse) 할 수 있어야 된다.

---

재귀란

어떤 함수가 자기 자신을 스스로 호출하는 것을 말한다.

배열의 요소들 합 구하기

자연수의 배열을 입력받아 리스트의 합을 리턴하는 함수를 구현하기

방법 1. for문 사용하기

sum 변수를 0으로 초기화 한 후, 반복문 안에서 각각의 요소에 접근해서
sum 변수에 요소를 더한다.

let arr = [1, 3, 5, 7];
let sum = 0;

for(let el of arr) {
  sum += el;
}
console.log(sum);

---

방법 2. 재귀 함수 사용하기

let arr = [24, 37, 5, 18];

위의 배열 arr의 각 요소들의 합을 구해야 되는데 배열을 한번에 합을 구하지 않고, 범위를 쪼개서 생각해 볼 것이다.

1. [24, 37, 5, 18] 을 한번에 생각하지 않고, 맨 첫번째 요소를 제외한 [37, 5, 18] 의 합을 생각해 본다.
   --> [37, 5, 18] 의 합을 구한 다음에 나온 결과값에 24를 더해주면
   --> 기존 arr의 모든 요소의 합을 구할 수 있다.

---

2. [37, 5, 18] 배열의 합을 구하는 것도 쉽지 않을 수 있다.
   그럼, 여기서 또 맨 첫번째 요소를 제외한 [5, 18]의 합을 생각해 본다.
   --> [5, 18] 의 합을 구한 다음에 나온 결과값에 37을 더하면
   --> [37, 5, 18] 의 합을 구할 수 있다.

---

3. 그럼 이제 [5, 18] 배열의 합을 구하는 대신, [18] 을 먼저 구한다.
   [18] 의 합에 5를 더하면 [5, 18] 의 합을 구할 수 있다.

---

4. 그럼 이제 남은 배열의 요소는 [18] 이다.
   [18] 의 합은 18이다.

---

위의 과정을 코드로 나타내면

let arr = [24, 37, 5, 18];

arrSumFumc([24, 37, 5, 18]) = 24 + arrSumFumc([37, 5, 18]);
arrSumFumc([37, 5, 18]) = 37 + arrSumFumc([5, 18]);
arrSumFumc([5, 18]) = 5 + arrSumFumc([18]);
arrSumFumc([18]) = 18 + arrSumFumc([]);
arrSumFumc([]) = 0;

재귀 과정 생각하기

어떤 문제를 해결할 때, 구조는 동일하지만 더 작은 경우를 쪼개서 해결하는 것을 재귀(recursion)이라고 할 수 있다.

위의 재귀의 과정을 arrSumFunc를 통해 적어놓은 것을 다시 한 번 풀어서 생각해 볼 것이다.

---

1. 원래의 배열의 모든 요소의 합을 구하는 문제에서 더 작은 경우를 생각해 보기

let arr = [24, 37, 5, 18];

arrSumFumc([24, 37, 5, 18]) = 24 + arrSumFumc([37, 5, 18]);

---

2. 계속해서 문제가 더 작아지지 않을 때 까지 더 작은 경우를 생각해 보기

arrSumFumc([37, 5, 18]) = 37 + arrSumFumc([5, 18]);
arrSumFumc([5, 18]) = 5 + arrSumFumc([18]);
arrSumFumc([18]) = 18 + arrSumFumc([]);

---

3. 이제 가장 작은 경우가 나올 때 까지 쪼개서 생각했던 것을 다시 생각해 보기

arrSumFumc([]) = 0; // 문제가 더 작아질 수 없는 순간
// 가장 작은 경우의 해결책을 적용한다.
arrSumFumc([18]) = 18 + arrSumFumc([]) = 18;
arrSumFumc([5, 18]) = 5 + arrSumFumc([18]) = 5 + 18 = 23;
arrSumFumc([37, 5, 18]) = 37 + arrSumFumc([5, 18]) = 37 + 23 = 60;
arrSumFumc([24, 37, 5, 18]) = 24 + arrSumFumc([37, 5, 18]) = 24 + 60 = 84;

---

그럼 이제 arrSumFumc 함수를 재귀 함수를 이용해서 활용할 수 있다.

arrSumFumc(arr)
1. arr이 빈 배열인 경우 = 0
2. 그 외의 경우에는 arr[0] + arrSumFumc(arr2)
--> arr2는 arr[0], 첫 요소를 제외한 나머지 요소를 가진 배열이다.

---

재귀 함수로 문제 해결하기

function arrSumFumc(arr) {
  // 재귀의 기초(base case)
  // 문제를 더 이상 쪼갤 수 없을 경우
  if(arr.length === 0) {
    return 0;
  }

  // recursive case
  // 그렇지 않은 경우
  // firstElement: 배열의 첫 번째 요소
  // restElement: 배열의 첫 번째 요소를 제외한 나머지 요소들이 담긴 배열
  return firstElement + arrSumFumc(restElement);
}

factorial로 확인하는 재귀

재귀란

어떤 함수가 자기 자신을 스스로 호출하는 것을 말한다.

function factorialFunc(n) {
  if (n === 1) {
    return 1; 
  }

  return n * factorialFunc(n-1);
}

---

위의 코드에서 n이 7일 때, 즉, 7!을 구해야 될 때를 알아볼 것이다.

function factorialFunc(n) {
  // 1!은 더이상 나눌 수 없기 때문에 1을 리턴한다.
  if (n === 1) {
    return 1; 
  }

  return n * factorialFunc(n-1);
  // return 7 * factorialFunc(6); // 5040
  // return 6 * factorialFunc(5); // 720
  // return 5 * factorialFunc(4); // 120
  // return 4 * factorialFunc(3); // 24
  // return 3 * factorialFunc(2); // 6
  // return 2 * factorialFunc(1); // 2
  // return 1; // 1
}
let result = factorialFunc(7); // 5040