[22장] 재귀함수

자 오늘은 재귀 함수에 대해 공부를 해보겠습니다.
재귀 함수란 아래와 같은 형태의 함수를 의미합니다.

#include <stdio.h>     // 1 line
                       // 2
int Print()            // 3
{                      // 4
    printf("Print\n"); // 5
    Print();           // 6
}                      // 7
                       // 8
int main()             // 9
{                      // 10
   Print();            // 11
   return 0;           // 12
}                      // 13

// 실행결과
// runtime error eccured

 

자기 자신을 호출하는 함수를 재귀 함수라고 합니다.
위의 코드는 문제가 있는데 실제로 실행해보면 11라인에서 3~6라인 다시 3~6라인 무한히 호출이 됩니다.

 

종료조건이 없는 재귀함수의 Stack메모리

함수가 완전히 수행해서 종료가 돼야 Stack 메모리에서 제거가 됩니다.

하지만 위 코드는 계속 콜 하니까 제거는 안되고 쌓이기 만하죠? 결과적으로 메모리가 부족해서 프로그램이 죽게 됩니다.

하지만 종료 조건이 있다면 프로그램을 정상 종료시킬 수 있는데요.
아래의 코드를 보시죠!

#include <stdio.h>                // 1 line
                                  // 2 
int Print(int idx)                // 3             
{                                 // 4
    if (idx <= 0)                 // 5
       return;                    // 6
    printf("Print: % d\n", idx);  // 7
    Print(idx - 1);               // 8 
}                                 // 9
                                  // 10
int main()                        // 11
{                                 // 12
    Print(3);                     // 13
                                  // 14
    return 0;                     // 15
}

// 실행결과
// Print: 3
// Print: 2
// Print: 1

 

종료조건이 있는 재귀함수의 Stack메모리 (초기: 함수 콜에 의해 가득찬 상태)

함수 호출 한 결과를 그려보면 아래와 같습니다.
이해가 되시죠? idx가 0 미만이면 조건에 부합되지 않아서 Print를 더 이상 호출하지 않게 돼서 스택을 비우게 됩니다.

하나하나 호출됬던 함수들이 스택에서 비워지니깐 함수가 정상적으로 종료가 됩니다.

재귀 함수는 자기 자신을 콜 하는 함수 하나하나가 분기입니다.

위의 코드는 분기가 하나인 코드인데요.  다음은 분기가 2개인 코드를 보시죠!

#include <stdio.h>                   // 1 line
                                     // 2
int Print(int idx)                   // 3
{                                    // 4
    if (idx <= 0)                    // 5
       return;                       // 6
    printf("Print: % d\n", idx);     // 7
    Print(idx - 1);                  // 8
    Print(idx - 1);                  // 9
}                                    // 10
                                     // 11
 int main()                          // 12
{                                    // 13
    Print(3);                        // 14
    return 0;
}

한 노드를 중심으로 2갈래씩 쪼개지면서 조건에 만족하는 모든 노드를 순회하게 됩니다.
자기 함수 호출 수만큼 쪼개지는 노드가 발생을 하게 됩니다.

 

재귀 함수에서 분기가 2개인 코드

앞서 말한 것과 같이 함수 호출을 할 때마다 메모리 Stack에 쌓였다가 함수의 종료되면 Stack을 비운 후, 다시 원래의 함수로 복귀를 하는데요.

이 재귀를 사용하게 되면 stack 메모리가 엄청나게 소모되기 때문에 실무에선 되도록 지양합니다.

반복문으로 얼마든지 구현 할 수 있습니다. 

 

알고리즘 대회나 코딩 문제 풀이에선 코드 몇 줄로 문제를 단순하게 풀 수 있어서 많이 활용되곤 합니다.
자 다음은 재귀함수를 사용한 예제입니다.

#include <stdio.h>

void Pibonach(int n)
{
    if (n <= 1)
        return 1;
    return n * Pibonach(n - 1)
}

int main()
{
    printf("% d\n", Pibonach(5);
    return 0;
}

// 실행결과
// 120

 

재귀 함수에 대한 심화 부분은 알고리즘 및 자료구조를 공부할 때
더 사용해보겠습니다. 오늘은 개념만 공부해보시기 바랍니다~