[Note] tail-recursive

[cwdoh]

꼬리 재귀

재귀호출 함수를 구현할 때 마지막(Tail)에 자기 자신만을 호출(Recursion)하는 형태의 함수다. 보통 컴파일러의 힘을 빌어 루프 형태로 실행 코드를 생성하고, 호출에 의한 콜스택이 계속 적재되는 형태가 아니므로, stack overflow가 해결되고, 콜 스택의 생성 등에 의한 성능 저하를 막을 수 있다.

~일단은 좋은 거다.~

코틀린에서는 tailrec이라는 키워드를 통해 꼬리 재귀를 명백하게 표현하고, 적절하지 않을 경우 ~뇌를 사용하지 않고~ warning을 받아낼 수 있다. 아래와 같은 재귀함수가 있다. ~재귀일 필요는 없는 내용이지만~

fun dive1(n: Int): Int =
        if (n <= 0) 1
        else dive1(n - 1)

아래와 같이 코드가 생성된다.

   public static final int dive1(int n) {
      return n <= 0?1:dive1(n - 1);
   }

tailrec을 붙여보자.

tailrec fun dive2(n: Int): Int =
        if (n <= 0) 1
        else dive2(n - 1)

올~

   public static final int dive2(int n) {
      while(n > 0) {
         --n;
      }

      return 1;
   }

쓰려면...

fun sum(n: Int): Int =
        if (n <= 0) n
        else n + sum(n - 1)

예제롤 쓸 그냥 재귀 함수다.

   public static final int sum(int n) {
      return n <= 0?n:n + sum(n - 1);
   }

tailrec을 붙여보자.

tailrec fun sumIsNotTailForm(n: Int): Int =
        if (n <= 0) n
        else n + sumIsNotTailForm(n - 1)

당연한 얘기지만 Tail-recursion form이 아니므로 그냥 같은 결과다. ㅜ

   public static final int sumIsNotTailForm(int n) {
      return n <= 0?n:n + sumIsNotTailForm(n - 1);
   }

loop 변환이 가능하도록, 콜스택 상에서의 반환에 의한 연산 등이 배제되어야 한다.

tailrec fun sumWithTailrec(n: Int, acc: Int): Int =
        if (n <= 0) 0
        else sumWithTailrec(n - 1, n + acc)

   public static final int sumWithTailrec(int n, int acc) {
      while(n > 0) {
         int var10000 = n - 1;
         acc += n;
         n = var10000;
      }

      return 0;
   }

좋지만, 호출 시에 나는 안쓰는 초기값을 넣어줘야 한다.

sumWithTailrec(100, 0)

결과를 담을 변수의 초기값을 결정하는 것은 귀찮으므로, default value를 넣어주자

tailrec fun sumWithTailrec(n: Int, acc: Int = 0): Int =
        if (n <= 0) 0
        else sumWithTailrec(n - 1, n + acc)

결과는...

   public static final int sumWithTailrec(int n, int acc) {
      while(n > 0) {
         int var10000 = n - 1;
         acc += n;
         n = var10000;
      }

      return 0;
   }

   // $FF: synthetic method
   // $FF: bridge method
   public static int sumWithTailrec$default(int var0, int var1, int var2, Object var3) {
      if((var2 & 2) != 0) {
         var1 = 0;
      }

      return sumWithTailrec(var0, var1);
   }

간단하게 호출하면 되므로 편하다.

sumWithTailrec(100)

솔직히 꼬리 재귀 최적화는 커녕 재귀 자체도 쓸 일이 많지가 않다고 생각은 하지만, 꼬리 재귀를 생성할 때 명시적인 표현으로 의도를 전달할 수 있고, default 값을 사용하면 호출 자체도 간단해보이므로 괜춘함.

~...왠지 뭐라도 적어야 할 것 같아. 퇴근 전에 끄적~