함수의 재귀적 호출의 이해

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

 

ex)

void Recursive(void)

{

    printf("Recursive call! \n");

    Recursive();

}

Recursive 함수내의 Recursive 함수가 호출되면, Recursive 함수의 복사본이 만들어져서 복사본이 실행되는 구조로 재귀함수를 진행한다.

 

RecursiveFunc.c

함수를 구성하는 명령문은 CPU로 이동이 되어서(복사가 되어서)실행이 된다. 그런데 이 명령문은 얼마든지 CPU로 이동이(복사가) 가능하다. 즉 Recursive함수의 중간까지 명령문을 실행하다가 다시 Recursive함수의 앞부분에 위치한 명령문을 CPU로 이동시키는 것은 문제가 되지 않는다.

또한 위 코드처럼 재귀함수를 정의하는데 있어서 탈출조건을 구성하는 것은 매우 중요한일이다.

 

재귀의 활용

피보나치 수열 : Fibonacci Sequence

피보나치 수열은 재귀적인 형태를 띄는 대표적인 수열로서 앞엣것 두개를 더해서 현재의 수를 만들어가는 수열이다. 첫번째, 두번째 값은 0,1로 고정이고 세번째부터 앞의 두수를 더하여 수열을 만들어간다.

 

피보나치 수열 수학적 표현

 

피보나치 수열의 수학적 표현

위 수식의 코드

int Fibo(int n)

{

     if(n == 1)

         return 0;

     else if(n== 2)

         return 1;

     else

        return Fibo(n-1)+Fib(n-2);

}

 

 

FibonacciFunc.c

위 코드의 함수 호출 순서를 정리하기 위한 코드

FibonacciFun2.c

실행화면

return Fibo(n-1)+Fibo(n-2); //return Fibo(6)+Fibo(5);

에서 +연산자 왼편의 Fibo 함수 호출이 완료되어야 +연산자 오른편에 있는 Fibo함수 호출이 진행된다.

 

Fibonacci 재귀 순서도

Fibo 재귀 순서도 2

위 순서대로 재귀함수들이 실행된다 즉 return Fibo(n-1)+Fibo(n-2); //return Fibo(6)+Fibo(5);

에서 +연산자 왼편의 Fibo 함수 호출이 완료되어야 +연산자 오른편에 있는 Fibo함수 호출이 진행된다.