재귀 함수 개념
재귀 함수는 함수 안에서 자기 자신을 호출하는 함수이다.
아래 간단한 재귀 함수의 예제를 봅시다.
1. void Function (void)
2. {
3. printf ("Function Call \n") ;
4. Function( ) ;
5. }1 행에서 Function 함수를 선언 , 정의하고 있다.
4 행에서 자기 자신인 Function 함수를 호출하고 있다.
따라서 위 Function 함수는 재귀 함수이다.
또 다른 재귀 호출 함수의 예제를 봅시다.
재귀 함수 예제 01
3 행에서 river 함수 선언하고 있다.
7 행에서 river 함수 호출하고 있다.
12 행에서 재귀 함수를 정의하고 있다.
16 행에서 함수 내부에서 자기 자신을 다시 호출하고 있다.
위 예제의 실행 결과는 아래와 같다.
Han River
Han River
Han River
. . . .
12 행의 river 함수는 재귀 함수이다. 왜냐하면 16 행에서 자기 자신을 호출하고 있기 때문이다. 따라서 함수 값을 반환하기 전에 자신을 호출하는 문장으로 인하여 처음부터 다시 실행을 하게 된다.
그런데 이렇게 계속 자신을 호출하게 되면 함수가 끝나질 않게 된다. 따라서 이 반복을 끊어줄 조건이 필요하다. 즉 ,올바른 재귀 함수가 되기 위해선 탈출 조건이 있어야 한다. 탈출 조건이 있는 재귀 함수의 예를 봅시다
예제 02
3 행에서 Function 함수를 정의하고 있다.
5행에서 if 문을 이용하여 재귀 함수의 탈출 조건을 만들었다. 따라서 조건이 참이면 6 행의 return 문에 의하여 재귀의 과정이 종료가 된다.
9 행에서 보듯이 함수 내부에서 자기 자신을 호출하는 것으로 보아 Function 함수는 재귀 함수임을 알 수 있다.
위 예제의 실행 결과는 다음과 같다.
Function call ! 3
Function call ! 2
Function call ! 1
위 예제에서 Function 재귀 함수는 5 행의 탈출 조건에 의하여 매개 변수 number 가 0 을 전달 받으면 함수가 종료하게 되어 있다.
재귀 함수의 실행 순서
- 14 행에서 Function 함수에 3을 인자로 전달하며 호출한다.
- 매개 변수 3 은 5 행의 탈출 조건에 부합하지 않는다.
- 따라서 8 행에 의해 Function call ! 3 을 출력한다.
- 9 행에 의해서 number 값이 1이 감소된 2를 전달하며 다시 Function 함수를 호출한다.
- 매개 변수 2 는 5 행의 탈출 조건에 맞지 않는다.
- 다시 Function call ! 2 를 출력한다.
- 9 행에 의해서 number 값이 1이 감소된 1을 전달하며 다시 Function 함수를 호출한다.
- 매개 변수 1 은 5 행의 탈출 조건에 맞지 않는다.
- 따라서 8 행에 의해 Function call ! 1 을 출력한다.
- 9 행에 의해서 number 값이 1이 감소된 0 을 전달하며 다시 Function 함수를 호출한다.
- 매개 변수 0 은 탈출 조건을 만족 시킨다. 따라서 재귀 함수의 반복이 종료 된다.