Recursion Function(재귀 함수)

재귀함수란?

• 함수를 정의할 때 자신을 재참조하는 함수
• 계속해서 자기 자신의 함수를 호출하며 같은 로직을 반복해나가고 인덱스를 변화시켜 진행되는 문제에서 사용
• ex) 피보나치

F(0) = 0, F(1) = 1 이며 N>=2일 때 F(N) = F(N-1) + F(N-2)

코드로 구축했을 때

#include <bits/stdc++.h> 
using namespace std;  
int fibo(int idx){
	if(idx == 0 || idx == 1) return idx; 
	return fibo(idx - 1) + fibo(idx - 2);
} 

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cout << fibo(10);  // 55
    return 0;
}

• 재귀함수는 크게 기저사례와 메인로직으로 나뉜다.

기저사례

• 탈출할 조건, 즉 종료조건을 의미한다.
• 재귀함수를 구축할 때는 기저사례를 가장 먼저 작성한다.
• 위 코드에서의 기저사례

if(idx == 0 || idx == 1) return idx;

메인로직

• 위 코드에서의 메인 로직

return fibo(idx - 1) + fibo(idx - 2);