08. 재귀 함수

Q. 1부터 N까지의 정수를 덧셈하는 프로그램을 작성해 보세요.

---

위의 문제를 해결하기 위해서는 다양한 방법으로 프로그램을 작성할 수 있다.

 

1. 수학 공식을 이용한 프로그램 작성

#include <stdio.h>

int main()
{
    int i, n, sum = 0;
    
    printf("N값을 입력해주세요 : ");
    scanf("%d", &n);

    sum = (n*(n+1))/2;
    printf("%d", sum);

    return 0;
}

등차수열의 공식을 이용하여 n까지의 합을 구할 수 있다.

 

2. 반복문을 이용한 프로그램 작성

#include <stdio.h>

int main()
{
    int i, n, sum = 0;
    
    printf("N값을 입력해주세요 : ");
    scanf("%d", &n);

    for(i = 1; i<=n; i++)
        sum += i;
        
    printf("%d", sum);

    return 0;
}

for나 while 반복구문을 이용하여 n까지의 합을 구할 수 있다.

 

3. 재귀 함수를 이용한 프로그램 작성

재귀 함수란 함수 내부에서 자기 자신을 호출하는 함수를 의미한다. 이러한 재귀 함수는 특정한 작업을 반복적으로 수행할 때 유용하게 사용된다.

아래는 재귀함수를 이용한 1부터 N까지의 합을 구하는 프로그램이다.

#include <stdio.h>

int n_sum(int n){
    if (n == 1) return 1;
    return n + n_sum(n-1);
}

int main()
{
    int n;
    
    printf("N값을 입력해주세요 : ");
    scanf("%d", &n);
    
    printf("%d", n_sum(n));

    return 0;
}

n이 1이라면 1을 반환하고 1보다 크다면 n을 더하고 n-1을 매개변수로 하여 함수를 재호출 한다.

만약 종료 조건이 없다면 함수는 무한히 호출되므로 스택 오버플로우가 발생할 수 있다.

 

그럼 반복문이 있는데 굳이 재귀함수를 사용하는 이유는 무엇일까?

 1. 반복문에 비해 코드가 간결하고 함수 내부에서 스택을 이용하기 때문에 복잡한 변수 선언이 필요 없다.

 2. 재귀함수를 이용하면 자연스러운 문제 해결이 가능하다. (추후 알아보도록 하자)

 3. 함수 호출은 스택 프레임에 저장되므로, 어디서 오류가 발생하는지 쉽게 파악할 수 있다.

 4. 재귀함수를 이용하면 다양한 알고리즘을 구현할 수 있다. (추후 알아보도록 하자)

 

재귀함수에는 다양한 장점이 존재한다. 하지만 재귀함수를 사용할 때 주의점도 존재한다.

 1. 종료 조건을 꼭 만족시켜야 한다.

 2. 반복문보다 스택을 많이 사용하므로 크기 제한이 되는 경우가 있을 수 있다.

 

재귀함수를 공부하기 위해서는 이전과 같은 이론적인 접근보다는 직접 문제를 재귀함수로 작성하여 해결해 보는 것이 가장 빠른 공부 방법이라고 생각한다. 아래 문제들을 직접 재귀함수를 이용한 프로그램으로 작성해 보면서 공부해 보도록 하자.

 1. 팩토리얼 계산

  주어진 수의 팩토리얼을 계산하는 함수를 재귀적으로 구현해 보세요.

  n값을 입력하면 n! 을 계산하도록 구현하세요.

 2. 피보나치수열

  주어진 인덱스에 해당하는 피보나치수열 값을 재귀적으로 계산하는 함수를 구현해 보세요.

  n값을 입력하면 피보나치수열에서 n번째에 해당하는 값을 계산하도록 구현하세요

 3. 하노이의 탑

  세 개의 기둥과 n개의 원판으로 이루어진 게임이다.

  각 원판은 크기가 다르며, 큰 원판이 작은 원판 위에 올려지지 않도록 옮겨야 한다.

  재귀 함수를 이용하여 하노이의 탑 문제를 해결하는 함수를 구현해 보세요

 4. 이진 검색

  주어진 정렬된 배열에서 특정 값의 인덱스를 찾는 이진 검색 알고리즘을 재귀적으로 구현해 보세요.

 

 이외에도 다양한 문제들이 있으니 직접 프로그램을 작성해 보고 원리를 파악하여 재귀함수에 대해 공부해 보도록 하자.