C 언어 / C++ 언어 제25강 재귀 함수 연습 (팩토리얼, 피보나치 수열, 2진수 변환)

 

이번 시간에는 코딩 문제에서 많이 쓰이는 기법 중에 하나인 '재귀 함수'에 대해서 익혀보겠습니다.

함수는 함수 안에서 자기 자신을 호출할 수 있습니다. 재귀는 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법입니다.

처음에는 좀 이상해 보이지만, 사실 재귀는 정말 효과적이고 흥미로운 프로그래밍 기법입니다. 3가지 예제를 통해서 재귀 함수에 대해서 익혀보도록 하겠습니다.

 

 

---

재귀 함수로 팩토리얼 구하기

팩토리얼의 정의는 n! = n * (n-1)! 입니다. (단, n이 0일땐 n!은 1)

위의 정의에선 n!을 정의하는데 (n-1)! 가 다시 사용된 것을 알 수 있습니다. 이를 코딩을 통해서 함수로 구현해보겠습니다.

 

#include <stdio.h>

long factorial(int n)
{
	printf("factorial(%d)\n", n);
	if (n <= 1) { return 1; }	//n이 1이 되면 1을 리턴
	else { return n * factorial(n - 1); }	//재귀로 n! = n * (n-1)! 구현
}	


void main() {
	int n;
	printf("n을 입력하세요 : ");	
	scanf("%d", &n);	//n을 입력받음
	printf("%d!은 %d입니다.", n, factorial(n));
}		//n과 n팩토리얼 출력

 

 

코딩을 이와 같이 간단하게 해줄 수 있습니다. 팩토리얼 함수를 재귀를 통해 구현해주었습니다.

그리고 메인 함수에서 팩토리얼함수를 호출해 사용해보았습니다.

실행해보겠습니다.

대표사진 삭제

사진 설명을 입력하세요.

이렇게 n으로 5를 입력해주니 5!은 120입니다가 출력되는 것을 볼 수 있습니다. 5! = 5 * 4 * 3* 2* 1 = 120

 

---

재귀 함수로 피보나치 수열의 항 구하기

피보나치 수열은 앞에 있는 두개의 항을 더해서 뒤의 숫자를 만드는 수열입니다.

순서대로 해보면 1, 1, 2, 3, 5, 8, 13, 21, ... 이렇게 수열이 진행됩니다.

이것 또한 재귀를 사용하면 아주 쉽게 구현할 수 있습니다.

 

#include <stdio.h>

long fibonacci(int n)
{
	if (n == 0) return 0;	//n이 0이 되면 0을 리턴
	if (n == 1) return 1;	//n이 1이 되면 1을 리턴
	return (fibonacci(n - 1) + fibonacci(n - 2));	// 재귀로 피보나치 수열 구현
}

void main() {
	int n;
	printf("n을 입력하세요 : ");
	scanf("%d", &n);	// n 입력받음
	printf("피보나치 수열 %d번째 항은 %d입니다.", n, fibonacci(n));	//출력
}
	

 

 

이와 같이 재귀를 사용하면 피보나치 수열도 쉽게 구현할 수 있습니다. 실행해보겠습니다.

대표사진 삭제

사진 설명을 입력하세요.

이렇게 7을 입력하니까 7번째 항인 13이 출력되는 것을 볼 수 있습니다.

 

 

 

---

재귀 함수로 10진수 2진수로 변환하기

이번엔 10진수의 수를 입력받아서 2진수로 바꿔주는 함수를 재귀로 표현해보겠습니다.

2진수는 10진수의 수를 2로 나눈 몫과 나머지를 계속해서 구해야 합니다. 이것을 재귀함수로 코딩해보면

 

#include <stdio.h>

void converter(int n)
{
	if (n > 0)
	{
		converter(n / 2);	//나눈 몫을 다시 불러서 반복 (재귀)
		printf(" %d ", n % 2);	// 나눈 나머지를 출력
	}
}

void main() {
	int n;
	printf("n을 입력하세요 : ");
	scanf("%d", &n);	// n 입력받음
	printf("n의 2진수 : ");
	converter(n);	//converter함수로 2진수 출력
}
	

 

 

이렇게 완전 간단하게 함수로 표현할 수가 있답니다. converter 함수를 만들어서 함수만 호출하면 n의 2진수를 출력할 수 있도록 코딩해주었습니다.

실행해보겠습니다.

대표사진 삭제

사진 설명을 입력하세요.

100을 입력했더니 정상적으로 2진수 1100100이 출력되는 것을 알 수 있습니다.

 

 

 

이처럼 재귀 함수를 잘 활용하면 어려워 보이는 문제도 쉽게 접근하고 해결할 수 있습니다.

하지만 재귀 함수는 반복적인 연습을 통해서 익혀야 합니다. 어려워 보이는 프로그래밍도 차근차근 하다 보면 금방 익숙해질 것입니다. 읽어주셔서 감사합니다.