[C언어_15] C언어 문제 풀이 #5

안녕하세요.

 

이번 시간에는 재귀함수를 이용하는 문제를 풀어보려고 합니다.

 

| 지난 강좌 Review

swdoodle.tistory.com/19

[C언어_14] 재귀함수의 개념과 공부하는 이유

지난시간에는 재귀함수의 개념과 공부하는 이유에 대해 살펴보았습니다.

 

이번 시간에는 재귀함수를 좀더 활용한 문제를 살펴보겠습니다.

| 피보나치 수열

여러분은 피보나치 수열에 대해 알고 계신가요?

 

피보나치 수열을은 아래와 같이

 

처음 두 항을 0과 1로 한 후, 그 다음 항부터는 바로 앞의 두 개의 항을 더해 만드는 수열을 말합니다.

 

흔히들 황금비라고 이야기를 하죠.

 

 

피보나치 수열을 이용한 황금비

 

 

 

 

우리는 이 피보나치 수열을 재귀함수를 통해 만들어 볼 것입니다.

 

| C언어 문제

먼저 자연수 N을 입력받습니다. ( N > 2 )

 

그리고 피보나치 수열의 N번째 값을 구하는 함수를 만들어 봅시다.

 

| 문제 풀이

먼저 사용자로부터 값을 입력받아야 합니다.

 

int N;

printf("Insert Number : ");

scanf("%d", &N);

 

그리고 함수를 만들어야 하는데,

 

함수는 사용자로부터 N을 입력받는 것이기 때문에,

 

int fib(int N);

다음과 같이 프로토타입을 설정하도록 하겠습니다.

 

| 함수 만들기

우리는 함수 fib를 만들어야 합니다.

 

맨 처음에 피보나치 수열의 정의에서 첫 번째와 두 번째 항을 각각 0과 1로 정하였습니다.

 

즉 맨 처음 두 수만 안다면 우리는 피보나치 수열을 만들 수 있습니다.

 

컴퓨터도 똑같습니다.

 

맨 처음 두 수의 값을 정해준다면 피보나치 수열을 만들 수 있습니다.

 

즉 맨 처음 두 수의 조건이 이전 재귀함수시간에서 배운 Termination Step 입니다.

 

int fibo(int N){
	
    if(N < 2) //첫 번째 항과 두 번째 항일때
    	return N; //각각 0과 1을 리턴
}

위의 함수를 확인하면 이해가 빠를것입니다.

 

조건문을 통해 첫 번째 항과 두 번째 항을 각각 0과 1로 설정해주었습니다.

 

그리고 피보나치 수열은 앞의 두 항의 합으로 이루어진 수열이기 때문에

 

재귀 함수를 이용하여

 

현재 항의 앞 두 항의 값의 합을 리턴해주면 됩니다.

 

즉 다음과 같이 만들어주면 됩니다.

 

int fib(int N){
	
    if(N < 2) //첫 번째 항과 두 번째 항일때
    	return N; //각각 0과 1을 리턴
    else	//그렇지 않으면
	return fib(N - 1) + fib(N - 2);	//앞 두항의 합을 리턴
}

 

위의 함수는 일반항을 활용한 것과 같습니다.

 

 

 

https://aerocode.net/129

즉 fib(5) = fib(4) + fib(3) 이기 때문에 앞 두항의 합을 위와 같이 리턴한 것입니다.

 

그리고 컴퓨터는 fib(4)나 fib(3)이 무엇인지 모르기 때문에 함수를 다시 실행합니다.

 

작동 방식은 아래의 그림을 참고하시면 더 쉽게 이해가 갈것입니다.

 

 

https://aerocode.net/129

 

| 마무리

이번시간에는 재귀함수를 이용한 피보나치 수열 만들기를 해보았습니다.

 

재귀함수에 대한 이해도가 위 문제를 통해 높아지셨기를 바랍니다.

 

감사합니다.