C#에서 재귀 호출 이해하기

재귀는 일단 이해되면 많은 문제에 대한 접근 방식을 크게 단순화할 수 있는 개념입니다. 이를 제대로 파악하기 위해 더 많은 예제를 살펴보고 C#에서 재귀 호출이 작동하는 방식을 자세히 살펴보겠습니다.

 

재귀란 무엇입니까?

 

프로그래밍에서의 재귀란 문제를 더 작고 관리하기 쉬운 하위 문제로 나누어 문제를 해결하기 위해 직접 또는 간접적으로 자신을 호출하는 함수를 말합니다. 재귀 함수에는 일반적으로 무한 루프에 빠지지 않도록 종료 조건이 있습니다.

 

거듭제곱

이 작업은 숫자의 거듭제곱을 계산하는 것입니다. 예를 들어, '3'을 '4'(3^4) 거듭제곱하면 '3 * 3 * 3 * 3 = 81'이 됩니다.

재귀를 사용하여 이 문제를 해결하는 방법은 다음과 같습니다.

 

public static int Power(int baseNumber, int exponent)
{
    // Termination condition
    if (exponent == 0)
        return 1;

    return baseNumber * Power(baseNumber, exponent - 1);
}

Power(3, 4)가 호출되는 경우:

1. 3 * Power(3, 3)를 반환합니다. 이는 3 * (3 * Power(3, 2))가 됩니다.
2. 계속해서 분석하면 '3 * (3 * (3 * Power(3, 1)))' 입니다.
3. 마지막으로 '3 * (3 * (3 * (3 * Power(3, 0))))' 입니다.
4. 종료 조건으로 인해 Power(3, 0)은 1을 반환합니다. 따라서 최종 계산은 3*3*3*3이 된다.

 

피보나치 수열

 

피보나치 수열은 숫자가 '0'과 '1'부터 시작하여 앞의 두 숫자의 합인 일련의 숫자입니다.

피보나치 수열에 대한 재귀 :

public static int Fibonacci(int n)
{
    // Termination conditions
    if (n <= 1)
        return n;

    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

1. 5 * Factorial(4)를 반환합니다.
2. 분해하면 5 * (4 * Factorial(3))을 얻습니다.
3. 게다가 5 * (4 * (3 * Factorial(2)))입니다.
4. 마지막으로 5 * (4 * (3 * (2 * Factorial(1))))로 변합니다.
5. Factorial(1)은 종료 조건에 따라 1을 반환합니다. 따라서 최종 답은 '5 * 4 * 3 * 2'입니다.

 

배열 요소의 합

 

이 문제를 해결하기 위해 우리는 배열의 크기를 계속해서 줄여서 배열의 나머지 부분의 합에 첫 번째 요소를 추가합니다.

public static int ArraySum(int[] arr, int n)
{
    // Termination condition
    if (n <= 0)
        return 0;
    
    return ArraySum(arr, n - 1) + arr[n - 1];
}

 

n = 4인 배열 [2, 4, 6, 8]의 경우:

 

1. 함수는 ArraySum([2, 4, 6, 8], 3) + 8을 반환합니다.
2. 추가로 ArraySum([2, 4, 6, 8], 2) + 6 + 8을 반환합니다.
3. 계속하면 ArraySum([2, 4, 6, 8], 1) + 4 + 6 + 8이 됩니다.
4. 마지막으로 n <= 0일 때 종료 조건이 0을 제공하므로 0 + 2 + 4 + 6 + 8입니다.

 

결론

재귀를 단계별로 시각화하면 그 자체가 이해하기 쉬워집니다. 재귀적 솔루션의 우아함은 종종 문제를 분석하는 단순성에서 비롯됩니다. 그러나 깊은 재귀에 대한 스택 오버플로 오류나 추가로 최적화할 수 있는 비효율적인 솔루션과 같은 함정에 항상 주의해야 합니다.