[C++ 기본 공부정리] 11-3. 재귀함수(recursive function)

공부 내용을 정리하는 목적 이므로 참고용으로만 읽어 주시기 바랍니다. 틀린 부분에 대한 지적은 감사합니다.

먼저 재귀의 뜻을 알아보면, 재귀(recursion)의 정의는 어떤 것을 정의할 때 자기 자신을 참조하는 것을 뜻한다. 즉, 재귀 함수란 재귀 호출(recursive call)을 사용하는 함수이다. 재귀 호출은 어떤 함수가 내부에서 자기 자신을 다시 호출하는 것을 뜻한다. 재귀 호출을 사용할 경우 언제 호출을 그만둘 것인지를 정의해야 한다. 그렇지 않으면 무한루프처럼 계속 자기 자신을 호출하게 되므로 종료를 위한 조건을 가진 명령문을 포함해야 한다.

 

재귀 함수 동작

동작 원리는 함수가 명령을 수행한 뒤 자기 자신을 다시 호출한다. 재귀 호출을 종료할 조건을 만나게 되면 이전 자기 자신에서 자신을 호출한 곳으로 돌아가며 호출한 곳 밑에 코드가 남아있다면 더 진행한 뒤 }을 만나 함수를 끝내는 것을 반복하여 결국 함수가 종료된다.

장점 - 복잡한 문제를 간단하게 논리적으로 표현할 수 있도록 해주며 변수의 사용을 줄일수 있기 때문에 사용한다.

단점 - 함수의 call이 반복되므로 stack의 메모리를 많이 사용하여 stack overflow의 위험이 크다.

 

만약 해당 숫자 부터 1까지의 곱을 표현하는 팩토리얼을 계산하는 함수를 만든다고 가정하자.

 

재귀함수를 사용하지 않고 반복문을 통해서 구현하게 되면 함수 내 i란 변수는 왜 사용되었고 result라는 변수는 어디에 사용되는지 직접 해석해야 무슨 동작을 하는 코드인지 알 수가 있다. 하지만 재귀 함수를 사용하면 해당 알고리즘에 대한 논리를 바로 코드로 전환할 수 있다.

 

해당 알고리즘을 생각해 보면 주어진 값까지의 모든 자연수를 곱하는 것이다. 5까지의 곱은 1~4까지의 곱에 5를 곱하고 4까지의 곱은 1~3까지의 곱에 4를 곱하고 마지막 1까지의 곱은 그냥 1이다.

즉, 주어진 수 n이 1이 아니라면 n에 n-1까지의 곱한 결과를 곱하면 된다.

 

위에서 생각한 알고리즘을 재귀함수를 통해 만든 모습이다.

Factorial(5)로 main에서 호출되면 num매개변수에 들어간 값이 1이 아니므로 return 5*Factorial(4)가 실행된다.

이때 다시 자기자신인 Factorial이 호출 매개변수로 4의 값이 넘겨지고 1이 아니므로 return 4*Factorial(3)가 실행된다. 이 동작이 반복되어 return 3*Factorial(2), return 2*Factorial(1)이 차례로 호출된다.

마지막에는 num이 1이므로 조건문에 걸려 return 1;을 실행하게 된다. 이때 함수가 종료되며 반환 값을 가지고 함수를 호출한 곳으로 돌아가게 되어 지금까지 계산되지 않은 값이 거꾸로 올라가며 계산된다.

Factorial(1) 은 1이 반환

Factorial(2) 은 2*Factorial(1) -> 2*1 이 반환

Factorial(3) 은 3*Factorial(2) -> 3*2*1 이 반환

Factorial(4) 은 4*Factorial(3) -> 4*3*2*1 이 반환

Factorial(5) 은 5*Factorial(4) -> 5*4*3*2*1 이 반환

위 흐름으로 반환되어 결국 main에서 호출한 위치로 돌아가 5*4*3*2*1의 값을 반환하게 된다.

 

그림을 통해 확인하면 이와 같은 방법으로 동작 된다.

 

위 재귀 함수에서 만약 if문이 존재하지 않는다면 계속 num-1 값이 인수로 들어가 무한루프에 빠져 stack의 메모리가 부족할 때까지 동작되어 overflow로 인해 종료될 것이다.

재귀 함수는 굉장히 간결해 보이지만 위와 같은 이유처럼 값이 굉장히 커지게 되면 Factorial(1000), Factorial(999)... Factorial(1)까지 전부 생성해야 하므로 무한루프가 아니더라도 stack의 메모리를 전부 써버릴 수 있기 때문에 비효율적이다.