Intro

재귀함수를 사용해서 프로그래머스 피보나치 수열 문제를 풀며 겪었던
stack overflow와 관련된 문제를 정리해 보고자 합니다.

문제 보러 가기

---

1. 숫자의 크기

피보나치 수열의 47번째 값은 2,971,215,073이고,
javascript의 int에서는 32비트의 정수 2,147,483,647 까지만 저장할 수 있습니다.

그렇기 때문에 런타임 에러가 발생했고, 이를 해결하며, 문제의 요구 조건을 맞추기 위해 모든 숫자를 전달할 때에도 1234567로 나눈 나머지를 전달해 해결했습니다.

const fibonacciNumbers = (prev, curr, count) => {
	if(count === n) return answer = (prev + curr) % 1234567
	fibonacciNumbers(curr % 1234567, (prev + curr) % 1234567, count + 1)
}
    
fibonacciNumbers(0, 1, 2)

---

2. stack overflow

두 번째 런타임 에러는 바로 위에 사용했던 재귀함수로 인해 발생했습니다.

물론 피보나치 수열에서 재귀함수를 사용하면
위와 같이 표현이 자연스럽고, 변수의 사용을 최대한 줄일 수 있지만
재귀함수는 스택 메모리를 사용하기 때문에 일정 호출 이상으로 넘어가게 되면
스택이 꽉 차게 되어 런타임 에러가 발생하게 됩니다.

하지만 for와 같은 반복문은 재귀함수와는 다르게 cpu 사이클을 반복적으로 사용하기 때문에 런타임 에러가 발생하지 않는 것입니다!
속도 또한 for문이 더 빠릅니다.

let fibonacci = [0, 1];
let [prev, curr] = fibonacci;

for(let i = 0 ; i < n - 1; i++){
    let now = (prev + curr) % 1234567;
    prev = curr % 1234567;
    curr = now
}

---

마치며..

for문이 재귀함수에 비해 빠르고, stack overflow와 같은 런타임 에러를 방지할 수 있지만, 재귀함수가 for문에 비해 적은 코드로 가독성이 좋고, 간단하게 구현할 수 있다는 장점이 있습니다.

결론적으로 무조건 for문! 무조건 재귀함수! 가 아니라 각각의 상황에 맞는 곳에 알맞게 사용하면 될 것 같습니다 :)