([C언어] 19강) 재귀함수

 

이번 강의에서는 다소 늦은 감이 있지만

 

재귀함수에 대해서 배워볼까 하는데요

 

재귀함수란

 

"함수 내에서 자기 자신을 호출하는 함수"

 

라고 외워주시면 되겠습니다

 

재귀함수의 생김새를 한 번 볼까요??

 

 

int loopFunction()
{
    loopFunction();
}

이런 형식의 함수를 재귀함수 라고 볼 수 있습니다.

 

하지만, 이 코드에서 loopFunction함수를 사용하려 한다면

 

어떻게 될까요?

 

지 혼자 뭘 막 하다가

 

에러가 나버립니다 (-1073741571코드로 종료, 정상이라면 0으로 종료되어야함);

 

왤까요??

 

방금 짠 코드는 while문에 인자로 1을 넘겨준것과 같습니다

 

"무한루프" 라고하죠 무한하게 계속 실행되다가 "스택오버플로우"라는 오류가 나며 종료됩니다.

 

더이상 실행할수없을만큼 스택이 다 쌓였다 라는 말이죠.

 

이 때문에 재귀함수에는 탈출 조건을 적절히 짜야합니다.

 

#include <stdio.h>

int loopFunction(int n)
{
    printf("%d",n);
    if(n >= 5)
        return 0;
    loopFunction(n + 1);
}

int main()
{
    loopFunction(0);
}

이 코드의 실행 결과는 무엇일까요?

 

012345라고 나오네요 왤까요?

 

main함수에서 loopFunction함수에 0을 보내주고

 

loopFunction함수에서는 n을 출력한후 자기 자신을 n + 1한 값으로 계속 호출합니다

 

그럼 차례대로 0 1 2 3 4 5 순서대로 가다가 5가 되는 순간 if문에 걸려

 

자기 자신을 더이상 호출하지않고 return 해버립니다. 이해 되셨나요?

 

#include <stdio.h>

int loopFunction(int n)
{
    printf("%d",n);
    if(n >= 5)
        return 0;
    loopFunction(n + 1);
    printf("%d",n);
}

int main()
{
    loopFunction(0);
}

그럼 이번 코드의 실행 결과는 어떨까요? 실행해보죠!

 

어라? 왜 012345012345가 아니라 01234543210이 나오죠?

 

이번에는 조금 복잡하므로 잘 따라와 보세요 설명하겠습니다

 

 

 

main함수에서 loopFunction에 0을 보냅니다 따라서 n은 0입니다.

 

loopFunction함수에서 n을 출력합니다. 화면에 0이 출력됩니다.

 

loopFunction이 자기 자신을 호출하고 인자로는 n + 1 즉, 1을 넘겨줍니다 따라서 n은 1입니다.

주의! 여기서 n이 0일때의 함수는 아직 종료되지 않고 n이 1일때의 함수가 끝나기를 기다립니다!

 

loopFunction함수에서 n을 출력합니다. 화면에 1이 출력됩니다.

 

loopFunction이 자기 자신을 호출하고 인자로는 n + 1 즉, 2을 넘겨줍니다 따라서 n은 2입니다.

주의! 여기서 n이 1일때의 함수는 아직 종료되지 않고 n이 2일때의 함수가 끝나기를 기다립니다!

 

loopFunction함수에서 n을 출력합니다. 화면에 2가 출력됩니다.

 

이를 반복하다 결국 n이 5가되고 화면에 5가 출력 된 후 함수가 종료 됩니다.

 

다시 n이 4일때의 함수로 돌아가서 화면에 4가 출력된후 함수가 종료 됩니다.

 

다시 n이 3일때의 함수로 돌아가서 화면에 3이 출력된 후 함수가 종료됩니다.

 

이렇게 반복하다 n이 0일때의 함수까지 모두 종료되고 프로그램이 종료됩니다

 

 

 

조금 어렵죠? 그래도 열심히 공부해보세요!

 

 

이번엔 피보나치 수열을 재귀함수로 만들어볼까요?

 

피보나치 수열이란 0과  1로 시작해서

 

0, 1, 1, 2, 3, 5, 8, 13, 21, 23

이런식으로 앞의 두 숫자를 더한수가 현재의 수가되는 수열입니다

 

0, 1, ( 0 + 1 = 1), (1 + 1 = 2), (2 + 1 = 3)

이런식으로 말이죠!

 

그럼 코드는 어떻게 짜야할까요?

#include <stdio.h>

int fibo(int num);

int main(void){
    int i;
    for(i = 0 ; i < 20 ; i++ ){
       printf("%d " , fibo(i));
    }
    printf("\n\n");
    return 0;
}

int fibo(int num){
    if(num == 0)
    {
        return 0;
    }
    else if(num == 1)
    {
        return 1;
    }
    else
    {
        return fibo(num-1) + fibo(num-2);
    }
}

이렇게 짜면 20번째까지의 피보나치 수열이 출력되겠네요!

 

fibo함수만 해석해보자면

 

num이 0이면 0, 1이면 1을 리턴해주고

 

2면 fibo(num - 1) + fibo(num - 2) 이므로 fibo(1)과 fibo(0)의 결과를 더해주므로 1이 반환됩니다.

 

3이라면 fibo(num - 1) + fibo(num - 2) 이므로 fibo(2)와 fibo(1)의 결과를 더해주므로 2가 반환됩니다.

 

이해 되셨나요?

 

재귀함수 게임개발에서 가끔 쓰이는 경우가 있으니 외워두시는게 좋을겁니다~

 

이상 마치겠습니다! 다음 강좌에서 뵈는걸로해요!