再帰と末尾再帰とは？

再帰と末尾再帰の意味

関数が自分自身を呼び出しながら処理を進める手法（再帰）のうち、再帰呼び出しが関数の一番最後の処理になっている形式を「末尾再帰」と呼ぶ。末尾再帰は一部の処理系でループ処理に変換され、呼び出しごとにスタックを積み上げる必要をなくせる。

再帰と末尾再帰の具体例

階乗計算を「戻ってきてから掛け算する」形で書くと通常の再帰、「途中経過を引数で渡しながら呼び出す」形で書くと末尾再帰になる。末尾再帰最適化に対応した処理系ではスタックオーバーフローを避けやすい。

再帰と末尾再帰は試験でどう引っ掛けられる？

「再帰呼び出しが最後に書いてあるか」ではなく「再帰呼び出しの戻り値にさらに演算を加えていないか」が末尾再帰の分岐点。return n * f(n-1) は呼び出しの後に掛け算が残るので末尾再帰ではない。また再帰的（リカーシブ）と再入可能（リエントラント）は別概念で、再帰的に呼べても複数プロセスから同時に呼べるとは限らない。

再帰と末尾再帰と関連する用語

• スタックとキュー