[C언어 연습문제]강좌 15. Calculate the Nth term(재귀 함수를 활용한 조건 계산)

재귀 함수 학습 - n번째 조건 계산 문제

학습(Study) & 목표(Objective)

재귀 함수를 배우는데 도움이 되는 문제를 풀어보겠습니다.

함수 내에서 자신을 호출하는 함수를 재귀함수라고 합니다. C 프로그래밍 언어에서는 재귀함수를 지원합니다. 하지만, 재귀함수를 사용하는 동안에 함수 종료 조건 중 하나는 주의 깊게 정해야 합니다. 안 그러면 무한루프에 빠져 프로그램이 비정상 종료되거나 잘못된 동작을 일으킵니다.

무한루프를 방지하기 위해 if - else 문(또는 유사한 접근)을 사용하면 하나의 분기는 재귀 호출을 하고, 다른 분기는 종료하거나 다른 동작을 할 수 있습니다.

void recurse()

{

...

recurse();    // recursive call

...

}

int main()

{

...

recurse();    // function call

...

}

과제(Task)

세트 S는 이전 3개 항의 합으로 이루어진 다음 항을 가지는 세트 S가 있습니다.

세트의 처음 3번째 항은 각각 a, b, c로 입력을 받습니다. 

재귀로 호출된 n번째 항을 출력합니다.

n번째 항은 아래와 같이 재귀 함수로 입력받습니다.

입력 형식(Input Format)

- 첫 줄에는 하나의 정수 n을 입력받습니다.

- 다음 줄에는 a, b, c 3개의 정수를 공백으로 분류하여 포함합니다.

제약 조건(Constraints)

출력 형식(Output Format)

세트 S(n)의 n번째 항을 출력한다.

입력 예제(Sample Input)

5

1 2 3

출력 예제(Sample Output)

11

아래의 순서대로 수행되어 답을 도출합니다.

1. S(1) = 1

2. S(2) - 2

3. S(3) = 3

4. S(4) = S(3) + S(2) + S(1)

5. S(5) = S(4) + S(3) + S(2)

3번의 단계를 지나고, 4번째 단계에서는 S(4) = 3 + 2 + 1 =6; 이 나오고, 2, 3, 4번째 값을 통해 S(5) = 6 + 3 + 2 = 11이 나옵니다. 따라서 값 11을 얻습니다.

주어진 코드

#include <stdio.h>
#include <stdlib.h>
//Complete the following function.
int find_nth_term(int n, int a, int b, int c)
{
  //Write your code here.
}
 
int main()
{
    int n, a, b, c;
  
    scanf("%d %d %d %d", &n, &a, &b, &c);
    int ans = find_nth_term(n, a, b, c);
 
    printf("%d", ans); 
    return 0;
}

답안 코드

int find_nth_term (int n, int a, int b, int c)
{
    if(n == 1) return a;
    if(n == 2) return b;
    if(n == 3) return c;
    return find_nth_term(n-1, a, b, c) + find_nth_term(n-2, a, b, c) + find_nth_term(n-3, a, b, c);
}

기본적인 조건으로 n = 1일 때는 a를 반환하고, n = 2일 때 b, n = 3일 때 c를 반환합니다.

재귀적인 경우는 n > 3일 때 조건입니다. S(n-1) + S(n-2) + S(n-3)를 반환해야 하겠죠.

각각의 재귀 호출은 n=1, n=2, n=3이 될 때까지 작아지면서 계산을 하게 됩니다.

프로그램은 그 후 호출 스택을 통해 재귀의 각 수준의 반환 값을 다시 전달하기 시작합니다.

n = 5, a = 5, b = 7, c = 8인 예제 Flow입니다. 호출되면 단계마다 위의 그림처럼 계산을 하고, return 하면서 올라가는 구조로 보시면 될 것 같습니다.

추가 답안 코드

#include <stdio.h>
#include <stdlib.h>
 
int find_nth_term(int n, int a, int b, int c)
{
    int nRet = a + b + c;
    if (n <= 4)
    {
        return nRet;
    }
    nRet = find_nth_term(n-1, nRet, b, c);
 
    return nRet;
}
 
int main()
{
    int n = 0, a = 0, b = 0, c = 0;
  
    scanf("%d %d %d %d", &n, &a, &b, &c);
 
    int ans = find_nth_term(n, a, b, c);
 
    printf("%d", ans);
    return 0;
}

좀 더 재귀를 활용한 방법입니다. 4와 같거나 작아질 때 결괏값을 반환하고, 그전에는 계속 한 단계씩 줄어들면서 합을 구해 조건을 만족시켜 나가는 방법이죠. 이 방법으로 구현을 했는데, 사람이 이해하기 쉽게 읽기에는 답안 코드가 더 가독성이 있을 것 같습니다. 식에 맞는 직관적인 return 반환문이 있으니까요.

재귀함수는 깊이(depth)가 계속 깊어지는 경우가 많으므로, 아무래도 같은 수준을 도는 반복문보다는 사람이 이해하기 어렵고, 조심해야 할 점도 많은 것 같습니다.

대신에 잘 활용하면 효율적인 코드 작성이 가능해지죠.

재귀함수로 구현 가능한 사례를 모아 reference를 만드는 것도 하나의 방법인 것 같습니다.