% 再帰

\documentclass{jsarticle}
\pagestyle{myheadings}
\markright{tmt's math page}
\def\baselinestretch{1.33}

\begin{document}

\noindent\textbf{再帰}

プログラミング学習において数学の知識は必要ない、とはよく言われる。これはもうちょっと正確に言う方がよいだろう。プログラミング{\textgt 自体}を学習するなら数学の知識は必要ない、ということだ。

プログラミング言語\.自\-\.体を学ぶ際、多くの言語は算数程度の知識があれば文法などを理解し身につけることは簡単にできるはずだ。で、それを元に何かしらのプログラムを書くわけだが、書くプログラム---すなわちコンピュータにやらせたいこと---が数学に無関係なら数学の知識は要らない。でも、コンピュータにやらせたいことが数学的な処理なら数学の知識は必要である。プログラム言語の文法を学ぶことと、プログラムによる処理の仕方を学ぶことは別物ということだ。

そんなわけでプログラミングの教本は、数学の知識を前提にしなくても学べるように書かれているものである。当然、コンピュータに処理させるプログラム例も数学を使わなくて済むものが載っている。

コンピュータの処理はプログラム言語によらず、逐次処理と分岐を組み合わせて行うので、教本も
\begin{enumerate}
\item 何かを入力して何かを出力する
\item 繰り返しの処理をする
\item 分岐の処理をする
\end{enumerate}
みたいなところから始めて、関数だのクラスだのといった複雑な処理に進むものだ。で、その途中で「再帰」呼び出しが登場することがある。

再帰って数学的処理のためにあるわけじゃないけど、数学的考えをプログラム言語に置き換えている。典型的なのは{\textgt 漸化式(ぜんかしき)}として実装できるものだ。たとえば
\[
a_n = n\cdot a_{n-1}\quad (n > 0),\quad a_0 = 1
\]
のようなものは、よく教本の例に挙げられている。言わずと知れた{\textgt 階乗}の定義である。ところで教本の中には、数学に縁のない人のために、数学的なことを一切述べずにプログラムの説明をするものだから、なんだかよく分からないまま通過してしまう人が続出する。そして結局、再帰を知らなくてもプログラムは組めるので、再帰のことなど忘れてしまうのだ。ああ、もったいない。

階乗の例をプログラム言語に置き換えるなら、数学では必須の添字表記は、あらかじめカッコ表記に直しておくとわかりやすい。つまりこんなふうに。
\[
f(n) = n\cdot f(n-1)\quad (n > 0), \quad f(0) = 1~.
\]

すると大抵の場合、これはこのままプログラム言語に置き換えられる。たとえばHaskellなら
\begin{center}
\verb| let f n = if n > 0 then n * f (n-1) else 1 |
\end{center}
と定義できる。数学的表記もプログラム表記もほとんど変わらないじゃないか。ちなみにHaskell流の表記『\verb|let f n = ...|』は、『\verb|f n|を\verb|...|と定義する』という意味だ。\verb|f 5|と入力すれば\verb|120|が表示される。

このような例は数学的に説明するとよいのだが、プログラム自体は小学生にも理解できる概念なので、教本が数学的なことを書かないのは理解できる。でも、数学的な考えが使われているものには、数学の話を持ち出すのが自然だと思うんだけどね。とは言え、私もそこかしこでこの原則を貫(つらぬ)いているわけではない。悪しからず。

\end{document}