C# 재귀 호출 동작 방식

재귀 호출에 대해

재귀(recursion) 함수란 자신을 호출하는 함수를 말하는데, while이나 for와 같은 순환처럼 재귀 함수도 하나씩 작은 부분을 처리한 결과를 결합해 하나의 복잡한 문제를 해결해 나가는 방법이다. 하지만 for나 while은 작업이 끝날 때까지 반복을 계속하는 반면, 재귀호출은 작업 자체를 잘게 쪼개서 처리한 결과를 결합하는 방법으로 더 큰 문제를 해결한다는 차이가 있다. 반복에 비해 재귀가 더 짧게 구현 가능한 경우가 많기 때문에 함수형 접근 방식에 적합하지만, 설계와 테스트는 더 어려운 편이다.

 

• 재귀 호출로 코드를 더 짧게 구현 가능
• 설계와 테스트 난이도가 올라감

using System;

public partial class Program
{
    static void Main(string[] args)
    {
        Console.WriteLine($"Factorial :{Factorial(5)}");
    }

    public static int Factorial(int n)
    {
        if (n == 0)
        {
            return 1;
        }

        return n * Factorial(n - 1);
    }
}

 

 

일반적으로 재귀 함수 예제로 자주 등장하는 Factorial 함수를 구현해 봤다. Factorial 함수 내부에서 Factorial 함수를 호출한다. 전형적인 재귀 함수의 구조이다. 예제의 경우 개별 재귀 호출이 실행될 때마다 n의 값이 바뀌며 최종적으로 n이 0이 되면 호출을 멈춘다.

 

재귀 호출의 동작 방식

재귀 호출이 어떻게 동작하는지 이해하기 위해 예제에서 5의 계승을 찾는 과정을 n의 상태 변화를 보면서 살펴보자.

 

int i = GetFactorial(5)
 (n = 5) != 0
 return 5 * Factorial(4)
  (n = 4) != 0
  return 4 * Factorial(3)
   (n = 3) != 0
   return 3 * Factorial(2)
    (n = 2) != 0
    return 2 * Factorial(1)
     (n = 1) != 0
     return 1 * Factorial(0)
      (n = 0) == 0
      return 1
     return (1 * 1 = 1)
    return (2 * 1 = 2)
   return (3 * 2 = 6)
  return (4 * 6 = 24)
 return (5 * 24 = 120)
i = 120

 

이 흐름은 재귀 호출의 동작을 명쾌하게 보여주고, 기본 케이스가 재귀 호출의 끝을 정의하는 것을 확인할 수 있다. 한편, 함수 호출을 제거하고 반복하는 형태의 구현이 더 효율적인 경우에 컴파일러가 재귀 호출을 반복으로 변환하기도 한다.

 

반복을 재귀 호출로 리팩터링 하기

재귀는 가독성을 높여주며 함수형 프로그래밍에서는 필수적이다. 이번에는 for 루프 반복을 재귀 메서드로 리팩토링 해보자.

 

using System;

public partial class Program
{
    static void Main(string[] args)
    {
        int[] intDataArray = { 8, 10, 24, -1, 98, 47, -101, 39 };
        Console.WriteLine($"Max Number: {FindMaxIteration(intDataArray)}");
    }

    public static int FindMaxIteration(int[] array)
    {
        int iMax = 0;
        for (int i = 0; i < array.Length; i++) 
        {
            if (array[i] > iMax)
            {
                iMax = array[i];
            }
        }

        return iMax;
    }
}

 

 

이제 FindMaxIteration() 메서드를 재귀 함수로 리팩토링 해보자.

 

using System;

public partial class Program
{
    static void Main(string[] args)
    {
        int[] intDataArray = { 8, 10, 24, -1, 98, 47, -101, 39 };
        Console.WriteLine($"Max Number: {FindMaxRecursive(intDataArray)}");
    }

    public static int FindMaxRecursive(int[] intArray, int iStartIndex = 0)
    {
        if (iStartIndex == intArray.Length - 1)
        {
            return intArray[iStartIndex];
        }
        else
        {
            return Math.Max(intArray[iStartIndex], FindMaxRecursive(intArray, iStartIndex + 1));
        }
    }
}

 

 

결과에 도달하는 재귀 호출 과정은 다음과 같다.

 

Array = { 8, 10, 24, -1, 98, 47, -101, 39 }
Array.Length - 1 = 7
int iMaxNumber = FindMaxRecursive(Array, 0)
 (iStartIndex = 0) != 7
 return Max(8, FindMaxRecursive(Array, 1))
  (iStartIndex = 1) != 7
  return Max(10, FindMaxRecursive(Array, 2))
   (iStartIndex = 2) != 7
   return Max(24, FindMaxRecursive(Array, 3))
    (iStartIndex = 3) != 7
    return Max(-1, FindMaxRecursive(Array, 4))
     (iStartIndex = 4) != 7
     return Max(98, FindMaxRecursive(Array, 5))
      (iStartIndex = 5) != 7
      return Max(47, FindMaxRecursive(Array, 6))
       (iStartIndex = 6) != 7
       return Max(-101, FindMaxRecursive(Array, 7))
        (iStartIndex = 7) == 7
        return 39
       return Max(-101, 39) = 39
      return Max(47, 39) = 47
     return Max(98, 47) = 98
    return Max(-1, 98) = 98
   return Max(24, 98) = 98
  return Max(10, 98) = 98
 return Max(8, 98) = 98
return 98

 

이 흐름으로부터 FindMaxRecursive()를 호출할 때마다 최댓값의 변화를 확인할 수 있으며, 최종적으로 주어진 배열의 최댓값은 98 임을 증명할 수 있다.

 

이렇게 풀어서 보니 재귀가 작동하는 방법에 대해서 한층 이해도가 높아졌다.