末尾再帰

実は、SICPのネタだったりする。

id:selvaggioとの雑談より。こういう話は、彼のほうが得意そうなのに・・・。

例として、次のようなコードがあったとする。



int f(int);

int g(int);
int f(int i){

  return g(i+i);

}
int g(int i){

  return i+1;

}
void main(){

  f(10);

  // .....}

関数を呼び出すためには、ローカル変数をいったん別の場所に退避させる必要があります。

そして、ローカル変数はたいていスタック上に置かれるので、関数を呼び出すためには、スタックの保存・復元が必要となります。

なので、上記のコードは次のように実行されます。

上記のコードをよく見ると、fはgを呼び出したあと、ローカル変数を一度も使用していません。ローカル変数を使わないなら、わざわざスタックを復元する必要はありません。

さらに言えば、fはgの返り値を利用して計算を行っていないので、fにいったん制御を返す必要すらありません。

なので、この2つの処理を飛ばすと次のようになります。

こういう処理のことを末尾再帰って言う、・・・んだと思います。SICPの該当するページが見つからなかったから、記憶をたよりに書いてみたから、微妙かも。