재귀함수와 콜스택

재귀함수 (Recursive Function)

재귀함수는 자기 자신을 재참조하여 문제를 수행하는 함수이다.

a recursive function can be defined as a routine that calls itself directly or indirectly.
https://www.geeksforgeeks.org/recursive-functions/

for문이나 while문을 사용하는 대신 재귀함수를 사용하면 가독성이 높아지고, 자연스레 재사용성을 도모할 수 있다. 다만 함수를 끝내는 base case가 반드시 수반되어야 stack이 overflow 되는 것을 방지할 수 있다.

다음은 재귀함수의 예시다.

function func(count) {
  if (count > 0) {
    console.log(count, '현재');
    func(count - 1);
  }
  console.log('결과', count);
}

func(3);

3 현재
2 현재
1 현재
결과 0
결과 1
결과 2
결과 3

func(3)이 호출되고 if문 내부의 count - 1인 2를 인자로 func(2)가 실행된다. if문 내부는 count가 0이 되기 전까지 진입하게 된다. count가 0이 되면 console에 결과 0 만 찍힐거라 예상했는데 결과 0부터 결과 3까지 모두 결과가 출력되는 걸 볼 수 있다. 게다가 역순으로 출력되었다.

콜스택의 동작원리를 보면 알 수 있다.

콜스택(Call Stack) 동작원리

재귀 함수에서 함수 호출이 일어날 때마다 해당 함수의 호출 정보가 콜스택에 쌓인다. 함수의 실행이 완료되면(base case) 해당 함수의 호출 정보는 콜스택에서 제거되는데, 이때 제거되는 순서는 역순이다. 따라서 결과 3 은 func(3) 의 호출이 모두 종료된 후에야 호출 스택에서 역순으로 출력된다.