재귀함수; 팩토리얼 계산, 피보나치 수열

오늘은 재귀 함수에 대해 정리해 볼 것이다. :-)

 

재귀 함수

 

요즘 기말고사 시즌이던데.. ^-^ 셤 공부 화이팅..!

1. 재귀함수 간단 정리
2. 팩토리얼 계산 함수
3. 피보나치 수열

 

재귀 함수(recursive function)는??

• 재귀적인 (Recursive) 관계를 지닌 문제를 해결하기 위해 사용하는 함수이다.
• 재귀 함수는 자기 자신을 호출하는 것이 특징이다.
• 재귀 함수는 무한반복될 수 있으므로 조심해서 프로그래밍 해야 한다.
• 재귀 함수 안에 자기자신을 호출하는 명령어가 두 개 이상이여도 된다. 
• 대표적인 예제로는 factorial과 fibonacci가 있다.

 

 

< 팩토리얼 (Factorial) >

예제로는 팩토리얼 함수를 만드는 것이 있다. 

참고) 팩토리얼이란? 1부터 어떤 양의 정수 n까지의 정수를 모두 곱한 것을 말하며 n!로 나타낸다. 이때, 0! = 1로 약속한다.

일단, 재귀 함수를 생각하지 않고 팩토리얼 함수를 만들어보자. 이 함수는 정수를 전달받아 정수 값을 반환하는 함수이다.

// 팩토리얼 함수
int factorial(int n) {	// 정수 n을 전달 받음
	int product = 1;	// 이 값들은 서로 곱해지기 때문에 초기화를 1로 해준다.
	for (int i = 1; i <= n; i++) product *= i;	// 1부터 n까지의 정수들의 곱을 계산
	return product;	// 결괏값 반환
}

그러면 이제 함수만을 이용해서 factorial을 계산해보자. 미지수 n으로 생각하려면 어려우니까 간단한 숫자 4를 넣어서 생각해보자.

즉 4! 의 경우를 예를 들어 생각해보자.

// factorial(4) 계산
   factorial(4) = 4 * foctorial(3)
		= 4 * (3 * factorial(2))
 		= 4 * (3 * (2 * factorial(1)))
		= 4 * (3 * (2 * (1 * factorial(0))))
 		= 4 * (3 * (2 * (1 * factorial(0))))
 		= 4 * (3 * (2 * (1 * 1)))
		= 4 * (3 * (2 * 1))
 		= 4 * (3 * 2)
 		= 4 * 6
	        = 24

위와 같이 함수를 쓸 수 있고 재귀 함수를 이용해서 팩토리얼 코드를 작성하면 다음과 같다.

// 재귀함수를 이용하여 factorial 함수 만들기
int factorial(int n) {
	if (n == 0)
		return 1;	// 0! = 1 로 약속
	else	// 0이 아닐경우 n에서 1을 빼준 n-1을 다시 함수에 넣어준다.
		return n * factorial(n - 1); // Recursive call 재귀적 호출
}

main 함수에 호출하여 팩토리얼 계산기를 사용해보자!

#pragma warning(disable:4996)
#include <stdio.h>
int factorial(int n) {
	if (n == 0)
		return 1;
	else
		return n * factorial(n - 1); // Recursive call
}
int main() {
	int n;
	printf("number? ");
	scanf("%d", &n);	// 계산할 양의 정수 n을 입력 받음
	printf("Factorial of %d is %d", n, factorial(n));
	return 0;
}

 

 

< 피보나치수열(Fibonacci Sequence) >

재귀 함수를 사용하여 피보나치수열을 계산해보자. 

참고) 피보나치 수열이란? 처음 두 항을 1과 1로 한 후, 그다음 항부터는 바로 앞의 두 개의 항을 더해 만드는 수열을 말한다. 그러므로 피보나치수열의 처음 몇 개의 항은 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ···

이 수열 순서대로 index와 짝지으면 다음과 같다.

피보나치 수열

그런데, 이렇게 하면 첫 번째 항이 index가 0일 때이므로 헷갈린다. 따라서 0번째 index에 0을 짝지어주면 다음과 같이 짝지어지고 덜 헷갈린다. 

피보나치 수열

이 표에 맞게 재귀 함수를 이용하여 피보나치 수를 계산하는 함수를 작성해보자.

// 피보나치 수를 계산하는 함수
int fib(int index){
	if (index == 0) // 첫 번째 항
		return 0;
    else if (index == 1) // 두 번째 항
		return 1;
	else // 반복되는 호출
		return fib(index - 1) + fib(index - 2);
}

피보나치 수를 계산하는 함수를 이용하여 사용자에게 항을 입력받고 그 항까지 수열을 출력해보는 프로그램을 만들어보자. 

#pragma warning(disable:4996)
#include <stdio.h>
// 피보나치 수를 계산하는 함수
int fib(int index)
{
	if (index == 0) // 첫 항
		return 0;
	else if (index == 1) // 두 번째 항
		return 1;
	else // 반복되는 호출
		return fib(index - 1) + fib(index - 2);
}
// 사용자에게 항을 입력 받고 그 항까지 수열을 출력하는 프로그램
int main() {
	int index;
	printf("index? ");
	scanf("%d", &index);	// 사용자에게 index 받기
	for (int i = 1; i <= index; i++) printf("%d ", fib(i));	// 첫항 (i=0)부터 사용자가 입력한 항(index)까지 피보나치 수열 출력
	return 0;
}