왜 포스팅을 하게 되었는가?
사실 재귀함수라는 부분이 개인적으로 정말 와닿지 않는 부분이었는데, 결국 익숙해지려면 여러 코드를 보고 익히는 것이 최고라고 생각했습니다. 그래서 인프런의 영리한 프로그래밍을 위한 알고리즘 강좌의 코드를 C로 재작성했습니다.
영리한 프로그래밍을 위한 알고리즘 강좌 - 인프런
영리하게 프로그래밍을 할 수 있기 위한 기본 소양인 '알고리즘' 을 배우고 응용하는 방법을 배웁니다. 초급 알고리즘 알고리즘 온라인 강의 프로그래밍을 위한 알고리즘 강좌
www.inflearn.com
재귀함수
간단히 말해서 재귀함수란 자기 자신을 호출하는 함수이다.
void foo()
{
...
foo();
...
}위 코드처럼 자기 자신을 호출하는 꼴을 가진 함수를 재귀함수라고 할 수 있다. 생김새로는 그렇게 어렵지 않게 생겼으니 겁먹지 말고 계속 보자.
재귀함수를 어떻게 사용할 수 있을까?
// 코드1
#include <stdio.h>
void foo()
{
printf("재귀함수입니다.\n");
foo();
}
int main()
{
foo();
}이런 식으로 코드를 작성했을 때 어떠한 결과가 나올까?
코드를 실행시켰을 때 위와 같이 재귀함수입니다가 무한정 반복되는 현상을 볼 수 있는데, 이렇게 되는 절차는 다음과 같다.
1. main에서 foo()함수를 실행시킨다.
2. foo함수에서 print문을 수행한다.
3. foo()함수에서 foo()함수(자기자신)을 호출한다.
4. 그러면 또 foo함수가 실행되어 print문을 수행하고 또 foo()함수를 실행시킨다.
...
위의 과정을 계속 반복하다보니 무한 루프에 빠지게 된다.
그러면 어떻게 재귀함수가 무한루프를 돌지 않게 만들 수 있을까?
재귀함수를 끝내는 법
재귀 함수에서는 두 가지의 조건을 만족하면 재귀 함수가 종료될 수 있다. (올바르게 작성했다는 가정 하에)
1. Base Case : recusion에 빠지지 않는 조건
2. Recursive Case : recursion을 반복하다 보면 base case로 수렴할 수 있어야 함.
이번 예시 코드를 보자.
//코드2
#include <stdio.h>
void foo(int n)
{
if (n <= 0) {
return;
}
else {
printf("재귀함수입니다.\n");
foo(n - 1);
}
}
int main()
{
int n = 4;
foo(n);
}
위의 결과에서는 재귀함수입니다를 5번 출력하고 종료한 모습을 확인할 수 있다. 이 결과가 어떻게 도출되었는지 순서를 생각해보자. 그리고 foo에 매개변수가 들어가는데, 호출될 때마다 숫자가 달라지는 것을 알기위해 매개변수에 숫자를 표시할 것이다.
1. main에서 foo(4)를 호출함.
2. foo(4)에서는 n(4)이 0보다 크거나 같지 않으니 else문이 실행되어 1번째 print후 foo(3)을 호출한다.
3. foo(3)에서는 ... 실행되어 2번째 print후 foo(2)를 호출한다.
4. foo(2)에서는 ... 실행되어 3번째 print후 foo(1)을 호출한다.
5. foo(1)에서는 ... 실행되어 4번째 print후 foo(0)을 호출한다.
// 총 4번의 print가 실행됨.
----------------------------------
여기서 중요함
----------------------------------
6. foo(0)에서는 n(0)이 0보다 크거나 같으니 if문 내용이 실행되어 return이 된다. 이를 통해 foo(0)가 종료된다.
7. foo(0)을 호출했던 foo(1)로 돌아간 뒤, foo(0)을 호출했던 foo(1)함수가 끝난다.
8. foo(1)을 호출했던 foo(2)로 돌아간 뒤, foo(1)을 호출했던 foo(2)함수가 끝난다.
9. foo(2)을 호출했던 foo(3)로 돌아간 뒤, foo(2)을 호출했던 foo(3)함수가 끝난다.
10. foo(3)을 호출했던 foo(4)로 돌아간 뒤, foo(3)을 호출했던 foo(4)함수가 끝난다.
11. 마지막으로 foo(4)를 호출했던 main함수가 종료되고, 프로그램이 끝난다.
재귀함수는 처음부터 끝까지 어떻게 호출되고 끝나는지 순서를 제대로 알아야 되는데, 특히 print문이 4번 수행된 것을 보고 귀찮아서 생각을 이어서 안할 수 있기에 순서 6번부터 중요하다고 강조했다. 호출이 어떻게 종료되는지도 제대로 알아야 한다.
//코드2
#include <stdio.h>
void foo(int n)
{
if (n <= 0) {
return;
}
else {
printf("재귀함수입니다.\n");
foo(n - 1);
}
}
int main()
{
int n = 4;
foo(n);
}다시 돌아와서, 코드2에서 무엇이 "Base Case"이고 "Recursive Case"인가?
if (n <= 0) { //Base Case
return;
}
else { //Recursive Case
printf("재귀함수입니다.\n");
foo(n - 1);
}답은 위 코드인데, if ( n<=0 )가 Base Case이고, else의 foo(n - 1)이 Recursive Case이다. 그 이유는 n <= 0 을 통해 재귀를 빠져나올 수 있는 조건이 설정되었기 때문에 이 부분이 Base case이고, foo(n-1)으로 계속 자기 자신을 호출하지만 매개변수의 값이 지속적으로 바뀌면서 결국 Base case로 수렴하기 때문에 Recursive Case라고 할 수 있다.
이제부터는 재귀함수로 작성할 수 있는 여러 가지 예시를 보겠다.
재귀함수의 분석법
// 1~n까지의 합
#include <stdio.h>
int sum(int n)
{
if (n == 0)
return 0;
else
return n + sum(n - 1);
}
int main()
{
int recursum = sum(4);
printf("%d", recursum);
return 0;
}위 코드로 재귀함수의 코드가 맞게 작성되었는지 그리고 어떠한 개념을 가지고 봐야하는지 간략히 설명해보겠다.
1. 손으로 직접 그려서 확인하기.
위 사진처럼 손으로 그려서 확인할 수 있다. 그러나 재귀함수에서 호출코드가 많아질수록 복잡한 구조를 띄기 때문에 복잡해질수록 귀찮아진다는 단점이 있다. 그래서 적당한 매개변수 크기를 잡고 그림을 그리는 것을 추천한다.
사실 이정도면 간단한편
2. 귀납적으로 생각하기
- 0까지의 합은? : 0
- 1까지의 합은? : 1
- 2까지의 합은? : 3
...
즉, 0~n까지의 합을 제대로 구한다고 생각할 수 있다.
3. 재귀함수를 보는 개념
else
return n + sum(n - 1);0~n까지의 합은 n에 0~n-1까지의 합을 더한 것과 같다. 다시 말하자면 n + sum(n - 1)은 n에 sum(n - 1)을 통해 구한 0~n-1까지의 합을 더한 것이다.
정리하자면
1. n이 0일 때는 합은 0이라는 경우가 맞는지 확인.
2. sum(n-1)이 제대로 결과값을 반환한다는 가정이 맞는지 확인.
3. 그리고 코드를 살펴보면 재귀함수를 조금 더 쉽게 해석할 수 있을 것이다.
재귀함수로 작성한 예시들
1. 팩토리얼
#include <stdio.h>
int fact(int n)
{
if (n == 1)
return 1;
else
return n * fact(n - 1); //n에 n-1팩토리얼의 값을 곱하면 n!일 것이다.
}
int main()
{
int result = fact(5);
printf("%d", result);
return 0;
}
2. 제곱 값 구하기
#include <stdio.h>
int exponent(int x, int n)
{
if (n == 0)
return 1;
else
return x * exponent(x, n - 1); // X에 X^n-1 까지의 값을 곱하면 X^n의 값일 것.
}
int main()
{
int result = exponent(2, 3);
printf("%d", result);
return 0;
}
3. 피보나치
#include <stdio.h>
int fibo(int n)
{
if (n < 2) {
return n;
}
else {
return fibo(n - 1) + fibo(n - 2);
}
}
int main()
{
int result = fibo(6);
printf("%d", result);
return 0;
}
| 순서 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 값 | 0 | 1 | 1 | 2 | 3 | 5 | 8 |
피보나치수 = fibo(n-1) + fibo(n-2)
=> 피보나치 n-1까지의 합과 피보나치 n-2까지의 합을 더하면 다음 피보나치의 값이 나옴.