[C] 재귀함수(Recursion)

눈으로 하는 코딩이 아닌! 직접 타이핑하는 코딩은 실력 향상에 엄청난 도움이 됩니다.

---

안녕하세요~! 정선생이예요. 이번에는 재귀함수를 배워볼꺼예요.

일단 재귀함수의 사전적 정의를 봐보죠!! 재귀란, 수학이나 컴퓨터 과학 등에서 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻한다. (출처바로가기)

음.. 마지막이 중요해요. 자기 자신을 재참조한다. 프로그래밍에서는 자기 자신을 재호출한다. 로 바꿔서 해석할 수 있어요. 이게 뭔소린지 예제소스를 보면서 알아가봐요!!

가장 많은 예시로 사용되는 코드는 계승(Factorial)이예요. 표시는 n! 로 합니다. 자세히 들어가면 수학시간이 되버리니까 구글링으로 정의를 알아보도록해요 ㅎㅎ 자 일단은, 3! = 1 x 2 x 3 이구요. 5! = 1 x 2 x 3 x 4 x 5 가 됩니다.

" 아하! n! 이란 1~n 까지를 곱한거구나. "

이해 가시나요?

1~n까지 1씩 증가하면서 곱한 값을 출력해주는거니까 반복문으로 해결 할 수가 있겠죠?

#include <stdio.h>

int main() {
    int n=10;
    int i, fact=1;
    for(i = 2; i <= n; i++)
        fact = fact * i;
    printf("10! = %d", fact);
    return 0;
}

출력 10! = 3628800

자 반복문으로 작성했으니 10!을 구하는 함수를 작성해봅시다.

#include <stdio.h>
int fact(int n){
    int i, result;
    result = 1;
    for(i = 2; i <=n) i++)
        result *= i;
    return result;
}

int main() {
    printf("10! = %d", fact(10));
    return 0;
}

이제 이 함수를 재귀함수로 바꿀수가 있는데요. 이게 쉽다고 단정을 짓기도 애매하고, 어렵다고 확정 짓기도 애매합니다.. 

일단 재귀함수란, 자기 자신을 계속 호출하는건데 어떤식으로 호출하는지 코드를 볼게요.

#include <stdio.h>
int fact(int n){
    if(n == 1)
        return 1;
    else
        return n * fact(n-1);
}

int main() {
    printf("10! = %d", fact(10));
    return 0;
}

코드는 생각보다 엄청 간결해졌어요.  fact함수는 매개변수로 정수형 변수 하나를 받네요.

맨 처음은 fact(10)

if에서는 false니까 넘어가겠죠?

그리고 return n * fact(n-1) 을 해주는데 현재 n은 10이죠?

그러면 fact(9)를 호출하겠네요. 그렇다면 return 10 * fact(9)

fact(9)에서는 9 * fact(8)

fact(8)에서는 8 * fact(7)

...

fact(2)에서는 2 * fact(1)

fact(1)에서는 if문의 true가 되니까 1을 리턴합니다.

자 그러면 계산된 값들을 역으로 올라가봅니다.

fact(1)은 1이니까 fact(2)에서는 2 * 1이 되요.

fact(3)에서는 3 * fact(2). 즉 3 * 2 * 1.

fact(4)는 4 * fact(3). 즉 4 * 3 * 2 * 1.

...

fact(9)는 9 * fact(8). 즉 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1.

fact(10)은 10 * fact(9). 

재귀함수는 여러 문제를 봐보면서 어떤 방식으로 동작하는지를 파악해야해요.

코드 자체를 외운다기보다는 공책 펴놓고 거기에서 n이 10일때, 9일때, 8일때, ... 각각의 n에 대해 함수가 어떻게 작동하는지를 디버깅 해보면 이해가 쉽게 될거예요. 컴퓨터 코딩이라고 손코딩이 중요하지 않은 것은 아니예요. 손코딩도 그만큼 중요합니다 ^.^

======================================== 5월 29일에 추가된 내용 ==========================================

현재 제가 작성 한 줄 알고 넘어갔던 변수의 유효범위와 관련된 게시글을 재귀함수 다음으로 읽어주시고 배열 파트로 넘어가시길 권장합니다.

죄송합니다 ( __ )

( 변수의 유효범위 게시글로 바로가기 )

게시글을 보시다가 궁금한 내용, 이게 맞나? 하는 내용, 이건 틀렸어!하는 내용들은 과감하게 댓글 달아주시면 감사하겠습니다.

이론적인 내용에 대한 궁금증은 검색을 통해 궁금증을 해결하는 것이 좋아요!!

실습적인 내용에 대한 궁금증은 최대한 생각을 해보고 검색을 하는 것이 좋아요!!