재귀(Recursion)란?


<aside> 💡 컴퓨터 과학에서 재귀란 자신을 정의할 때 자기 자신을 재참조하는 방법을 의미한다.

</aside>

재귀 함수(Recursion Function)란?

재귀의 설명 그대로 함수에서 자기 자신을 다시 호출해 작업을 수행하는 방식이다.

그렇기에 특정 분기까지 자기 자신을 계속해서 호출하는데, 주로 반복문을 구현할 때 사용한다.

우리가 흔히 알고 있는 반복문은 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)를 호출했을 경우의 콜스택 변화

함수를 호출할 때마다 콜스택에는 함수의 매개변수,지역변수,반환주소값등을 모두 저장하게 되는데, 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

이러한 재귀 함수 사용에는 스택 오버플로우(stack overflow)를 주의해야한다.