[JavaScript] 재귀

재귀 공부 목표

• 재귀적 사고

  • 쪼개어 생각하기
  • 함수 자신의 재귀적 호출
  • 탈출 조건

• 재귀 활용(트리 구조)

  • 트리 구조
  • json 구조
  • dom 구조

재귀 함수

• 재귀란?
• 재귀 함수 언제 사용해?
• 재귀 함수 사용 연습

문제를 쪼개서 생각하기

하나의 배열이 있고, 그 배열의 합을 구하는 함수를 만든다고 가정하자

내가 생각한 공식은 반복문 이었다.

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

let sum = 0
for (let i = 0; i < arr.length; i++) {
    sum += arr[i]
}
console.log(sum);

하지만 반복문 없이 단순히 arr의 원자의 합을 구한다고 생각해 보자
한번에 합을 계산하는 것보다 하나씩 쪼개서 계산하는게 더 쉬울 것이다.

[1] sum = 1
[1, 2] sum = 3
[1, 2, 3] sum = 6
[1, 2, 3, 4] sum = 10
[1, 2, 3, 4, 5] sum = 15

즉 원자 하나에서 다른 하나를 더해가는 과정이다.

1
1 + 2
1 + 2 + 3
1 + 2 + 3 + 4
1 + 2 + 3 + 4 + 5

그렇다면 재귀는 언제 쓰일까?

저렇게 반복문으로 계산하면 되지 왜 재귀를 써? 라고 생각 할 수도 있다.

하지만 반복문이 4중 5중 으로 엄청나게 많아 진다면 시간 복잡도가 증가하고, 코드의 효율은 떨어질 것이다.

재귀의 예로 하노이의 탑을 많이 든다. 한번 찾아보고 직접 반복문으로 구현을 해보는 것은

추천드리지 않는다.

재귀적 사고

1. 가장 단순하게 정의하기

• 가장 작은 단위를 먼저 생각합니다 ex) sum 1 = 1

2. 가장 단순하게 정의한 것에서 그 부분만 해결하기

• ex) sum = sum + el

3. 다음 경우의 수를 합쳐서 생각하기

• ex) function sum을 다음 수를 생각하여 구하기

4. 마지막 결과까지 해결하기
5. 코드 구현하기

재귀의 문제로 재귀 구현하기 >>> 팩토리얼 문제

팩토리얼

function factorial (n) {
    if (n === 1) {
        return 1
    }
    return n * factorial(n - 1)
}