[10주 완성 C++ 코딩테스트] 필수개념 - 재귀함수(Recursion)

* 재귀함수

1) 정의 단계에서 자신을 참조하는 함수

2) 전달되는 상태인 매개변수가 달라질 뿐 똑같은 일을 하는 함수

3) 큰 문제를 작은 문제로 쪼갤 때 사용함

 

* 재귀함수 주의사항

1) 반드시 기저사례를 써야 한다.(종료조건)

2) 사이클이 있다면 쓰면 안된다.

3) 반복문으로 될 것 같으면 반복문으로.(함수 호출에 대한 cost를 줄이기 위해. 반복문이 더 빠를 수 있음.)

 

* 예시

1) 팩토리얼 n! : 그 이전의 항을 모두 곱하는 것.

2) 피보나치: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ...

#include <bits/stdc++.h>
using namespace std; 

int fact(int n){
    if(n == 1 || n == 0) return 1;
    return n* fact(n -1);
}

int fibo(int n){
    if(n == 0 || n == 1) return n;
    return fibo(n - 1) + fibo(n - 2);
}

int n = 5;
int main() { 
    cout << fact(5) << "\n";
    cout << fibo(5) << "\n";
    return 0; 
}

점화식을 기반으로 구현한 모습 !

 

출력

120

5

 

#include <bits/stdc++.h>
using namespace std; 

int fact(int n) {
    int result = 1;
    for(int i = n; i >= 1; i--) {
        result *= i;
    }
    return result;
}

int n = 5;
int main() { 
    cout << fact(5) << "\n";
    return 0; 
}

이 때, 재귀함수는 함수 호출에 대한 cost 가 있으므로 반복문으로 구현 가능하면 위처럼 구현하기.

 

출력

120