[알고리즘] 너무 쉬운 재귀함수

 

코드를 짤 때면 재귀를 사용한 함수를 만날 때가 많은데, 조금만 복잡해도 이게 어떻게 동작했더라? 헷갈리는 경우가 많았다. 가장 단순한 예시(누산기)의 분석을 통해 재귀함수를 머릿속에 박아놓자.

function sumUpTo(n) {
    // 종료 조건: n이 1이면 1을 반환
    if (n === 1) {
        return 1;
    }

    // 현재 숫자 n을 더하고, 그 다음 숫자에 대해 재귀 호출
    return n + sumUpTo(n - 1);
}


let result = sumUpTo(5);  // 1부터 5까지의 합 구하기
console.log(result);  // 최종 결과 출력

---

실행 흐름

첫 번째 호출: sumUpTo(5)

n = 5, return 5 + sumUpTo(4)을 호출.

 return n + sumUpTo(n - 1);

두 번째 호출: sumUpTo(4)

n = 4, return 4 + sumUpTo(3)을 호출

 return n + sumUpTo(n - 1);

세 번째 호출: sumUpTo(3)

n = 3, return 3 + sumUpTo(2)을 호출.

 return n + sumUpTo(n - 1);

네 번째 호출: sumUpTo(2)

n = 2, return 2 + sumUpTo(1)을 호출.

 return n + sumUpTo(n - 1);

다섯 번째 호출: sumUpTo(1)

n = 1이므로 종료 조건에 도달하여 1을 반환.

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

---

이제 돌아가기

다섯 번째 호출에서 1을 반환하고,

// sumUpTo(n - 1)= 1

네 번째 호출에서는 2 + 1 = 3을 반환하고,

//n=2, sumUpTo(n - 1) = 1 

return n + sumUpTo(n - 1);

세 번째 호출에서는 3 + 3 = 6을 반환하고,

//n=3, sumUpTo(n - 1) = 3

return n + sumUpTo(n - 1);

두 번째 호출에서는 4 + 6 = 10을 반환하고,

//n=4, sumUpTo(n - 1) = 6

return n + sumUpTo(n - 1);

첫 번째 호출에서는 5 + 10 = 15를 반환.

//n=5, sumUpTo(n - 1) = 10

return n + sumUpTo(n - 1);

 

최종 결과

15

---

코드 설명

sumUpTo(5)를 호출하면서 5부터 1까지 하나씩 줄여가며 재귀적으로 호출한다. 
종료 조건은 n === 1일 때, 더 이상 호출하지 않고 1을 반환한다. 
그런 후에 각 호출에서 n 값을 더하고, 자기 자신을 호출하면서 최종 결과를 누적한다.

---

왜 재귀 함수인가?

함수가 자기 자신을 호출하면서, 문제를 더 작은 문제로 나누고, 결국 종료 조건에 도달해서 결과를 돌아가며 구하는 방식이 재귀 함수다.  이 예시는 재귀 함수의 가장 기본적인 형태로, 각 호출이 점점 더 작은 문제를 해결하고 마지막에 모두 합쳐져서 최종 결과를 구하는 방식이다.