https://dongwoo.blog/2017/05/08/번역-자바스크립트의-재귀-ptc-tco-stc-에-대한-모든-것/
원문 : http://lucasfcosta.com/2017/05/08/All-About-Recursion-PTC-TCO-and-STC-in-JavaScript.html
요즘은 모두가 함수형 프로그래밍과 그 개념에 대해서 열광적인 것 같다. 하지만 많은 사람들이 재귀(Recursion)나, 특히 적절한 꼬리 호출(Tail Call)에 대해서는 이야기하지 않는 것 같다. 이는 스택이 넘치는 일 없이 깔끔하고 간결한 코드를 작성하기 위해 매우 중요한데도 말이다.
이 글에서는 재귀를 더 잘 시각화하고 생각할 수 있는 팁을 제공하고, 적절한 꼬리 호출, 꼬리 호출 최적화, 문법적 꼬리 호출이 무엇인지와 각각의 차이점, 작동 방식, 그리고 주요 자바스크립트 엔진에서 어떤 식으로 구현되어있는지에 대해 설명하도록 하겠다.
콜스택과 스택 트레이스에 대한 이야기도 많이 하겠지만, 너무 상세한 내용까지는 다루지 않을 예정이므로, 만약 이 주제에 대해 더 자세히 알고싶다면 내가 쓴 이 글(지금까지 이 사이트에서 가장 유명한 글이다)을 읽어보길 권한다.
재귀는 특정 문제의 해결책이 해당 문제의 다른 예에 동일한 해결책을 적용하는 것에 의존하는 경우 발생한다.
예를 들어 4의 factorial 은 3의 factorial에 4를 곱하는 것으로 정의될 수 있으며, 이런 식으로 계속될 수 있다.
이것은 팩토리얼 연산이 자기 자신을 이용해서 정의될 수 있다는 것을 의미한다.
factorial(5) = factorial(4) * 5
factorial(5) = factorial(3) * 4 * 5
factorial(5) = factorial(2) * 3 * 4 * 5
factorial(5) = factorial(1) * 2 * 3 * 4 * 5
factorial(5) = factorial(0) * 1 * 2 * 3 * 4 * 5
factorial(5) = 1 * 1 * 2 * 3 * 4 * 5
간략하게 말해서, 함수가 자기 자신을 호출할 때 재귀를 갖는다고 할 수 있을 것이다.
나는 재귀에 대해서 생각할 때 첫번째 실행에서 파생된 다수의 브랜치들이 실행된 다음, 초기 호출에게 결과값을 순차적으로 돌려주는 (bubbling up) 것을 상상해본다.
앞의 팩토리얼 예제에서 우리는 첫번째 호출에서 파생된 다수의 호출이, 이미 스스로 존재하는 정의(이 경우에는 0의 팩토리얼, 즉 1을 의미)에 다다를때까지 발생하는 것을 볼 수 있다. 그 후에는 이 정의의 결과값이 반환되면서 (bubbles up) 그 값으로 다른 작업을 할 수 있게 되고, 그 작업이 또다시 값을 반환하고, 이런 식의 과정이 “최초” 호출에 다다를때까지 반복된다.
만약 우리가 factorial 함수를 인수 5를 넘겨주면서 호출했을 때를 표현하려 한다면 다음과 같을 것이다.
컴파일러 이론과 함께 생각해 보면, 이 과정은 문맥 자유 문법을 사용해서 최종 값에 다다를때까지 문장을 만들어내는 과정과 아주 유사하다.
처음이라 추상적으로 느껴질 수도 있겠지만, 이번에는 피보나치 수열에서 N번째 수를 계산해 내는 함수를 분석하면서 이러한 사고가 어떻게 다른 방식으로 적용되는지를 시각화해서 보여주도록 하겠다.
우리의 피보나치 함수 코드는 다음과 같다.