재귀 함수는 쓰레기다.

재귀 함수의 가장 대표격인 Factorial 함수를 통해 설명하겠다.

 

1. StackOverFlow

using System;
using System.Diagnostics;
using System.Net;
using System.Net.Sockets;
using System.Text;
using System.Threading.Tasks;

namespace Cs_Test
{ 
    class Program
    {
        public static ulong Factorial_recursion(ulong num)
        {
            if(num == 1)
                return 1;

            return num * Factorial_recursion(num - 1);
        }

        public static ulong Factorial_loop(ulong num)
        {
            ulong output = 1;

            for(; 1 < num; --num) 
            {
                if (num == 1) // unnecessary if.
                    return 1;

                output *= num;
            }

            return output;
        }

        public static void Main()
        {
            Stopwatch stopwatch_re = new Stopwatch(); //객체 선언

            stopwatch_re.Start();
            Console.WriteLine(Factorial_recursion(10000000));
            stopwatch_re.Stop();

            Console.WriteLine(stopwatch_re.Elapsed);
        }
    }
}

 

위 두 함수 Factorial_recursion, Factorial_loop 함수는 결과값이 같다.

Factorial (10,000,000) 의 반환값의 경우 ulong 형으로도 감당할 수 없어

변수 내부에서는 StackOverFlow 가 발생하는것이 당연하다.

 

하지만 재귀함수는 변수 내부뿐만 아니라 Stack 메모리에 '함수' 주소를 유지시킨다.

때문에 위에서 100번째 재귀작업을 수행했다면, 스택 메모리 안에는 100개의 함수주소가 유지되고 있는 것이다.

위 코드에선 16052 번 반복시 Stack overflow 에러가 발생한다.

 

 

 

 

2. Performance

 

성능적인 측면에서 재귀함수와 loop 함수를 비교 해 보자.

Main 함수를 아래와 같이 변경한다.

 

public static void Main()
{
    Stopwatch stopwatch_re = new Stopwatch();

    stopwatch_re.Start();

    for(int i = 0; i < 10000; ++i)
    {
        Factorial_recursion(10000);
    }

    stopwatch_re.Stop();

    Console.WriteLine(stopwatch_re.Elapsed);
}

i5-1135G7 CPU 기준

 

 

2-1. Recursion Function

Debug 모드서 평균적으로 1.1 초 이내에 실행된다

 

 

Release 모드서 평균적으로 0.75초 이내에 실행된다.

 

 

2-2 loop Function

loop 함수를 사용하기 위해 아래와 같이 Main 함수를 변경한다.

public static void Main()
{
    Stopwatch stopwatch_re = new Stopwatch();
    stopwatch_re.Start();

    for(int i = 0; i < 10000; ++i)
    {
        Factorial_loop(10000);
    }

    stopwatch_re.Stop();

    Console.WriteLine(stopwatch_re.Elapsed);
}

i5-1135G7 CPU 기준

 

Debug 모드서 평균적으로 0.3 초 이내에 실행된다

 

Release 모드서 평균적으로 0.2초 이내에 실행된다.

 

 

 

3. 결론

 

개인적으로 C++ 에 위치한 Template Meta Programming 을 사용하는것을 지양하는데

디버깅이 복잡하고, 활용처도 마땅치 않다는 데 있다.

그런데도 쓰레기라고 지칭하지 않는 이유는 RunTime 에서 연산시간이 0에 수렴하기 때문이다.

압도적인 성능에서 그 의의가 있는것이다.

 

반대로 재귀는 학생때부터 지금까지 느끼는거지만 쓰레기도 이런 개쓰레기가 따로없다.

사용하는데 제약도 있고, 성능도 딸리고, 작성력이 좋지도 않으며, 디버깅도 힘들다.

어떤분은 저런 간단한 Factorial 구하는 함수를 토대로 '재귀가 loop 보다 보기 편해요!' 라고 하지만,

Factorial 한정으로 보기 편할 뿐이지, 더 복잡한 함수를 구현하려고 하면, '겉보기' 에는 보기 편하나

실제로 디버깅 하려면 loop 대비 몇배는 불편하다.

 

내 경험상 수학적으로 깔끔하게 작동하고 -> 실제 재귀 형태로 구현하기 용이하며,

남에게 코드를 인수인계 할때, 성능이 크게 상관 없을때 제한적으로 쓸만하다.

 

4. 대표적인 예외로

분할정복 알고리즘의 경우에는 설계상 재귀함수로 구현하는게 올바르다.

애초에 메모리 복귀주소를 필요로 하며, 재귀로 구현하기 깔끔하기에 적절하다.