今回は，前回に引き続き，自分で関数を定義する方法を学びますが，今回の特徴は再帰的な 関数定義を扱うことです。
再帰的な関数定義とは，関数（f としましょう）の定義の中でその関数(f)自身が使われるような 定義の仕方のことです。あくまでも「定義の仕方」を区別する概念であり，「関数そのものの性質」
を区別するものではありません。
たとえば，
nの階乗
n!を求める関数
f(n)は，
n! = n*(n-1)!という関係式を利用して，
if文の中 で，
n=0のときは
f(n)=1で
n>0のときは
f(n)=n*f(n-1)と書けば，これは再帰的定義です。
一方，for ループの中で，p=1 を初期値とする変数
p に，p=p*i; という式を用いてi=1,2,…,n をつぎつぎと掛け算するコードを書けば，これは非再帰的定義です。
このように同じ関数でも再帰的定義と非再帰的定義があり得るわけですが，関数を再帰的に定 義したときに，それを「再帰関数」と呼びます。
再帰関数の多くは，上記の
n! = n*(n-1)! のように，数学的に自然な関係式をそのままＣ言語で記述したもので，決して難しいものではないのですが，コンピュータがこれをどのように実行する
のかを考え出すと，初心者にはかなり難しい面があります。今日の講義では，このような再帰関
数のコンピュータによる実行メカニズム（ふるまい）にも少し触れますが，あまり深入りしないことに
して，再帰関数の設計方法をノウハウとして学びます。また，「数学的に自然な関係式」とはいえ
ないような関係式を私たちユーザーが自ら考案する必要がある例として，累積テクニックと末尾
再帰という技術も紹介します。
このスライドの関数
sum(n) は，1から
n までの和を計算するものです。これはs=0 を初期値とする変数
s を用意し，for 文の中でs=s+i; を反復実行して，i=1,2,…,n をつぎつぎとs に足していくコードを書いても定義できます。しかし，このスライドの
sum(n) の中には反復実行のためのループ（for 文や
while 文）がなく，if 文が１つあるだけです。その中味をよく見ると，いま定義中の
sum を利用して（つまりまだsum の定義が完成していないのに）sum(n－1)を計算する部分が含まれています。このように，関数（この場合は
sum）の定義の中でその関数(sum)自身が使われるような定義の仕方のことを再帰的な定義といいます。また，再帰的に定義された関数を再帰関 数といいます。
この
sum(n) の定義を見ながら，再帰関数についての基本概念を説明します。まず最初の行に書かれている関数定義の見出し
int sum(int n)は，関数名が
sum，引数が
int n，および戻り値が
int型であることを示しています。この見出しに 加えて，プログラムのドキュメント（説明文書）あるいはプログラムのコメントの中に，この関数が「
何を」
(what)計算するものなのかを簡潔に書きます。
sumの場合は，「
1から
nまでの整数の和」
と書けます。これらの情報全体が関数の仕様を表します。
２行目からは，関数
sum を「どのように」(how)計算するか，その計算手順を書きます。書き方は基本的に前回学んだとおりですが，今回は再帰的に記述している点が異なります。つまり，if 文
の中で 「もし
n=1 ならば1 を返す」 は自明で問題ないとして，「そうでなければsum(n-1)+n を返す」 というところが再帰的になっています。再帰関数を呼び出している部分
sum(n-1) のことを再帰呼び出しといいます。
再帰関数
sum の定義は，数学的には sum(n) = 1 (if n=1)sum(n) = sum(n-1)+1 (if n>1)
と表すことができ，数学的に考察すると，この式は自然なものとして受け入れられるように思いま す。
しかし，この定義がコンピュータの内部でどう実行されるのか（ふるまい）は，初心者にはかなり 理解しにくい面があります。ここでは深入りせずに，概略だけを説明します。
このスライドを見てください。上記の数学的な定義に基づいて，sum(3) が次々と展開され，最
終的には
(1+2)+3 という式となり，これが計算されて6 が得られる様子を示しています。コンピュータはちょうどこれに相当する計算を巧妙な仕組みで行うのです。
その仕組みをもう少しコンピュータ寄りに描いたのがこのスライドです。
ここでは，コンピュータが１台で仕事を行うのではなく，main 関数と
sum 関数の実行主体を分けて考えて，それぞれを長方形として図示しています。さらに，sum の引数の値ごとに実行主体 を別なものと考えます。つまり，sum(3)，sum(2)，sum(1) の計算はそれぞれ別々の人が行うかの ように別々の長方形で図示しています。
コンピュータのふるまいに沿って，順に見ていきましょう。
１．まず
main 関数がsum(3) に仕事を依頼します。２．
sum(3)の中では
n=3となっていて，
sum(2)+3を計算するのが仕事です。そこで
sum(3)は
sum(2)
に仕事を依頼します。
３．sum(2) の中では
n=2 となっていて，sum(1)+2 を計算するのが仕事です。そこでsum(2)は
sum(1) に仕事を依頼します。４．sum(1) の中では
n=1 となっていて，境界条件が成り立つので，計算結果1 をsum(2)に返します。
５．
sum(2)の中では
n=2となっていて，計算結果
sum(1)+2 =1+2=3を
sum(3)に返します。
６．sum(3) の中では
n=3 となっていて，計算結果sum(2)+3 =3+3=6を
main に返します。ここで，
sum(3),sum(2),sum(1)というのは，実際には，必要に応じて
sum(n)の関数定義から作
られるコピーのようなものと思ってください。大事なことは，各コピーがそれぞれ独自にローカル
変数
nを持っているということです。それらは名前が同じ
(n)ですが，異なる変数で，それぞれ別
な値
(3,2,1)を保持できるのです。
再帰関数であろうとなかろうと，Ｃ言語のプログラミングというのは，一般に複数の関数を定義す ることがその中心的な作業です。しかし，初心者でもプロでも，関数定義の中に誤り（バグ）が潜 んでしまい，正しくプログラムが動作しないこと（不具合）が生じることがあります。プログラムに含 まれているバグの原因を突き止めて修正する活動のことをデバッグといいます。このスライドでは
，関数のデバッグについて，基本的な方法を紹介します。
デバッグの基本は，プログラムの実行が自分が期待しているように進んでいるかどうかを目で確 認することです。そのためには，プログラムの実行途中で変数の値を表示することが効果的です
。特に，関数の場合，その入口（実行の開始時点）と出口（値を戻す時点）での変数の値が重要 です。
このスライドは前のスライドの
sum関数をデバッグする例です。入口では，
printfを使って，引 数
nとして受け取ったデータを表示しています。表示の仕方は
call sum(3)
などとなるようにしています。
出口では，戻り値をいったん
ansという変数に代入し，その値を
return 6などと表示してから，実際に
returnによって値を戻して実行を終了するようにしています。
ここで示した
sum 関数はバグを含まないので，表示される内容は期待通りになりますが，もしバグが含まれていたら，期待と異なる表示がされるので，それをヒントとして，誤りの部分を突き止め
て修正することになります。
このスライドでは，再帰関数の設計方法を説明します。
基本的には，つぎの４ステップで作業を進めると良いでしょう。sum 関数を例とします。
(1)
まず，定義したい関数の見出しと意味（仕様）を簡潔な言葉で書きます。
int sum(int n)
= 1
から
nまでの整数の和
ここで最初の行はプログラムの一部となりますが，その次の行はコメントにするか，別途用意す るドキュメントに書きます。実際に「書く」ことが重要です。頭の中で「思う」だけではいけません。
(2) つぎに，再帰パターンを（何とかがんばって）発見します。再帰パターンとは，再帰呼び出し
の基本となる関係式のことです。
sum(n) = sum(n-1) + n (if n>0)
なぜなら，「1 から
n までの整数の和」＝「1 からn-1 までの整数の和」+ n だから。(3)
つづいて，上で求めた再帰パターンが無限に続かないようにするための境界条件とそのとき の関数の値（境界値）を求めます。
境界条件：n=1 境界値：sum(1) = 1
(4) 最後に，(1)(2)(3)で得た内容をまとめてＣ言語で記述します。その記述は多くの場合，スライ
ドに書かれているように，１つくらいの
if 文になります。境界条件が成り立つときには境界値を返し，そうでないときには再帰パターンに基づいて関数値を求めます。もちろん，数学的な設計段
階で
n=1 などと書いていたものは，Ｃ言語ではn==1 などと書く必要があります。これは最大公約数を求める関数
gcd(p, q) の再帰的定義の例です。（gcdは
greatest common divisor の頭文字）ユークリッドの互除法と呼ばれる方法に基づいていて，
p
と
qの最大公約数 ＝
qと 「
p÷
qの余り」の最大公約数
であることを使います。このスライドでは，本質的にはそれと同じですが，もっと単純に，割り算の 代わりに引き算を使って
p
と
qの最大公約数 ＝
qと
p－
qの最大公約数
（ただし，p>q とする。P<q のときは
p,qを交換した同様な式となる）
であることを使っています。
これをＣ言語で書き下すのは，皆さんの演習問題としておきましょう。
これまで，sum(n)=sum(n－1)+n という関係式に基づき，sum(n) を再帰的に定義しました。この定義のい やな点は，再帰呼び出しsum(n－1) が終わっても，まだ残された仕事（戻された値にn を足すこと）がある ことです。このスライドでは，再帰呼び出しから戻された値をそのまま関数値として返して実行を終了する（
つまり残された仕事がない）ような再帰（末尾再帰）を説明します。また，累積テクニックと呼ばれるプログラミ ング技術を合わせて紹介します。
スライドを見てください。1 からn までの和を求める関数sum(n) はsum_auxという関数（補助関数）を呼び 出して，それが戻した値を返すだけです。重要な仕事は補助関数が行っています。
補助関数は，ループを使ってacc=acc+k; を反復実行し，k=1,2,…,n をつぎつぎとacc （初期値は0）に足 していっても書けますが，この考え方を累積テクニックと末尾再帰を使って書いたのがsum_auxです。ルー プによる計算の「途中の状態」（現在の状態）は，一般につぎの２つの情報によって特徴付けられます。
１．ここまでの計算の中間結果（累積値）の情報。sum の場合はacc。つまり，1 からk までの反復加算の結 果。
２．ここからの計算が行う「残りの仕事」の情報。sum の場合はk+1 とn。つまり，さらにk+1 からn まで加算 する仕事。
補助関数sum_aux(acc, m, n) は，これらの情報を３つの引数として，最終的な計算結果を戻すものです。
ただし，２つめの仮引数をk+1 という式で指定することはできないのでm としました。この関数の意味は sum_aux(acc, m, n) = acc + m +…+ n
と表せます。再帰パターンは
sum_aux(acc, m, n) = sum_aux(acc+m, m+1, n) です。なぜなら，
acc + m +…+ n = (acc+m) + (m+1) +…+ n
