재귀함수

자기 자신을 호출하는 함수를 재귀함수라고 한다.

재귀 호출을 너무 많이 하게 되면 스택 메모리 영역에 너무 많은 공간을 할당하게 되어 스택 오버플로가 발생할 수 있다.

종료 조건을 꼭 만들어 주어야 한다.

 

함수가 호출될 때 공간이 할당되고 종료하면서 해제되는 메모리 영역을 Call Stack으로 나타낸다.

함수가 호출되면서 스택 프레임이 push되고, 함수가 종료되면 스택 프레임이 pop된다.

 

재귀 함수는 순열과 조합을 구할 때 활용할 수 있고, 이분 탐색, DFS 등 다양하게 활용된다.

 

예제1 : 피보나치 수열 구하기

#include <iostream>

using namespace std;

int fibonacci(int n);

int main(){
    
    int n;
    cin >> n;
    for(int i=0; i<n; i++){
        cout << fibonacci(i) << " ";
    }
    
    cout << endl;
    
    
}

int fibonacci(int n){

    if(n<=1)
        return n;
    else
        return fibonacci(n-1) + fibonacci(n-2);
}

 

예제 2 : 팩토리얼 

#include <iostream>

using namespace std;

int factorial(int n);

int main(){
    
    int n;
    cin >> n;
    
    for(int i=1; i<=n; i++){
        cout << factorial(i) << " ";
    }
    cout << endl;
    
}


int factorial(int n){
    if( n <= 1)
        return 1;
    else
        return n*factorial(n-1);
}