Scratchで再帰関数の実装とメモ化をやってみた
最近、初学者へのプログラミング教育というテーマについて取り組むことが増えて来たこともあって、ちょくちょくScratchを触ってます。Scratch、教育用途のプログラミング言語としてとってもよく出来ていますし、全世界のScratcher（？）と作品を共有できるようなプラットフォームとしても実に素晴らしいのですが、個人的に不満なところが一つあります。ブロック（普通の言語でいう関数相当）が返り値を持つことができない点です。
もちろん、Scratchの作者が教育上の配慮としてあえてブロックの返り値という概念を削除したのは想像に難くありません。しかしながら、そのままだと素朴には再帰関数を書けない。
しんどい。
さらに、ブロックローカル変数もない。
しんどい。
というわけで、Scratchの「リスト」を使って、
- 返り値を格納するスタック
- オペランドスタック
をエミュレートするプログラムを書いてみました。
例題は再帰関数でありがちなフィボナッチ数を計算するやつです。ついでに、メモ化も実装してみました。しかし、こうしてみると、オペランドスタックや返り値のスタックが変化していく様子が可視化されて、これはこれで別の意味で再帰関数の仕組みを教えるのに教育上良いツールになるかもしれませんね（ならない）。
なお、Scratchのコードは以下から見ることができますのでご自由にお使いください。
