【問題15 その2】再帰を実現するコンピュータの仕組み：完全マスター！ 組み込みC言語プログラミング（17）（2/2 ページ）

C言語のプログラムにおいて、関数が関数内で自分自身を呼び出すことを「再帰」と呼び、whileやforを使わなくても繰り返しのプログラムを書くことができます。再帰を実現するコンピュータの仕組みとともに身につけましょう。

[横田一弘 埼玉県立新座総合技術高等学校 教諭，MONOist]

プログラムの実行とは

　マイコンのように小さいコンピュータのプログラム開発では、コンピュータの資源を有効活用するための知識が必要です。ここで基礎となる、C言語のプログラムの実行の仕組みを確認しましょう。

　C言語で書かれたソースプログラムはCコンパイラによって機械語に翻訳され、結果、プログラムファイルが作られます。プログラムファイルはWindowsでは拡張子が.EXEのファイルで、例えばアイコンをダブルクリックすることで起動します。プログラムの起動はHDD（Hard disk drive）などに記録されているプログラムファイルをメモリに転送し、CPUの使用権を得ることを言います。

プログラムの実行イメージ

　コンピュータで実行中のプログラムはメモリに置かれます。CPUはメモリに記録された命令を1つずつ読み取って、解釈・実行するハードウェアでプロセッサとも呼ばれます。CPUとメモリはバスでつながれていて、プログラムやデータのやり取りを行っています。

　メモリ上のプログラムは「コード領域」「データ領域」「スタック領域」から構成されます。コード領域は機械語の命令が格納される領域で、プログラム領域やテキスト領域とも呼ばれます。データ領域はデータが置かれる領域で、静的記憶域期間をもつ変数が存在する領域です。スタック領域はプログラムを実行するための作業領域ともいえるもので、自動記憶域期間をもつ変数は、この領域に割り当てられます。

関数呼び出しとスタック

　それではconvert.cを例に、コンピュータで関数がどのように実行されるのか調べてみましょう。

　プログラムはmainから開始されます。mainにはn、b、strの3つの変数があって、すべて自動記憶域期間をもつ変数、すなわち「自動変数」です。これらの変数はmainの開始時にスタック領域に割り当てられます。

　スタックとは、コンピュータで用いられるデータ構造の一つで、データを入力すると上へと積み重ねられます。反対にデータを出力するときは、最も上のデータから出力されます。後に入力したデータが先に出力されるので、スタックはLIFO（Last In First Out）の構造で保持するメモリです。

　convert.cのmainの場合、n、b、strはスタック領域の下（下位番地）から積み重ねられるように配置されます。配置されると「スタックの底」は上（上位番地）へと移動します。

　関数呼び出しにおいて、C言語では引数を値で渡します。mainではconvertを呼び出しますが、事前に引数の値をスタックに積みます。続いてmainへの戻り番地がスタックに積み、その後convertへと処理が移ります。

　convertの仮引数s、num、bは、スタックに積まれた値をアクセスするものです。

　convertはいずれ処理を終えてmainに復帰します。スタックにはmainへの戻り番地が記録されているので、それを元にmainへと復帰します。さらにスタックの底をconvertが呼び出される以前の位置に移動し、復帰は完了します。

再帰呼び出しとスタック

　以上で説明したとおり、自動変数や関数の引数はスタックに割り当てられます。ですから例えば自動変数にあまりに大きい配列を使うとスタックが不足するエラーが生じます。マイコンのように小さいコンピュータでは、なおさら心配です。

　また、再帰もスタックを消耗する原因となります。convert.cでは、_convertが再帰呼び出しされる毎に、スタックに引数と戻り番地が積まれていきます。マイコンのプログラムでは再帰を用いない方がよさそうです。

問題16

　それでは、次回の宿題です。

問題16：

何月かを入力し、その月を表す英語を表示するプログラムを作ってください。⇒解答と解説は次回

お知らせ

「CADLUS+Arduino電子工作ガイド」

本連載「完全マスター！ 組み込みC言語プログラミング」も好評掲載中の横田氏による書籍「CADLUS+Arduino電子工作ガイド」（オーム社）が発売中です。

Arduinoと無料プリント基板CAD「CADLUS PCB」を組み合わせた電子工作の手法を示すもので、実際にサンプルを示しながら、プリント基板の設計、作成から組み立て、プログラムまでを手順を追って解説しています。