리눅스 C 프로그래밍 튜토리얼 18부: 재귀 함수

프로그래밍 언어에 관계없이 코딩을 많이 하다 보면 코드가 간결하고 읽기/이해하기 쉬운 개념을 배우게 됩니다. C 언어에도 이러한 개념이 여러 가지 있습니다. 그 중 하나가 ‘재귀 함수’로, 이 기사에서 논의할 것입니다.

재귀 함수는 자신을 호출하는 함수입니다. 호출은 함수 본체 내에서 직접 이루어질 수 있으며, 해당 함수에 의해 호출되는 다른 함수 내에서 간접적으로 이루어질 수도 있습니다.

다음은 직접 재귀의 예입니다:

int func (int a)  
{  
    //statements  
  
    func(a-1);  
  
    // statements  
  
    return 0;  
}

그리고 다음은 간접 재귀의 예입니다:

int func (int a)  
{  
    //statements  
  
    func_new(a);  
  
    // statements  
  
    return 0;  
}  
  
int func_new(int b)  
{  
    //statements  
  
    func(b-1);  
  
    //statementsur  
  
    return 0;  
}

앞서 언급했듯이, 재귀는 간결한 코드를 작성하는 데 도움을 주며, 이는 작성하기 쉬울 뿐만 아니라 이해하고 검토하기도 쉽습니다. 이 장점을 더 명확히 하기 위해 예를 들어 보겠습니다.

모두가 팩토리얼 개념에 대해 들어본 적이 있을 것이라고 확신합니다. 잘 모르는 분들을 위해 설명하자면, 팩토리얼은 정수를 그보다 작은 모든 양의 정수와 곱했을 때의 결과입니다. 예를 들어, 5의 팩토리얼은 5x4x3x2x1로, 이는 120과 같습니다.

다음은 숫자의 팩토리얼을 찾기 위한 간단한 코드입니다:

#include   
  
int main()  
{  
 int a = 0, i = 0, fact = 1;  
 printf("숫자를 입력하세요: ");  
  
 scanf("%d", &a);  
   
 for(i=1; i<=a; i++)  
 {  
 fact = fact * i;  
   
 }  
 printf("숫자의 팩토리얼은: %d ", fact);  
 return 0;  
}

이 코드는 숫자의 팩토리얼을 C 프로그램을 통해 계산하는 방법을 알려주기 위한 것입니다. 이 프로그램은 결과의 정확성에 영향을 미칠 수 있는 모서리 케이스를 처리하지 않습니다.

따라서 이것은 재귀 함수를 사용하지 않고 숫자의 팩토리얼을 계산할 수 있는 여러 방법 중 하나입니다. 이제 재귀를 사용하여 팩토리얼을 계산하는 코드를 살펴보겠습니다.

#include   
  
int factorial (int b)  
{  
 if(!b)  
 return 1;  
   
 return (b * factorial(b-1));  
}  
  
int main()  
{  
 int a = 0, fact = 1;  
 printf("숫자를 입력하세요: ");  
  
 scanf("%d", &a);  
   
 fact = factorial(a);  
   
 printf("숫자의 팩토리얼은: %d ", fact);  
 return 0;  
}

보시다시피, 실제로 팩토리얼을 계산하는 ‘factorial’ 함수는 매우 간결합니다. 그리고 주의 깊게 살펴보면 이해하기도 매우 쉽습니다.

무슨 일이 일어나고 있는지 모르는 분들을 위해 설명하자면, 사용자가 입력한 값, 예를 들어 5가 ‘main’ 함수 내에서 처음 호출될 때 ‘factorial’ 함수로 전달됩니다. ‘factorial’ 함수 내에서는 입력 값이 0인지 확인하는 조건이 있으며, 이는 함수가 처음 호출될 때 입력 값이 ‘5’이므로 참이 아닙니다.

그런 다음, return 문에는 5와 ‘factorial(4)’의 반환 값을 곱하는 표현식이 포함되어 있습니다. 그래서 이제 ‘factorial’ 함수가 다시 실행되고, 다음 표현식에 도달합니다: return (4 * factorial(3)). 그리고 다시 이러한 단계가 반복됩니다.

넓게 보면, 이러한 함수 호출이 쌓이는 방식은 다음과 같습니다:

• 5 * factorial(4)
• 4 * factorial(3)
• 3 * factorial(2)
• 2 * factorial (1)
• 1 * factorial (0)

이제 factorial(0)이 실행되면, ‘factorial’ 함수의 ‘if’ 조건이 참이 되어 값 ‘1’이 반환됩니다. 따라서 이제 위에 나열된 호출이 완료되는 방식은 다음과 같습니다(이전 목록의 마지막 항목과 이 목록의 첫 번째 항목을 비교하세요):

• 1 * 1
• 2 (11)
• 3 (2(1*1))
• 4 (3(2(11)))
• 5 (4 (3(2(1*1))))

이는 효과적으로 5 4 3 2 1로, 이는 다시 120, 즉 5의 팩토리얼입니다.

이것이 재귀 함수가 작동하는 방식입니다. 지금까지 나열한 재귀 함수의 장점에 의심의 여지가 없지만, 단점도 있습니다.

예를 들어, 위의 예에서 ‘factorial(0)’ 호출이 완료될 때까지 모든 이전 ‘factorial’ 호출은 함수 처리가 완료될 때까지 대기하고 있었습니다. 재귀 호출마다 자동 또는 지역 변수가 메모리를 차지한다는 사실은 말할 것도 없습니다.

따라서 재귀를 사용할 때 저장 공간에서 실질적인 절약이 없습니다. 또한 코드 실행 속도가 더 빠를 것이라는 보장도 없습니다. 재귀 함수의 실제 장점은 데이터 구조를 다룰 때 발생하며, 이는 이 진행 중인 C 튜토리얼 시리즈의 후속 부분에서 논의할 것입니다.

결론

결론적으로, 일상적인 코딩 작업에서 재귀 함수를 자주 사용하지 않을 수 있지만, 반드시 알아야 할 중요한 개념입니다. 여기서 언급한 예제를 시도해 보고, 재귀 함수의 개념을 더 잘 이해하기 위해 수정해 보세요.