재귀함수 (velog에서 옮겨옴 2024-08-05)

📌재귀함수란?

자기자신을 호출하는 함수

• 특정 조건이 만족할 때 까지 자기 자신을 계속해서 호출. 주로 반복문을 구현할 때 사용한다.
• 간결하긴 하나 공간복잡도가 높다. (종료되기전까지 이전의 값을 계속 스택에 쌓아두고 있기 때문)

 

📌재귀함수를 사용하려면

• 기저 조건 (Base Case) : 반복할 필요 없이 간단하게 계산되는 부분 (재귀 호출을 중단하는 조건). 이런 탈출조건이 명시되지 않으면 계속 자신을 호출하며 무한루프에 빠진다!
• 재귀 조건 (Recursive Case) : 함수가 자기 자신을 호출하며 반복 계산하는 부분.
  호출될수록 base case에 가까워져야한다!

function recursiveSum(num) {
  if (num === 0) {       // Base Case
    return 0
  }               

  let res = num + recursiveSum(num - 1)      // Recursive Case
  return res
}
debugger;
recursiveSum(3)    // 함수호출 💡

위 함수에서 Base Case는 'num이 0일 때, 호출을 멈추고 0을 반환하라',
Recursive Case는 'num이 0이 아닐 때, num과 recursiveSum(num - 1)의 합을 계산하라'는 의미이다.

 

💡  여기서 함수를 호출할 때 num의 값으로 3을 넘겨주는데, 만약 재귀조건을 반복 할수록 recursiveSum(3)의 값이
1씩 커지게 된다면..
recursiveSum(4)... recursiveSum(5)... recursiveSum(6) ............ recursiveSum(100).... 
이런식으로 계속 호출을 반복하게 되고 무한루프에 빠지게 된다!

∴ 위 함수에서는 재귀 조건에서 num - 1로 값이 매번 1씩 감소되도록 하고 있다.

(num === 0)의 값에 점점 가까워지게끔.

 

📌재귀함수 주의점

1. 반드시 base case가 존재해야 하고 (재귀를 멈추는 조건식)
2. 재귀호출이 반복될수록 base case에 수렴해야한다.
3. 스택 자료구조는 후입선출이라 앞의 숫자가 계속 쌓여 메모리를 차지하므로 주의!

 

* 📝 stack overflow 오류가 나면 종료조건이 없거나, 종료조건이 너무 큰 경우이다.
* 📝 stack 메모리용량은 pc마다 다르기 때문에 코드를 짤 때 미리 이런 조건을 고려 해야 한다.

 

---

 

function recursiveSum(num) {
  if (num === 0) {       // Base Case
    return 0
  }               

  let res = num + recursiveSum(num - 1)      // Recursive Case
  return res
}
debugger;
recursiveSum(3)

이제 이 함수를 실행해 recursiveSum(3)의 값을 실제로 알아보자!

1.  첫번째 호출 : recursiveSum(3). num = 3 (num이 0이 아니므로) 3 + recursiveSum(2)를 계산해준다. 이 때, recursiveSum(2)의 값을 알아야하기 때문에  (↓ 두번째 호출 실행)
2. 두번째 호출 : recursiveSum(2). num = 2 (역시 num이 0이 아니므로) 2 + recursiveSum(1)를 계산. 다시 recursiveSum(1) 값을 구하기 위해 (↓ 세번째 호출 실행)
3. 세번째 호출 : recursiveSum(1). num = 1 이니까 1 + recursiveSum(0). recursiveSum(0)의 값을 구하기 위해  (↓ 네번째 호출 실행)
4. 네번째 호출 : recursiveSum(0). 네번째 호출까지 실행하면

 

num이 0 이므로 0을 반환한다!
여기서 처음에 호출한(내가 원한 값인) recursiveSum(3)은 3 + recursiveSum(2) 이고,
recursiveSum(2)는 2 + recursiveSum(1)인 3이기 때문에 3 + 3 = 6. 

결과는 6이 나온다.

 

---

 

* 📝 NOTE  2024-08-05

 

 내가 처음에 헷갈렸던 부분이 'recursiveSum(3)은 3 + recursiveSum(2)니까 3 + 2면 5잖아?
왜 6이나오지?' 였다.

 

이 함수는 재귀함수기 때문에 recursiveSum 함수가 num에 대해 자신을 다시 호출하고, num - 1 의 값을

num에 더해서 반환하기 때문에 recursiveSum(2)는 그냥 2가 아니라 2 + recursiveSum(1)인 3이다.
∴ recursiveSum(3) = 3 + recursiveSum(2) = 3 + 3 = 6.

(⭐ 재귀함수는 자기 자신을 반복적으로 호출하고 그 결과값이 스택에 쌓인다는 개념을 잘 이해하자,,)

+ 스택은 후입선출..!