[자료구조] 함수의 재귀적 호출

<재귀함수의 기본적인 이해>

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

void Recursive(void){
     printf("Recursive call! \n");
     Recursive():
}

나도 처음에는 "어떻게 완료되지 않은 함수를 다시 호출하지?" 라고 생각했는데

함수가 호출되면 해당 함수의 복사본을 만들어서 실행하는 구조이기 때문에

​

Recursive 함수를 실행하는 중간에 다시 Recursive 함수가 호출되면, Recursive 함수의 복사본을

하나 더 만들어서 복사본을 실행한다

​

라고 생각하면 된다.

​

하지만 위의 예제는 Recursive함수에 '재귀의 탈출조건'이 없기 때문에 한번 호출되면 계속 호출되는 문제가 있다.

따라서 탈출의 조건을 추가해보자

 

#inckude <stdio.h>

void Recursive(int num){
     if(num <= 0) //재귀의 탈출 조건
           return; //재귀의 탈출!
     printf("Recursive call! %d \n", num);
     Recursive(num-1);
}
    
int main(void)
{
     Recursive(3);
     return 0;
}

이렇게 코드를 작성하면

메인 함수에서 Recursive함수를 호출하고 num을 3으로 초기화했기 때문에

Recursive 함수에 num=3을 해서 실행하면

printf까지 실행을 하고

Recursive(3-1)을 호출하고 또 거기에서 printf까지 실행하고 Recursive(2-1)을 호출하게 되는..

그런 구조이다!! 그래서 조건을 만족할 때 (num<=0)까지 재귀적으로 호출을 하게 되는 것이다.

 

<재귀함수의 디자인 사례>

재귀함수는 자료구조나 알고리즘의 어려운 문제를 단순화하는데 사용되는 중요한 무기이다.

재귀함수로 재귀적인 수학적 수식을 그대로 코드로 옮길 수 있다.

​

예를 들어서 팩토리얼(factorial) 값을 반환하는 함수를 재귀적으로 구현해보자.

​

n! = n × (n-1) × (n-2) × … × 2 × 1은 재귀적으로

​

n! = n × (n-1)! 으로 표현할 수 있다

​

함수로 표현하면

n팩토리얼 f(n)은

​

 

으로 나타낼 수 있다.

따라서 f(0)에 해당하는 0!이 1이 되므로 이것이 재귀함수의 탈출 조건이 된다.

​

인자로 전달된 정수의 팩토리얼 값을 반환하는 함수의 이름을 Factorial이라 할 때, n이 1이상인 경우의

수식 n × f(n-1)은

 

if(n >= 1)
     return n * Factorial(n-1);

로 표현할 수 있다.

그리고 n이 0인 경우의 결과값 1은

if(n == 0)
     return 1;

으로 표현할 수 있다

​

따라서 Factoria 함수에 0 이상의 값만 전달된다는 가정을 하면,

 

if(n == 0)
     return 1;
else
     return n * Factorial(n-1);

 

으로 하나의 if-else 문으로 묶을 수 있다.

 

#include <stdio.h>

int Factorial(int n) {
	if(n == 0)
		return 1;
	else
		return n * Factorial(n - 1);
}

int main(void) {
	printf("1! = %d\n", Factorial(1));
	printf("2! = %d\n", Factorial(2));
	printf("3! = %d\n", Factorial(3));
	printf("4! = %d\n", Factorial(4));
	printf("9! = %d\n", Factorial(9));

	return 0;
}

 

따라서 이렇게 수행하면 결과는

1! = 1

2! = 2

3! = 6

4! = 24

9! = 362880

으로 나온다