16-2-나.재귀호출이 가능한 이유

함수가 자신을 호출한다는 것은 선뜻 이해하기 힘든 동작이다. 재귀 호출이 어떻게 가능하며 자신을 호출하고도 무한 루프에 빠지지 않는 이유는 무엇인지 그 내부를 조금 연구해 보도록 하자. 함수가 호출될 때 어떤 일이 벌어지는지 이해하고 재귀 호출이 가능한 문법적 근거를 알게 되면 이해의 폭이 넓어지고 스스로 재귀 호출 함수를 백방으로 응용할 수 있게 될 것이다.

함수가 호출되면 호출된 함수에 대한 정보들이 스택에 생성되는데 이를 스택 프레임이라고 한다. 스택 프레임에는 복귀 번지, 인수, 지역변수 등의 정보들이 저장된다. 이 정보들은 각각의 함수 호출시마다 매번 생성되며 각각의 호출 인스턴스의 스택 프레임은 독립적이다.

같은 함수가 여러 번 호출되더라도 각 호출에 사용되는 인수나 지역변수들은 호출별로 따로 기억된다. 설사 같은 함수가 반복적으로 호출되더라도 각 함수의 스택 프레임은 개별적으로 생성되는 것이다. Factorial 예제에서 Factorial(1)이 실행 중일 때의 스택 모양을 그려 보면 다음과 같다.

각 Factorial 함수 호출 인스턴스는 스택에서 고유한 영역을 차지하고 있으며 이 영역에 자신의 지역변수(인수도 일종의 지역변수이다.)를 기억한다. 지역변수는 함수가 진행중인 작업의 상태를 기억하는데 재귀 호출에 의해 자신을 다시 호출하더라도 이 정보는 스택에 고스란히 유지된다.

즉, Factorial(5)가 Factorial(4)를 호출할 때 인수 n이 5에서 4로 바뀌면서 파괴되는 것이 아니라 새로운 스택 영역에 새로운 지역변수가 새로 생성되는 것이다. Factorial(5)의 n은 5의 값을 유지하며 Factorial(4)는 새로운 변수 n을 할당받아 4라는 값을 전달받는다. Factorial(5)는 Factorial(4)를 호출하고 이 함수가 리턴할 때까지 대기하면서 자신의 실행상태들을 지역변수에 그대로 간직하고 있는 것이다.

Factorial(5)와 Factorial(4)는 같은 함수이지만 모든 정보를 개별적으로 가지는 다른 호출 인스턴스이다. 컴파일러에게 이름이 같다는 것은 아무 의미가 없다. 그래서 자신을 호출하더라도 각 호출 인스턴스는 스택상에 다른 함수들로 기록되며 서로 방해받지 않고 잘 동작할 수 있는 것이다. 재귀 호출이 가능한 물적 토대는 함수 호출시마다 생성되는 스택 프레임이며 각 호출에 대해 독립적으로 저장되는 지역변수가 재귀 호출의 문법적 근거이다. 지역변수의 개념이 없는 베이직이나 포트란은 재귀 호출을 지원하지 않는다.

재귀 호출이 무한 호출이 되지 않는 이유는 함수 내부에 반환점이 있기 때문이다. 일정한 조건이 되면 스택에 생성된 호출 인스턴스를 역으로 되짚어 돌아갈 수 있는 장치가 있기 때문에 무한히 반복되지 않고 언젠가는 종료될 수 있는 것이다. 만약 다음과 같은 함수를 만든다고 해 보자.

int func() {

return func();

}

이런 함수는 반환점없이 자기 자신을 무한히 호출하기 때문에 제대로 된 재귀 호출 함수라고 할 수 없다. 단순한 무한 루프이며 끝이 없기 때문에 이런 함수를 실행하면(일단 컴파일은 된다는 얘기다. 컴파일러는 이것이 진짜 무한 루프인지까지는 판단하지 못한다.) 그 즉시 프로그램은 자폭해 버릴 것이다. 재귀 호출이 안전하려면 반드시 조건에 의해 재귀를 끝낼 수 있는 구문이 포함되어 있어야 한다. Factorial 예제에서는 if (n <= 1)이 반환점의 역할을 하고 있다.

재귀 호출이 가능한 이유와 무한 루프가 되지 않는 이유에 대해 알아보았으므로 이제 재귀 호출의 특성과 주의점을 자연스럽게 도출할 수 있을 것이다. 재귀 호출은 각 호출 인스턴스마다 스택 공간을 소모하므로 호출 깊이가 너무 깊어서는 안되며 일정 회수를 넘지 않도록 관리해야 할 필요가 있다. 자신을 중복 호출하는 깊이가 수천, 수만회 이상 된다면 스택 공간이 소진되는 사태(Stack Overflow)가 발생할 수 있으므로 이 점을 항상 주의해야 한다. 스택이란 유한한 메모리 공간이다.

재귀 호출 함수가 몇 번이나 재귀를 할 수 있는가는 스택의 현재 남은 양과 함수 내부에서 사용하는 지역변수의 총 크기에 따라 달라진다. 스택이 많이 남아 있을수록, 지역변수 크기가 작을수록 더 많은 재귀를 할 수 있다. 그래서 깊은 재귀 호출을 하는 프로그램은 옵션 조정을 통해 스택을 기본값보다 더 크게 잡아주는 것이 좋고 재귀 호출 함수의 지역변수는 꼭 필요한 것만 선언하여 스택 공간을 낭비하지 않도록 해야 한다.

최대 재귀 회수도 관리의 대상이다. 만약 Factorial(1234567) 호출을 한다면 어떻게 될 것인가 생각해 보자. 이 경우 스택에는 최대 120여만개의 Factorial 함수 인스턴스가 생성될 것이며 스택 공간은 이렇게 넓지 않기 때문에 이런 호출을 처리할 수 없다. 스택 오버플로우 에러를 방지하려면 호출원에서 일정 회수 이상을 넘지 않도록 하거나 아니면 함수 내부에서 한계값 이상은 거부하도록 if (n > LIMIT) return 1; 따위의 안전 장치를 마련할 필요가 있다.

반환점의 조건이 잘못 설정된 경우도 스택 오버플로우가 발생할 수 있다. Factorial 예제의 반환 조건문은 if (n <= 1)로 되어 있는데 이 조건을 if (n == 1)로 작성했다고 해 보자. n이 1일 때 1!은 1로 정의되어 있으므로 1을 반환하는 것이 자연스러우며 if (n == 1) 조건문을 반환점으로 설정해도 이 예제는 잘 동작한다. 하지만 사용자의 부주의로 Factorial(-3)이 전달되었을 경우 이 함수는 무한 재귀(실제로는 약 40억번 정도)하는 잠재적인 문제가 있다. 반복 회수를 최종 사용자가 지정하는 경우는 극단적인 에러까지도 처리할 수 있도록 반환 조건을 충분히 안전하게 설정해야 한다.