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 recursion happens if a function, as its last operation, returns the result of calling itself. Tail recursion is easier to deal with because rather than having to jump to the beginning of some random function somewhere, you just do a goto back to the beginning of yourself, which is a darned simple thing to do.

Şö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.