C# 꼬리 재귀(tail recursion)

꼬리 재귀(tail recursion)란 무엇인가?

지금까지 재귀에 대해서 설명하면 GetFactorial() 메서드를 사용해서 계승을 계산하는 전통적인 재귀 형태를 사용했다. 이 방식은 재귀 호출을 먼저 수행하고 값을 반환하며, 이후에 결과를 계산한다. 이 재귀 모델을 이용하는 경우, 재귀 호출이 끝날 때까지 결과를 얻을 수 없다.

 

이 같은 전통적인 재귀 모델과 더불어 꼬리 재귀(tail recursion)라는 또 다른 형태가 있다. 

꼬리 재귀에서는 꼬리 즉, 마지막 재귀 호출이 함수가 수행하는 마지막 작업이다.

 

using System;

public partial class Program
{
    static void Main(string[] args)
    {
        TailCall(5);
    }

    public static void TailCall(int iTotalRecursion)
    {
        Console.WriteLine($"Value: {iTotalRecursion}");

        if (iTotalRecursion == 0)
        {
            Console.WriteLine("the tail is executed");
            return;
        }

        TailCall(iTotalRecursion - 1);
    }
}

 

iTotalRecursion이 0에 도달했을 때, 다음과 같이 이뤄진다.

 

 

이제, 재귀 호출이 발생할 때마다 일어나는 상태 변화를 확인해 보자.

 

TailCall(5)
 (iTotalRecursion = 5) != 0
 TailCall(4)
  (iTotalRecursion = 4) != 0
  TailCall(3)
   (iTotalRecursion = 3) != 0
   TailCall(2)
    (iTotalRecursion = 2) != 0
    TailCall(1)
     (iTotalRecursion = 1) != 0
     TailCall(0)
      (iTotalRecursion = 0) == 0
    TailCall(1) => 처리 사항 없음
   TailCall(2) => 처리 사항 없음
  TailCall(3) => 처리 사항 없음
 TailCall(4) => 처리 사항 없음
TailCall(5) => 처리 사항 없음

 

이와 같은 재귀 흐름에 따라 꼬리의 프로세스는 최종 재귀 호출 시에만 실행되며, 그 후에는 다른 재귀 호출에서 어떠한 처리도 하지 않는다. 즉, 이 흐름은 결론적으로 다음과 같다고 할 수 있다.

 

TailCall(5)
 (iTotalRecursion = 5) != 0
 TailCall(4)
  (iTotalRecursion = 4) != 0
  TailCall(3)
   (iTotalRecursion = 3) != 0
   TailCall(2)
    (iTotalRecursion = 2) != 0
    TailCall(1)
     (iTotalRecursion = 1) != 0
     TailCall(0)
      (iTotalRecursion = 0) == 0
      꼬리에서 정의된 프로세스 실행
끝 종료!

 

꼬리 재귀의 핵심은 제한된 자원인 스택 사용량을 최소화하는 것이다. 꼬리 재귀를 이용하면 다음 단계가 반환됐을 때를 위해 마지막 상태 값을 기억할 필요가 없다. 이어서 꼬리 재귀의 두 가지 유형인 누적기 전달형(Accoumulator-Passing Stype, APS)과 연속 전달형(Continuation-Passing Style, CPS)에 대해 살펴보겠다.

 

누적기 전달형(accumulator-passing stype)

누적기 전달형 재귀는 먼저 연산을 처리하고 재귀 호출을 실행하면서 현 단계의 결과를 다음 재귀 단계로 전달하는 방식이다.

 

using System;

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

    public static int GetFactorialAPS(int number, int accumulator = 1)
    {
        if (number == 0)
        {
            return accumulator;
        }

        return GetFactorialAPS(number - 1, accumulator * number);
    }
}

 

GetFactoralAPS() 메서드에는 accumulator라는 두 번째 매개 변수가 추가됐다. accumulator의 기본 값이 1인 것은 0의 계승이 1이기 때문이다. 값 하나만 반환하던 것과 달리 이제 재귀 호출이 발생할 때마다 계승을 계산한 값을 반환한다. 

 

 

다음은 상태 변화를 순서대로 나열한 것이다.

 

int i = GetFactorialAPS(5, 1)
 accumulator = 1
 (intNumber = 5) != 0
 return GetFactorialAPS(4, 5 * 1)
  accumulator = 5 * 1 = 5
  (intNumber = 4) != 0
  return GetFactorialAPS(3, 4 * 5)
   accumulator = 4 * 5 = 20
   (intNumber = 3) != 0
   return GetFactorialAPS(2, 3 * 20)
    accumulator = 3 * 20 = 60
    (intNumber = 2) != 0
    return GetFactorialAPS(1, 2 * 60)
     accumulator = 2 * 60 = 120
     (intNumber = 1) != 0
     return GetFactorialAPS(0, 1 * 120)
      accumulator = 1 * 120 = 120
      (intNumber = 0) == 0
      return accumulator
     return 120
    return 120
   return 120
  return 120
 return 120
i = 120

 

보다시피 호출할 때마다 계산이 이뤄지므로 다음처럼 intNumber가 0에 도달하는 마지막 함수 호출에서 결과를 얻는다.

 

여기서 GetFactorialAPS()가 값을 반환하지 않게 다시 리팩터링 한 GetFactorialAPS2()를 보면 꼬리 재귀에서 APS가 어떻게 동작하는지 더욱 명확해진다.

 

using System;

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

    public static void GetFactorialAPS2(int number, int accumulator = 1)
    {
        if (number == 0)
        {
            Console.WriteLine($"The result is {accumulator}");
            return;
        }

        GetFactorialAPS2(number - 1, accumulator * number);
    }
}

 

 

GetFactorialAPS2()의 상태 변경 과정은 다음과 같이 이전에 비해 더욱 명료하다.

GetFactorialAPS2(5, 1)
 accumulator = 1
 (intNumber = 5) != 0
 GetFactorialAPS2(4, 5 * 1)
  accumulator = 5 * 1 = 5
  (intNumber = 4) != 0
  GetFactorialAPS2(3, 4 * 5)
   accumulator = 4 * 5 = 20
   (intNumber = 3) != 0
   GetFactorialAPS2(2, 3 * 20)
    accumulator = 3 * 20 = 60
    (intNumber = 2) != 0
    GetFactorialAPS2(1, 2 * 60)
     accumulator = 2 * 60 = 120
     (intNumber = 1) != 0
     GetFactorialAPS2(0, 1 * 120)
      accumulator = 1 * 120 = 120
      (intNumber = 0) == 0
      accumulator 값 출력
종료!

 

연속 전달형(continuation-passing style)

연속 전달형은 꼬리 호출을 이용해서 재귀를 구현한다는 점에서 APS와 같지만 작업 과정에 명시적인 연속을 사용한다는 차이가 있다. CPS 함수의 반환값은 연속 함수에 전달된다.

 

using System;

public partial class Program
{
    static void Main(string[] args)
    {
        Console.WriteLine($"5! GetFactorialCPS(5):");
        GetFactorialCPS(5, x => Console.WriteLine(x));
    }

    public static void GetFactorialCPS(int intNumber, Action<int> actCont)
    {
        if (intNumber == 0)
        {
            actCont(1);
        }
        else
        {
            GetFactorialCPS(intNumber - 1, x => actCont(intNumber * x));
        }
    }
}

 

 

실행 결과는 다음과 같이 GetFactorialAPS2()와 일치한다. 하지만 재귀 과정을 보면 살짝 다른 면이 있다.

 

GetFactorialCPS(5, Console.WriteLine(x))
 (intNumber = 5) != 0
 GetFactorialCPS(4, (5 * x))
  (intNumber = 4) != 0
  GetFactorialCPS(3, (4 * x))
   (intNumber = 3) != 0
   GetFactorialCPS(2, (3 * x))
    (intNumber = 2) != 0
    GetFactorialCPS(1, (2 * x))
     (intNumber = 1) != 0
     GetFactorialCPS(0, (1 * x))
      (intNumber = 0) == 0
      GetFactorialCPS(0, (1 * 1))
     (1 * 1 = 1)
    (2 * 1 = 2)
   (3 * 2 = 6)
  (4 * 6 = 24)
 (5 * 24 = 120)
Console.WriteLine(120)

 

LINQ Aggregate를 이용한 함수형 재귀 호출

지금까지 살펴본 계승 공식에 LINQ의 Aggregate를 적용하면 재귀 함수를 함수형 접근 방식으로 리팩토링 할 수 있다. LINQ Aggregate를 이용하면 주어진 시퀀스를 누적한 다음 누적기로부터 재귀 결과를 얻을 수 있다.

 

using System;
using System.Collections.Generic;
using System.Linq;

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

    public static int GetFactorialAggregate(int intNumber)
    {
        IEnumerable<int> ints = Enumerable.Range(1, intNumber);

        var result = ints.Aggregate((x, y) => x * y);
        return result;
    }
}

 

 

이처럼 Aggregate를 이용해 일반적인 재귀 함수를 이용할 것과 같은 결과를 얻을 수 있다.

 

Aggregate 메서드

Aggregate 메서드의 동작 원리에 대해서 알아보자. 함수형에서 그 개념을 가져왔으며 함수형 언어에서는 reduce, fold 등의 이름으로 구현되어 있다.

 

using System;
using System.Collections.Generic;
using System.Linq;

public partial class Program
{
    static void Main(string[] args)
    {
        AggregateInt();
    }

    public static void AggregateInt()
    {
        var list = new List<int>() { 1, 2, 3, 4, 5, 6 };

        int addision = list.Aggregate((sum, i) => sum + i);

        Console.WriteLine($"The sum of listInt is {addision}");
    }
}

 

이 코드는 1부터 6까지 정수를 포함하는 int 형식의 리스트를 만들고, Aggregate를 이용해서 이 리스트(listInt) 내의 항목들의 합을 구한다. 다음은 이 코드의 흐름이다.

(sum, i) => sum + i
sum = 1
sum = 1 + 2
sum = 3 + 3
sum = 6 + 4
sum = 10 + 5
sum = 15 + 6
sum = 21
addition = sum

 

Aggregate 메서드는 숫자의 합을 구하는 것에 그치지 않고 문자로 다룰 수 있다. 다음은 Aggregate 메서드를 이용해서 문자열 시퀀스를 더하는 예다.

using System;
using System.Collections.Generic;
using System.Linq;

public partial class Program
{
    static void Main(string[] args)
    {
        AggregateString();
    }

    public static void AggregateString()
    {
        var list = new List<string>() { "the", "quick", "brown", "fox", "jumps", "over", "the", "lazy", "dog" };

        string stringAggregate = list.Aggregate((strAll, str) => strAll + " " + str);

        Console.WriteLine(stringAggregate);
    }
}

 

실행한 결과는 다음과 같다.

 

(strAll, str) => strAll + " " + str
strAll = "The"
strAll = "The" + " " + "quick"
strAll = "The quick" + " " + "brown"
strAll = "The quick brown" + " " + "fox"
strAll = "The quick brown fox" + " " + "jumps"
strAll = "The quick brown fox jumps" + " " + "over"
strAll = "The quick brown fox jumps over" + " " + "the"
strAll = "The quick brown fox jumps over the" + " " + "lazy"
strAll = "The quick brown fox jumps over the lazy" + " " + "dog"
strAll = "The quick brown fox jumps over the lazy dog"
stringAggreate = strAll

 

이와 같은 처리 흐름에 따라 Aggregate 메서드는 listString의 모든 문자열을 연결하며, int 형식뿐만 아니라 string 형식에서도 훌륭하게 동작한다.

 

함께 읽으면 좋은 글

C# Linq - Enumerable.Aggregate()

C#으로 함수형 프로그래밍을 해보자

출처

Functional C# - 예스24