재귀함수(recursive function) - 정보올림피아드 문제 풀이

C 언어를 처음 배우는 사람들이 어려워하고 잘 이해하지 못하는 것중에 하나가 포인터(Pointer)와 함께 재귀함수(recursive function)입니다. C언어의 재귀함수는 단순하게 함수 내부에서 자신을 호출하는 것을 의미합니다. 그렇지만 프로그래밍 영역에서 많이 사용하는 개념이니만큼 올림피아드에서도 출제 빈도가 높습니다. 일단 제 아들이 질문한 문제를 먼저 만나보도록 하겠습니다.

이런 문제는 프로그램을 읽는 능력을 알아보기 위한 것으로 실제 업무 영역에서도 프로그래밍 능력은 이러한 프로그램 읽기 능력과 비례한다고 해도 과언이 아닙니다. 재귀함수를 대할 때 가장 유념해야 할 것은 변수의 영향 범위(Scope)입니다. C언어는 함수 내부에 선언한 변수는 지역(Local) 변수로 다른 함수에서는 전혀 참조할 수 없습니다. 반면에 함수 외부에 선언한 변수는 전역 변수로 모든 함수에서 참조할 수 있습니다. 위의 문제에서 함수 파라미터인 "int n"의 Scope는 어떻게 될까요? 이러한 함수 파라미터(parameter) 또한 지역 변수로 다른 함수에서는 전혀 참조할 수 없습니다. 그리고 재귀함수는 자신을 호출한다고 하지만 파라미터를 비롯한 지역변수가 서로 다르게 취급되는 전혀 다른 함수를 호출한다고 생각하면 됩니다. 프로그램을 보고 수학의 어떤 수열을 떠올리고 식에 대입해서 답을 빨리 찾는 분도 계시겠지만 단순하게 값을 하나씩 대입하는 것이 정도일 수 있습니다.

C언어에서 함수 호출은 스택(Stack)을 사용하므로 스택에 대한 개념을 먼저 단순하게 설명하겠습니다. 스택은 LIFO(Last In First Out) 방식의 데이터 구조로 맨 마지막에 들어간 것이 먼저 나오는 형태입니다. A, B, C를 스택에 차례대로 집어넣은(PUSH) 다음 데이터를 인출(POP) 하면 C, B, A 순으로 데이터를 가져오는 것입니다. 맨 마지막에 입력된 데이터 즉, 다음 인출시 돌려줄 위치를 가지고 있는 것을 스택 포인터라 하고 함수 호출 과정에서 사용하는 스택을 콜 스택(Call Stack)이라 부릅니다. 예전에 컴퓨터 용량이 작을 때는 프로그램이 조금 크거나 재귀 호출이 길어지면 "Stack Overflow"라는 에러를 내면서 프로그램이 죽는 현상이 발생하곤 했었지요.

위 문제에서 n에 10을 대입하면 return f(9) - f(8) + f(7) * 2 가 됩니다. n을 바꾸어서 적용하면 다음과 같습니다.

• 10 : return f(9) - f(8) + f(7) * 2
• 9 : return f(8) - f(7) + f(6) * 2
• 8 : return f(7) - f(6) + f(5) * 2
• 7 : return f(6) - f(5) + f(4) * 2
• 6 : return f(5) - f(4) + f(3) * 2
• 5 : return f(4) - f(3) + 2 * 2
• 4 : return f(3) - 2 + 1 * 2
• 3 : return 2 - 1 + 0 * 2

n이 3보다 작을 때는 재귀호출이 일어나지 않으므로(재귀 함수를 만들때는 이와같이 반드시 종료점이 있어야 합니다) 이제 거꾸로 계산해 나갑니다. 계산 할때 연산자의 우선 순위를 주의하세요(괄호>단항연산자>곱셈/나눗셈>덧셈/뺼셈)

• 3 : 1
• 4 : 1 - 2 + 1 * 2 = 1
• 5 : 1 - 1 + 2 * 2 = 4
• 6 : 4 - 1 + 1 * 2 = 5
• 7 : 5 - 4 + 1 * 2 = 3
• 8 : 3 - 5 + 4 * 2 = 6
• 9 : 6 - 3 + 5 * 2 = 13
• 10 : 13 - 6 + 3 * 2 = 13

고로 정답은 13입니다.

위의 함수 호출 과정을 그림으로 나타내면 아래와 같습니다.

워낙 호출이 많아서 n이 8일때를 그림으로 나타낸 것인데, 초록색은 재귀 호출이 일어난 부분이고 파란색은 단순 호출을 의미 합니다. 콜 스택에 쌓아가며(PUSH) 함수를 호출하고 함수 결과를 가져오면서(POP) 결과를 계산해 갑니다. n 값을 8로 해서 함수를 호출하면 3을 만날때 까지 f(n-1)부분에 대하여 콜 스택에 쌓아가면서 계속 재귀 호출합니다. n이 3일 때는 재귀 호출없이 함수 호출 값을 바로 리턴하므로 f(4) 작업중 f(n-1) 작업인 f(3) 결과값을 리턴하면 f(4) 작업은 완료되어 콜 스택에서 이전에 작업하던 f(5)로 넘어가고 f(5)의 다음 작업 f(n-2)인 f(3)을 스택에 쌓고 호출하여 값을 계산합니다. f(5) 작업중 f(n-3)은 그냥 값을 리턴하므로 계산 결과를 리턴하여 f(6)작업으로 돌아가고 f(6) 작업중 f(n-2)인 f(4)를 스택에 넣고 다시 호출하는 방식으로 진행하는 것입니다.

그동안 정보 올림피아드에서 출제되었던 재귀 호출 관련 문제를 종합적으로 풀어보시기 바랍니다.

1. 다음은 1부터 자연수 N까지 합을 구하는 재귀함수(recursive function)를 구현한 것이다. 빈 칸("____")에 알맞은 구문은?

int Sum( int N )
{
    if ( N == 1 ) return 1;
    else return "________" ;
}

① N + Sum(N) ② (N - 1) + Sum(N) ③ N + Sum(N - 1) ④ (N - 1) + Sum(N - 1) ⑤ 1 + Sum(N - 1)

2. 재귀함수(recursive function) f()가 다음과 같이 정의되었을 때, f(99)의 값은 얼마인가?

int f(int n) {
    if (n > 100) 
        return n - 10;
    else
        return f(f(n + 11));
}

① 90 ② 91 ③ 99 ④ 100 ⑤ 101

3. 영어 단어 “madam”이나 “radar”처럼 앞에서 뒤로 읽는 것이나 뒤에서 앞으로 읽는 것이 동일한 단어를 회문(palindrome)이라고 한다. 주어진 문자열이 회문인지를 판별하는 재귀함수 isPal을 다음과 같이 정의하였다. 재귀함수 isPal은 주어진 문자열이 회문인 경우에는 1을 리턴하고 그렇지 않은 경우에는 0을 리턴한다. 이 함수를 이용하여 스트링  “madam”이 회문인지를 검사하기 위해서는 isPal(“madam”, 0, 4); 와 같이 호출하는데, 첫 번째 인자는 검사하고자 하는 문자열이며, 두 번째는 정수 0이고, 세 번째는 첫 번째 문자열의 길이에서 1을 뺀 값이다. ㉠, ㉡에 들어갈 내용으로 각각 알맞은 것은?

int isPal(char s[], int st, int en) {
    if ( ㉠ ) 
        return 1;
    else if ( ㉡ )
        return 0;
    else
        return isPal(s, st + 1, en - 1);
}

① ㉠ : s[st] == s[en] ㉡ : s[st] != s[en]  ② ㉠ : s[st] == s[en] ㉡ : en <= st + 1

③ ㉠ : s[st] == s[en] ㉡ : en <= st       ④ ㉠ : en <= st + 1 ㉡ : s[st] != s[en]

⑤ ㉠ : en <= st ㉡ : s[st] != s[en]

[4-5] 아래와 같은 함수 f가 있다고 하자.

int f(int a, int b){
    if (a <= 0)
        return b;
    else
        return f(a - 1, b * 2) + b;
}

4. f(8, 2)의 값은 무엇인가?

    ① 510 ② 512 ③ 1022 ④ 1023 ⑤ 1024

5. 함수 f를 재귀 호출(recursive call)을 사용하지 않도록 다음과 같이 수정하였다. ㉠, ㉡에 들어갈 내용으로 각각 알맞은 것은?

int f(int a, int b){
    int sum;
    sum = ㉠ ;
    while (a > 0) {
        a--;
        sum = sum +  ㉡;
        b = b * 2;
    }
    return sum;
}

① ㉠ : 0  ㉡ : b  ② ㉠ : 0 ㉡ : b * 2  ③ ㉠ : b  ㉡ : b

④ ㉠ : b ㉡ : b * 2  ⑤ ㉠ : b * 2 ㉡ : b * 2