末尾再帰ってあるじゃないですか・・・
って、書いて、??といわれると、先に話が進まないので、説明しちゃうと、
自分を呼び出す再帰プログラムの場合、
int a(x)
{
if ( x == 1 )
{
return 1;
}
return x + a(x-1);
}
とかやってしまうと、a(x-1)の再帰をやった後で、xと掛ける作業が必要ななので、このxの領域を保存しておかなきゃいけない、ってことは、再帰を行うたびに、メモリ領域ががんがん増えていくので、よくないなどと、C言語では、言われてたわけです。
でもね、もし、再帰のあとに、なーんにも命令がなかったら、つまり、
int a_oya(x)
{
int hikisu;
hikisu = 0;
a(&hikisu,x);
return hikisu;
}
void a(int *x,int n)
{
if ( n == 1 )
{
return;
}
(*x) = (*x) + n;
a(x,n-1);
}
とやったら、hikisuの領域だけとっておけば、最後の命令を実行したあと、GOTO で関数aの最初に飛ばせばよいだけだから、メモリ領域は増えないよね。
このように、最後に再帰を持ってきて、
呼び出し関数
{
初期化
再帰させる関数(引数・・繰り返し用引数);
}
再帰させる関数(引数・・繰り返し用引数)
{
if(繰り返し引数が終了条件に達したら)
{
終了処理
}
やりたい処理
再帰させる関数(引数・・繰り返し用引数-1)
}
みたいなかんじで、再帰させる関数を最後(末尾)に書いて、メモリを増やさない方法を末尾再帰といいます。
で、この末尾再帰なんだけど、みなさんは、どこで習いましたか?
ウィリアムのいたずらは、
ここ
第2回 「単一代入」と「末尾再帰」
http://itpro.nikkeibp.co.jp/article/COLUMN/20060912/247768/
SICP(「計算機プログラムの構造と解釈」)にも20ページに、
再帰的手続きとして記述してあっても、固定スペースで実行できる。この性質の実装
という風に出ている(おお、こんなに難しく説明するか ^^;)
ウィリアムのいたずらの上の説明で、初めてみた・・・
という人もいるかもしれません。
うーん、みんな負け組みです・・(>_<!)
放送大学の「情報科学の基礎('07)」を、学習センターのDVDで見てびっくり!
その授業の5回から、8回まで、高岡詠子先生が担当なのですが・・
ぜったい、かわいいです!
というか、かわいい口調で話してます(^^;)
放送大学のテキストに出てくる写真とは大違いです!
アップになると、かわいいです。。
で、その先生が、末尾再帰について、LOGOを使って、やさしく教えてくれます。
(第6回、テキスト89ページ)
ちなみに、他の先生のときは、コラムでインタビューするときにも、現地に先生は行かないのに、
高岡先生のときだけ、フライトシュミレーターにのって、その様子が映し出されます。
うーん、これ、狙ってますよね!
カリキュラムを組んだ先生に感謝したい!って感じ
やっぱ、こーやって、
「かわいいせんせいに、やさしくおしえてもらう」
のが、勝ち組の学び方(^^;)
P.S ちなみに、放送大学の「情報科学の基礎('07)」は、10月(2学期)からは
土曜の16時00分~16時45分だそうです。
う、見れない(>_<!)用事があって・・・
6回は放送しちゃったんだろうか・・・・
ちなみに、「末尾再帰」は、名前だけ出てくるけど、
詳しくは教えてくれません。。。
(じゃ、だめじゃん (^^;)