재귀 함수(recursive function) C++
목차
재귀 함수는 자기 스스로를 호출하는 함수입니다. 함수가 자기 자신을 호출한다니 약간 이상하지만 C언어 계열의 함수에서 중요한 특징입니다.
코드 조각에 불과한 함수가 스스로를 호출한다는 개념은 어쩌면 미래에는 중요한 알고리즘 학문 분야로 발전할지도 모릅니다. 실제로 인공지능 관련 프로그램에서 재귀 호출 방식이 사용되고 있습니다.
재귀라는 말이 어려워 보이지만 대다수 C++ 교재에서 기초 원리를 설명하는 예제 수준 정도는 별로 어렵지 않습니다. 이 포스팅에서는 예제와 함께 재귀 함수의 기초 개념을 설명합니다.
재귀 호출 기초
재귀 호출은 자기 자신을 호출하는 것이라고 했습니다. 예를 들어 function() 안에서 function() 을 호출하는 것 입니다. 그런데 이렇게 호출하게 되면 결국 무한 루프가 되버립니다. 원리적으로는 for 문이나 while 문의 무한 루프와도 비슷합니다.
시작점이 외부에서 함수를 호출한 것이면 종료점은 함수 내부에 있어야 합니다. main 함수에서 function()을 호출하면 function 내부에서 자신을 호출하다가 어느 시점에는 종료를 하도록 해야 합니다. 함수 내부에서 종료하는 방법에는 여러가지가 있지만 기본은 분기문을 사용합니다. if 문으로 더 이상 재귀 호출을 하지 못하도록 막아놓으면 종료하게 됩니다. 이 과정을 코드에서 보겠습니다.
아래 예제에서 recursiveFunction 의 동작원리를 이해할 수 있습니다. 재귀호출을 할 때 function(n) 다음에 function(n-1)을 하면 n이 계속 줄어듭니다. if 문으로 n값을 0보다 큰 값으로 걸어두면 n이 0이 되었을 때 더이상 재귀하지 않게 됩니다. 여기서는 n을 2로 시작하면 f(2) -> f(2-1) -> f(2-2) 로 n 값은 0이 되서 다시 호출한 곳으로 복귀(return) 합니다.
if 를 중심으로 위쪽은 정방향 실행이고 아래쪽은 역방향으로 실행합니다. 정방향이 n, n-1, n-2, … 0 나오고 if문에서 정지한 후에 역방향이 0, … n-2, n-1, n 나옵니다. 메모리의 주소를 보면 n 값이 같을 때 주소가 같습니다. 함수를 호출할 때 마다 새로운 스택 메모리를 할당하기 때문에 호출된 함수는 각각 개별적인 메모리에 위치하고 있기 때문입니다.
n값을 2를 주면 2,1,0 재귀호출 종료(if문) 0,1,2 코드에서 보면 가운데 if문을 기준으로 방향이 바뀝니다. 일반적 상식으로 코드는 위에서 부터 아래로 순서대로 실행되야 하는데 재귀함수는 새로운 방향을 만들어 버립니다.
#include<iostream>
#include<string>
using std::cout;
using std::endl;
void recursiveFunction(int n);
int main()
{
recursiveFunction(2);
return 0;
}
int count=0;
void recursiveFunction(int n)
{
// 정방향으로 실행
cout << count++ << " -> 재귀함수 n : " << n << " 주소: " << &n << endl;
if(n>0)
recursiveFunction(n-1);
// 역방향으로 실행
cout << count++ << " -> 재귀함수 n : " << n << " 주소: " << &n << endl;
return;
}
[실행결과]
0 -> 재귀함수 n : 2 주소: 0x7ffde60b75dc
1 -> 재귀함수 n : 1 주소: 0x7ffde60b75bc
2 -> 재귀함수 n : 0 주소: 0x7ffde60b759c
3 -> 재귀함수 n : 0 주소: 0x7ffde60b759c
4 -> 재귀함수 n : 1 주소: 0x7ffde60b75bc
5 -> 재귀함수 n : 2 주소: 0x7ffde60b75dc재귀 함수는 특정 알고리즘에서 코드를 간결하게 하는 장점이 있지만 모든 상황에 유용하지는 않습니다. 한번 함수를 호출할 때 마다 스택에 개별 메모리를 사용하므로 용량이 큰 데이터를 매개변수로 받는 작업이라면 상당히 부담이 됩니다. 1메가의 데이터를 매개변수로 받아서 처리하는 함수가 재귀를 할 때 마다 1메가의 메모리를 새로 사용해야 합니다. 마지막 함수에서 호출을 종료하기 전에 메모리를 그대로 점유하므로 비효율 적입니다. 또 C++ 컴파일러는 스택메모리 제한을 1메가 정도로 둡니다. 더 늘릴 수도 있지만 그 정도는 재귀 호출 몇 번 하다보면 금방 바닥이 납니다.(stack overflow)
피보나치 수열 재귀함수
피보나치는 재귀함수를 배울 때 많이 해보는 예제입니다. 함수를 보면 상당히 간략합니다. 하지만 캐시(Memoizer)를 사용하지 않으면 성능이 좋지 않다는 점도 염두해 둡니다.
#include<iostream>
#include<string>
using std::cout;
using std::endl;
int recursiveFibonacci(int n);
int count=0;
int main()
{
int num;
int result;
num=20;
for (int i = 0; i <= num; i++)
{
result=recursiveFibonacci(i);
cout <<"-> number : " << i << ", fibonacci: "<<result<<endl;
}
return 0;
}
int recursiveFibonacci(int n)
{
// cout << n << " : " << endl;
if(n==0) return 0;
if(n==1) return 1;
if(n==2) return 1;
return recursiveFibonacci(n-1)+recursiveFibonacci(n-2);
}
[실행]
-> number : 0, fibonacci: 0
-> number : 1, fibonacci: 1
-> number : 2, fibonacci: 1
-> number : 3, fibonacci: 2
-> number : 4, fibonacci: 3
-> number : 5, fibonacci: 5
-> number : 6, fibonacci: 8
-> number : 7, fibonacci: 13
-> number : 8, fibonacci: 21
-> number : 9, fibonacci: 34
-> number : 10, fibonacci: 55
-> number : 11, fibonacci: 89
-> number : 12, fibonacci: 144
-> number : 13, fibonacci: 233
-> number : 14, fibonacci: 377
-> number : 15, fibonacci: 610
-> number : 16, fibonacci: 987
-> number : 17, fibonacci: 1597
-> number : 18, fibonacci: 2584
-> number : 19, fibonacci: 4181
-> number : 20, fibonacci: 6765
요약
재귀함수의 개념을 알아 봤습니다. 재귀함수는 사용에 신중해야 합니다. 리소스를 많이 잡아먹기 때문인데요. 아직 C++의 학습 단계에서는 너무 무리해서 재귀함수를 사용하지 않는게 좋습니다. 알고리즘 적으로는 공부가 되기 때문에 루프로 할 수 있는 것들을 재귀함수로도 만들어 보면서 공부한다면 실력을 쌓는데 도움이 됩니다.
참고문서
C++ Recursion (With Example) (programiz.com)