Zenn
🐕

tail recursion: 末尾再帰最適化

2020/10/22に公開
ポエム
idea

世の中にたくさんわかりやすい記事があったので、そちらへのリンクだけ張る感じになってしまった。

tail callについて

末尾再帰を理解する

末尾再帰を詳細に理解する

https://qiita.com/pebblip/items/cf8d3230969b2f6b3132

関連: フィボナッチ数列を計算したときの計算量関連の話

メモ

Tail Recursionは、再帰的な関数呼び出しのあとに計算をしないもの。

以下は、Tail Recursionである。

int f(int x, int y) {
  if (y == 0) {
    return x;
  }

  return f(x*y, y-1);
}

一方、以下はTail Recursionではない。なぜなら、再帰関数g(x-1)を呼び出しあとに、x*g(x-1)という計算しているからである。

int g(int x) {
  if (x == 1) {
    return 1;
  }

  int y = g(x-1);

  return x*y;
}

Tail Recursionは、コンパイラでの最適化が行われるため、通常の再帰関数より効率的とされている。

Tail recursion is important because it can be implemented more efficiently than general recursion. When we make a normal recursive call, we have to push the return address onto the call stack then jump to the called function. This means that we need a call stack whose size is linear in the depth of the recursive calls. When we have tail recursion we know that as soon as we return from the recursive call we're going to immediately return as well, so we can skip the entire chain of recursive functions returning and return straight to the original caller. That means we don't need a call stack at all for all of the recursive calls, and can implement the final call as a simple jump, which saves us space.

Discussion