Tail Call - Klasik Recursion

Giriş
Tail Call aynı zamanda Tail Recursion olarak da bilinir. Özel bir çeşit öz yinelemeli çağrıdır. Açıklaması şöyle

Tail Call Optimization (TCO) lets you write recursive functions without worrying about running out of memory. If a function calls itself as its last action, TCO can reuse the current function’s stack frame.

Şöyledir.

sub foo (int a, int b) {
  if (b == 1) {
    return a;
  } else {
    return foo(a*a + a, b - 1);
  }
}

Bu kod derleyici tarafından şuna çevrilir.

sub foo (int a, int b) {
  label:
    if (b == 1) {
      return a;
    } else {
      a = a*a + a;
      b = b - 1;
      goto label;
   }
}

C++
Elimizde şöyle bir kod olsun.

void test2(int curIndex){
  if(curIndex == size) return;
  s+=A[curIndex];
  test2(curIndex+1);
}

Kod şuna çevrilir.

void test2(int curIndex){
  while(true)
  {
    if(curIndex == size) return;
    s+=A[curIndex];
    curIndex = curIndex + 1;
  }
}

Tail Recursion'ı Kaldırmak

Bazı kodlar Tail Recursion'ı call stack yüzünden kaldırıyor. Öreğin Quicksort. Açıklaması şöyle

Quicksort takes O(N2) time in the worst case.

In that worst case, if each call recurses separately on both halves, it also takes O(N) stack space.

That is too much space to waste on the call stack.

Practical implementations of quicksort recurse on the smaller half, and then loop to sort the larger half. This limits the worst case stack consumption to O(log N) in the worst case, which is quite reasonable.