꼬리 재귀

여러분, 안녕하세요! 👋

오늘의 기사는 특정 재귀 함수를 최적화할 수 있는 기술인 꼬리 재귀에 관한 것입니다.

소개

즉, 재귀 함수를 작성할 때 새로 호출할 때마다 스택에 프레임을 할당합니다. 예를 들어 다음과 같은 기능을 수행해 보겠습니다.

private static long RecursiveFib(long n)
{
    if (n <= 1)
    {
        return n;
    }
    return RecursiveFib(n - 1) + RecursiveFib(n - 2);
}

return n에 중단점을 설정하고 RecursiveFib(10)으로 함수를 호출하면 다음과 같은 스택 프레임을 얻게 됩니다. 스택 프레임에는 10개의 항목이 있습니다.



RecursiveFib()에 대한 각 재귀 호출은 이전 호출에 종속되며 프로그램은 이전 호출을 기억하기 위해 새 스택 프레임을 추가해야 합니다. 새 스택 프레임을 추가하는 프로세스에는 약간의 시간이 걸리며 프로그램에 많은 프레임이 필요한 경우 스택 오버플로 오류가 발생할 수 있습니다.

RecursiveFib(40)을 벤치마킹하면 약 4986853 경과된 틱을 얻습니다.

반복 버전

루프와 경우에 따라 스택을 사용하여 반복적인 방식으로 함수를 다시 작성할 수 있습니다. 그런 다음 루프 언롤링이라는 기술을 사용하여 컴파일러에서 루프를 추가로 최적화할 수 있습니다.

RecursiveFib의 반복 버전은 다음과 같습니다.

private static long IterativeFib(long n)
{
    var a = 0L;
    var b = 1L;
    if (n == 0)
    {
        return a;
    }
    for (var i = 1; i < n; i++)
    {
        var c = a + b;
        a = b;
        b = c;
    }

    return b;
}

반복 버전에서 IterativeFib(10) 스택에는 2개의 항목만 있습니다.



IterativeFib(100)에 대한 벤치마크는 19개의 경과된 틱을 보여줍니다. 이는 재귀 버전 RecursiveFib(40)보다 ~26246594% 더 빠르며 스택 오버플로 오류가 발생하지 않습니다.

꼬리 재귀

꼬리 재귀는 재귀와 비슷하지만 스택을 사용하는 대신 컴파일러가 레지스터를 사용합니다. 재귀 호출이 이전 호출에 의존하지 않는 방식으로 함수를 작성하면 됩니다. 일반적으로 데이터를 보관하려면 함수 서명에 추가 매개변수를 추가해야 합니다.

private static long TailRecursiveFib(long n, long a , long b )
{
    return n switch
    {
        0 => a,
        1 => b,
        _ => TailRecursiveFib(n - 1, b, a + b)
    };
}

TailRecursiveFib(100, 0 ,1)에 대한 벤치마크는 21개의 경과된 틱을 보여주며 이는 반복 버전에 매우 가깝습니다.

결론

꼬리 재귀는 새 재귀 호출이 현재 스택 프레임을 대체하고 새 스택 프레임을 추가하지 않는 방식으로 재귀 함수를 다시 작성하는 기술입니다.

읽어주셔서 감사하고 뭔가 배웠기를 바랍니다! 🍻

전체 코드 조각

using System;
using System.Diagnostics;

namespace TailRecursion
{
    static class Program
    {
        private static long TailRecursiveFib(long n, long a , long b )
        {
            return n switch
            {
                0 => a,
                1 => b,
                _ => TailRecursiveFib(n - 1, b, a + b)
            };
        }

        private static long RecursiveFib(long n)
        {
            if (n <= 1)
            {
                return n;
            }
            return RecursiveFib(n - 1) + RecursiveFib(n - 2);
        }

        private static long IterativeFib(long n)
        {
            var a = 0L;
            var b = 1L;
            if (n == 0)
            {
                return a;
            }
            for (var i = 1; i < n; i++)
            {
                var c = a + b;
                a = b;
                b = c;
            }

            return b;
        }

        private static void Main(string[] args)
        {
            var st = new Stopwatch();
            var r = new Random();
            for (var i = 0; i < 5; i++)
            {
                RecursiveFib(i);
                IterativeFib(i * 10 );
                TailRecursiveFib(i * 10, 0, 1);
            }

            long result = 0;
            st.Restart();
            // result = RecursiveFib(10);
            result = TailRecursiveFib(100, 0, 1);
            // result = IterativeFib(100);
            st.Stop();
            Console.WriteLine("Elapsed ticks: {0}", st.ElapsedTicks);
            Console.WriteLine(result);
        }
    }
}