1. はじめに

本研究は，再帰がなぜ人間の直観的な理解に合わず困難な課題であるのかについて， その原因を検討するものである．一般に，再帰はコンピュータ科学に精通している者を 除くとなじみの薄い概念である．そこで，本論文ではまず再帰とは何か，どのように 表現されるのかを説明する．その後，先行研究の概観と本研究での検討事項の記述を 行なう．

1.1 再帰とは何か

2枚の鏡が向かい合わせに平行に立っていると，その間においたものが鏡に映り， それが無限に続く「合わせ鏡」という現象がある．このように，あるものが部分的に それ自身で構成されていたり，それ自身によって定義されているとき，それは 「再帰的」 (recursive) であるといわれる[WirthWirth1986]．再帰は，論理的思考の 重要な特質のひとつで，数学では漸化式や数学的帰納法が再帰的構造を持っている．

再帰はコンピュータ言語においても存在し，実際に再帰的な処理を行なうことが できる．たとえば，ハノイの塔の操作手順やフラクタル図形は再帰的構造を持って おり，コンピュータ上でシミュレーションすることが可能で ある[市川市川1993,浪平浪平1997]．

ここで，コンピュータ言語や数学における再帰のように，その構造と処理を アルゴリズムによって表現，定義可能であるものを「論理的な再帰」と呼ぶことにし， 合わせ鏡のように日常的に見られる再帰と区別する．本研究では論理的な再帰を扱う．

1.2 LOGOと再帰

図: 正方形を描く手続きとタートルの動き

論理的な再帰は，再帰処理をもつコンピュータ言語を用いて以下のように表現される． LOGOでは，いくつかの命令をまとめて実行する形式があり，このようなプログラム を「手続き」(procedure) と呼ぶ．このとき，手続きの中にその手続き自身を呼び 出すことが可能であり，これを「再帰呼び出し」(recursive call)，または単に 「再帰」(recursion) という[PapertPapert1980,子安子安1987]．

たとえば，画面上のタートルを動かすLOGOの命令 (ディスプレイ上のタートルを 動かして図形を描くことができる「タートル・グラフィックス」という機能がある) を 使うと，正方形を描く手続きは図のようになる． 「てじゅんは しかく」 によって，「しかく」という手続きが「おわり」までで定義される．この「しかく」を 実行すると，タートルが前へ100歩進んで90度右へ曲がることを4回繰り返し，一辺の 大きさが100の正方形が描かれるのである¹．

ここで，図のように「しかく」という手続きの中に「しかく」という 手続きを再帰呼び出しすると，正方形を永遠に描き続けるプログラムとなる．

なお，このままでは手続きが無限に再帰呼び出しされるため，一般的には 「もし [ ]」という条件文を用いて終了状態 を設定する必要がある．

図: 再帰呼び出しとそのイメージ

図: 末尾再帰の手続きの例

図: 埋め込み再帰の手続きの例

つぎに，Kurland89にならうと，再帰呼び出しの位置によって 「末尾再帰」(tail recursion) と「埋め込み再帰」(embedded recursion) の2つに 区分可能である．末尾再帰は，手続きの最後に再帰呼び出しが置かれている形の再帰で ある (図)．たとえば，「さんかくしかく 100」として実行すると， 1辺100の正方形，1辺100の正三角形，1辺50の正方形，1辺50の正三角形の順に 描かれる (付録A.の図参照)．

埋め込み再帰は，手続きの途中で再帰呼び出しされる形の再帰である (図)．「さんかくしかく 100」として実行すると，1辺100の正方形， 1辺50の正方形，1辺50の正三角形，1辺100の正三角形の順に描かれる (付録A.の図参照)．

このように，手続きの構成要素が同じでも再帰呼び出しの位置によって，その処理順序 は大きく異なったものとなる．