재귀함수

재귀함수

재귀함수 Recursion 은 정의 단계에서 자신을 재참조하는 함수이다.

큰 문제를 작은 부분문제로 나눠서 풀 때 사용한다.

주의사항

반드시 기저사례 종료조건 을 작성한다.

재귀호출은 코스트가 높기에 반복문으로 풀 수 있다면 반복문으로 푼다.

Factorial

/* recursion */
int factorial(int n)
{
    if (n == 1 || n == 0) return 1; // 기저사례
    return n * factorial(n - 1); // 점화식
}

/* for loop. 반복문으로 풀 수 있다면 반복문으로 푼다.*/
int factorial(int n)
{
    int ret = 1;

    for(int i = 1; i <= n; i++)
    {
        ret *= 1;
    }
    return ret;
}

Fibonacci

/* recursion */
int fibonacci(int n)
{
    if (n == 0 || n == 1) return n; // 기저사례
    return fibo (n - 1) + fibo (n - 2); // 점화식
}

피보나치 수열을 예로들어서 그림으로 표현하면 아래와 같다.

Fibonacci sequence

재귀함수는 이러한 형태처럼, 같은 문제를 또 다시 풀게 되는 문제가 있다.

이런걸 보고 겹치는 하위 문제, 즉 overlapping subproblems 라고 한다.

이러한 이유 때문에 재귀함수는 시간이 오래걸린다.

이런 문제를 효율적으로 처리하기 위해서 Dynamic Programming (DP) 라는 기법을 사용한다.