<aside> 💡 컴퓨터 과학에서 재귀란 자신을 정의할 때 자기 자신을 재참조하는 방법을 의미한다.
</aside>
재귀의 설명 그대로 함수에서 자기 자신을 다시 호출해 작업을 수행하는 방식이다.
그렇기에 특정 분기까지 자기 자신을 계속해서 호출하는데, 주로 반복문을 구현할 때 사용한다.
우리가 흔히 알고 있는 반복문은 for
, while
등이 있는데, 이러한 반복문으로 구현가능한 로직은 모두 재귀함수로도 가능하고 그 반대 역시 가능하다.
이러한 재귀함수의 가장 대표적인 사용 예제는 팩토리얼(Factorial)
이다.
int factorial(int n) {
if (n === 1) {
return 1;
}
return n * factorial(n-1);
}
가령 예를 들어 인자로 5을 넣는다면 5 * 4 * 3 * 2 * 1
이 되는 것이다.
이를 좀 더 이해하기 쉽게 그림으로 해당 코드가 수행될 때의 콜스택을 살펴보자.
factorial(5)를 호출했을 경우의 콜스택 변화
함수를 호출할 때마다 콜스택에는 함수의 매개변수,지역변수,반환주소값등을 모두 저장하게 되는데, factorial(5)를 호출하게되면 반환타입 부분에서 5 * factorial(5-1) 이 수행되면서 factorial(4)가 호출되고 반환을 기다리게된다.
그럼 그 다음에는 factorial(4) 에 대한 지역변수, 매개변수, 반환주소값등이 콜스택에 쌓이게되는데, 이렇게 factorial(5), factorial(4), factorial(3), factorial(2), factorial(1) 까지 차곡차곡 콜스택이 쌓이게 되고, factorial(1)에서 if(n === 1)이라는 분기에 걸리면서 드디어 해당 콜스택이 하나씩 수행되며 사라질 것이다.
이러한 재귀 함수 사용에는 스택 오버플로우(stack overflow)를 주의해야한다.