[Algorithm] 재귀함수

✔️ 재귀함수란(recursion)?

- 정의 단계에서 자신을 재참조하는 함수 ( 똑같은 함수를 계속 호출함 )

- 전달되는 상태인 매개변수(함수를 정의할 때 사용하는 변수)가 달라질 뿐 똑같은 일을 하는 함수 

- 큰 문제를 작은 부분 문제로 나눠서 풀 때 사용함

 

✔️ 주의사항

- 반드시 종료 조건을 쓸 것

- 사이클이 있다면 쓰지 말 것

- 반복문으로 해결 가능하면 반복문으로 해결할 것

 

💻 팩토리얼

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

int fact(int n){ //5! 구하는 점화식
	if(n==1||n==0)return 1;
	return n*fact(n-1); 
} 

int fact1(int n){ //반복문으로 해결
	int ret=1;
	for(int i=1;i<=n;i++){
		ret*=i;
	}
	return ret;
}

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


>> 120 120

점화식을 사용하여 재귀함수를 통해 구할 수 있지만 반복문으로 해결할 수 있다면 반복문으로 해결하는 것이 좋다.

---

💻 피보나치

fibo(n) = fibo(n - 1) + fibo(n - 2)

fibo(1)과 fibo(2)는 1이다.

그럼 수열은 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... 이것을 재귀함수로 나타내보면 ?

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

int fibo(int n){
	cout<<"f(n)="<<n<<"\n";
	if(n==1||n==0)return n; //종료조건 
	return fibo(n-1)+fibo(n-2); //그 전의 항과 전전의 항을 더한다 
}
int n=4;
int main(){
	
	cout<<fibo(n)<<"\n";
}

타고타고 올라가는 것이 어렵게 느껴질 수 있지만 점화식을 보고 많은 디버깅을 통해 구현하는 것이 중요하다!