쉽지 않은 재귀함수의 이해

함수 부분에서 처음에 이해하기 어려운 부분이 이 재귀함수.

첨 봤을땐 욕 엄청 했다.

뭐 이런 아이가 다 있냐고 -_-

네X버 지식인에도 검색 해봤지만 속 시원하게 이해시키는 사람이 없었다.

결국 내가 시도한 방법은 "길 따라가보기"

이해력이 느린 나로썬 상당히 괜찮은 방법이었다.

재귀함수는 말 그대로 자기 자신을 호출하는 함수이다.

보통 반복문을 돌려서 쓰면 되지만 재귀함수를 굳이 쓰는 이유는

코드의 간결화 때문이다.

(사실 재귀함수를 사용하게 되면 속도는 많이 느려진다)

이 망할놈의 재귀함수.

조건이 있다.

첫번째는 반드시 끝나는 조건이 존재해야 한다는 것.

두번째는 계산 범위가 점점 줄어들어야 한다는 것.

뭔 소린지 모를 것이다. 나도 모르겠다.

일단 재귀함수를 사용한 팩토리얼 계산 코드를 살펴보자.

#include <stdio.h>

long fact(int n)

{

if (n == 0) return 1;   // 끝 조건

else

return n * fact(n - 1);   // 함수를 계속해서 호출하는 부분

}

int main()

{

int n;

printf("자연수");

scanf("%d", &n);

printf("fact(%d) = %d입니다\n", n, fact(n));

return 0;

}

자연수 하나를 입력받으면 팩토리얼 계산값을 출력해주는 프로그램이다.

코드는 상당히 간단하다. 그러나 처음 봤을 땐 이해하기가 좀 어렵다.

일단 프로그램이 실행되면 메인이 실행된다.

자연수 3을 입력받으면 fact() 함수에 인수를 전달하여 재귀함수 호출이 시작된다.

이 때, n = 0 이면 1을 반환한다. n = 3 이므로 else 구문이 실행된다.

n * fact(n-1)을 반환하라고 되어 있다. n = 3 이므로 3 * fact(2) 가 된다.

그럼 여기서 다시 fact(2)를 호출하게 된다. 이게 바로 재귀함수이다.

fact(3)을 계산하기 위해 fact(2)를 호출했고 그러면 2 * fact(1)

그러면 또 fact(1)을 호출하게 된다.

fact(1)은 또 fact(0)을 호출, fact(0)이면 반환값이 1이 되므로

여기서 다시 거슬러 올라가는 것이다.

fact(0)일때 반환값 1은 fact(1)로 반환되어 1 * fact(0) 이 계산되어 지고

1이 된다.

이 1은 다시 fact(2)로 반환되어 2 * fact(1) 을 계산하므로 반환값은 2.

이 2는 다시 fact(3)으로 반환되어 3 * fact(2) 가 되므로 최종 결과값은 6이 된다.

여기서 끝 조건이 필요하고 점점 계산범위가 줄어들어야 하는 이유가 설명이 된다.

이걸 그림으로 나타내면

이해는 겨우 했으나 뭐니뭐니해도 중요한건 실제로 다른 프로그램을 짤때에

적용을 시키는 것이겠지.

코딩에 뛰어난 사람들은 빨리 이해하겠지만 난 그렇지 못해서 한참을 보고 파헤쳐야 이해하니

난 쉬면 안되겠다.