재귀(Recursion)

재귀함수란?

재귀함수 : 함수 내에서 자기 자신을 다시 호출하는 함수

 

void Recursive(void)
{
    printf("Recursive call!\n");
    Recursive();
}

 

예를 들면, 위와 같은 함수이다.

 

그렇다면, 재귀함수의 호출을 어떻게 이해해야 할까?

완료되지 않은 함수를 다시 호출하는 것이 가능한 것인가? 라는 질문에 어떻게 답할 수 있을까?

 

재귀함수의 호출을 재진입의 관점에서 바라보면 재귀함수의 흐름을 파악하기가 어렵다. 따라서, 재귀함수의 호출은 함수의 복사본이 만들어져서 복사본이 실행되는 구조로 이해할 수 있다.

 

"Recursive 함수를 실행하는 중간에 다시 Recursive 함수가 호출되면, Recursive 함수의 복사본을 하나 더 만들어서 복사본을 실행하게 된다."

 

위 문장의 내용은 재귀적인 형태의 함수 호출이 가능한 이유를 설명한다. 실제로 함수를 구성하는 명령문은 CPU로 복사가 되어서 실행이 된다. 이때, 이 명령문은 얼마든지 복사가 가능하다. 따라서 Recursive 함수의 실행을 완료하지 않은 상태에서 Recursive 함수의 중간에 위치한 명령문을 실행하다가 다시 Recursive 함수의 앞 부분에 위치한 명령문을 CPU로 복사하는 것은 문제가 되지 않는다.

이러한 이유로 재귀적인 형태의 함수 호출이 가능하다.

 

 

재귀의 활용

피보나치 수열

피보나치 수열은 재귀적인 형태를 띠는 대표적인 수열로서 다음과 같이 전개가 된다.

0,1,1,2,3,5,8,13,21,34,55 ...

 

이를 일반화하면 다음과 같이 표현 가능하다.

 

A_n = A_n-1 + A_n-2

 

피보나치 수열의 n 번째 위치의 값을 반환하는 함수는 수학적으로 다음과 같이 표현 가능하다.

fib(n)

= 0      (n = 1)

   1      (n = 2)

   fib(n-1) + fib(n-2)      (o.w.)

 

 

이를 코드로 옮기면 다음과 같다.

#include <stdio.h>
 
int Fibo(int n)
{
    if (n == 1)
        return 0;
    else if (n == 2)
        return 1;
    else
        return Fibo(n - 1) + Fibo(n - 2);
}
 
int main(void)
{
    int i;
    for (i = 1; i < 15; i++)
        printf("%d ", Fibo(i));
 
    return 0;
}

 

 

출처 : 윤성우의 열혈 자료구조