그냥 게임개발자
재귀함수(Recursion) 본문
재귀함수
- 재귀함수(Recursion)는 정의 단계에서 자신을 재참조하는 함수
- 전달되는 상태인 매개변수가 달라질 뿐 똑같은 일을 하는 함수
- 큰 문제를 작은 부분문제로 나누어서 풀 때 사용한다.
주의사항
- 반드시 기저사례를 써야 한다.
기저사례라는 것은 종료 조건을 말한다. - 사이클이 있다면 쓰면 안된다.
ex) func(a) 가 func(b)를 호출한 뒤 func(b)가 다시 func(a)를 호출하는 것 - 반복문으로 풀 수 있다면 반복문으로 푸는 것이 맞다.
예시 코드들
#include <stdio.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(n) << " " << fibo(n) << '\n';
return 0;
}
여기서 보면 팩토리얼을 모른다?
괜찮다 우리한텐 위키형들이 있다.
뭔소리야 이건 또
근데 걱정하지말자 점화식만 쓰자.
여기서 보게 되면 어차피 재귀함수를 통해 n이 -1이되면서 줄어들면서 fact함수를 계속 가는 것을 볼 수 가 있다.
결국 우리는 이 점화식을 맞춰서 사용하는 거다.
피보나치 수열도 똑같다.
피보나치 수열에 대한 점화식이다.
보면 F(0) = 0, F(1) = 1
즉 F(n) = F(n-1) + F(n-2)이다.
ㅇㅇㅇ 잘 맞추었다.
이러면 정말 잘 실행이 된다.
근데 반복문으로 풀 수 있는 것은 반복문으로 푼다고 했다.
int fact(int n)
{
int value = 1;
for (int i = 1; i <= n; ++i)
{
value *= i;
}
return value;
}
이와 같이 팩토리얼은 바꿀 수 있다.
함수 코스트가 비용이 들기 때문에 이런식으로 바꿔서 사용할 수 있다.
다만 피보나치 수열은 반복문으로 만들기가 조금 복잡하다.
dp라는 것을 사용하는데 나중에 포스팅하겠다.
'내 개인적인 공부 > 알고리즘' 카테고리의 다른 글
반복문을 통한 순열 (0) | 2024.04.04 |
---|---|
조합(Combination) (1) | 2024.04.02 |
순열 - 재귀함수로 만드는 순열 (0) | 2024.04.01 |
순열(Permutation) (0) | 2024.03.31 |
문제 풀 때 주의 (0) | 2024.03.31 |