재귀함수(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라는 것을 사용하는데 나중에 포스팅하겠다.