総和

[課題1・1]　1からnまでの和、$\sum_{k=1}^n k$を求めよ。

最初の議題として、1からnまでの和を求めるプログラムを作成することにします。この問題をコンピュータにやらせる場合、第1段階として、問題を次のようにおおまかに分解します。このとき、直接コンピュータが理解できるかできないかは考えません。

• 正の整数nを入力する


• 1＋2＋・・・＋nを計算する


• 上の計算結果を出力する

最後の出力命令は、コンピュータの基本命令の中に存在します。これ以上、ここでは詳細化しないことにします。ただし、その形式は人間のように融通がきくものではないことに注意してください。望むような形式で出力を行いたいときは、やはり、コンピュータにそのための手順を詳細に指示しなくてはなりません。

1番目の命令は、一見これ以上細かくすることができないようにみえますが次のように細分化しなければなりません。入力したnの値が正の整数である保証はありません。

• nを入力する


• nの値が正か調べる

この順序は変えられません。nの値が入力されない限りは、正負の判定ができないからです。次に、nの値が正でないとき、どうすればよいかも考えなくてはなりません。ここでは、強制的にプログラムの実行を終了することにします。これは本来の目的とはあまり関係ないことのようですが重要な問題です。プログラムの間違いをなくし信頼性を増すためにも、「nに負の値が入力されるはずはない」というような、思い込みを持ってはいけません。

下線部:亀田

うわあ、これ全部を「プログラムを書く前に」考えるんなら、確かにプログラム書くのは億劫でしょう(笑)。すげえな(苦笑)。これ読んでたらさすがに「大仕事」に感じて嫌気が差してきます(笑)。
いや、間違っちゃいないでしょう。確かに言ってる事は正しい、です。
でも、僕だったら「いきなり書き始め」ますね。何も考えません(笑)。
僕みたいに「いきなりコードを書き始める」スタイルを、ラピッド・プロトタイピング(rapid prototyping)と呼びます。そして、今はそっちの方が「流行り」なのです。
ラピッドプロトタイピング、と言うのは、「速い試作品化」って意味です。元々UNIXなんかでも

できるだけ早く試作を作成する

Mike Gancarz

のがベストだと言われています。
ちょっと長いですが、UNIXという考え方―その設計思想と哲学と言う書籍から引用してみましょうか。

「できるだけ早く」とは、本当に「できるだけ早く」ということだ。「大至急」だ。アプリケーションの立案に少しの時間をかけ、あとはまっしぐらに進むだけだ。命をかけてコードを書く。端末が熱いうちにキーボードを打つ。1ナノ秒も無駄にする時間はない。
この考えは、多くの人が考える「正しい設計作法」と真っ向から対立している。ほとんどの人は「アプリケーション設計を完全にしてからコーディングにかかれ」と教えられている。「まず、機能仕様書を書かなくちゃ」と言う。定期的なミーティングで方向性を確認する。細部まではっきりさせた考えを設計仕様書に書く。90パーセントの設計ができて始めてコンパイラを使う。
原理的には、もっともな指針に聞こえる。しかしこの考え方は、試作というものの重要性を見過ごしている。あるアイディアがものになりそうかどうか、目に見える現実的な場面でテストするには試作が一番だ。試作以前のアイディアは、これはこう動くはずだという憶測の域を出ない。この時点では、設計構想はほとんど理解されておらず、おそらく人によって解釈が異なっているだろう。プロジェクトの前進には、全員の合意が必要だ。試作は、具体的に目標を示すことで全員の合意を醸成する。

ほら、全然真逆の事書いてるでしょう(笑)。
実は、UNIXなんかは「そんなに窮屈な」システムでも無いんです。もちろんその延長線上で言うと、C言語さえ「そんなに窮屈な」言語でもありません(もちろん難しいですが)。
大事なのは「やっつけ仕事」なんです。そして、UNIXにはその「やっつけ仕事用」のツールが山ほど揃ってるのです。
さて、「いきなりプログラムを書き始められる」のは僕が頭が良いから、でしょうか?あるいは慣れてるから?どっちも違いますね。単に「やっつけ仕事で早く目的に達成できる」ツールをプログラミング言語として選んでいるから、に過ぎません。
もう、PythonやRubyを弄ってみた人なら分かるでしょうが、通大御用達の「疑似プログラム」で「紙の上に」プログラムの流れ、なんて書くよりもPythonやRubyで「いきなり」書いちゃった方が速い、ってのは何となく分かったでしょう。それが下手な「プログラム設計書」より良い、と言う事が。「紙の上に」疑似コード書いていったって「実際に動く」わけではありません。反面、PythonやRubyなら「紙の上に」疑似コードを書く程度の労力で、しかもコッチの方は「目の前で動く」んです。どうしてPythonやRubyが「動く疑似コード」と呼ばれるのか、そろそろ分かってきたんじゃないか、と思います。
そして、そう言う言語の方が、今は人気があるのです。ラピッド・プロトタイピングが「21世紀型の」プログラミング法、なのです。
もちろん、システム・プログラミング(例えばOSとかのプログラミング)は同様な文脈では語れませんが、数値計算のプログラムを書く程度で……余計な脅しは必要無いですよね。

本来の目的とはあまり関係ない

ホント関係無い、ですよ(笑)。関係ない事は書くべきじゃないです。脅しが好きだなあ(苦笑)。
なお、一応ここでは「プログラムの実行を終了する」のではなくってエラーを返す方向で対処していきましょうか。

プログラムの間違いをなくし信頼性を増すためにも、「nに負の値が入力されるはずはない」というような、思い込みを持ってはいけません

そうか(笑)?まあ、そう言う部分もあるでしょう。
ただし、です。プログラマ側が「全ての入力値を予測出来る」ってわけでも無いでしょう。だったらいきなり「文字」を入力されたら?どうすんだろ(笑)?
このテの問題は、ラピッド・プログラミングの文脈では「問題が起きてから修正する」方が結果効率的、なんです。大体、プログラミングの世界では「ユーザーはいつもプログラマが予測もしないソフトウェアの使い方をする」と言う格言がある程、なんですよ。全ての「禁じ手」を列挙しよう、ってのは土台無理なんです。
大体、ここでやってんのは「個人で使う」数値計算プログラムでしょ?しかも学科が「数学コース」ですし。何かの「商用製品」作ろう、とかじゃないんです。
あんま脅しても良い事ないんじゃないの?とか思うんですけどね。
気楽に行きましょうよ(笑)。「お気楽プログラミング」がここでのモットーです。

2番目の命令をどのようにすれば、コンピュータに理解できるものにすることができるかを考えます。ところで、

1＋2＋3＋・・・＋n
＝(((((0＋1)＋2)＋3)・・・)＋n)

が成り立つことに注意しましょう。この式の右辺は、演算"＋"が2項演算であることを認識し、演算の順序まで考えた記述です。コンピュータに計算をさせるときは、この演算の順序が重要な意味をもつことを常に意識しなければなりません。

いやいやいやいやいやいや。ちょっと待て。
確かに

1＋2＋3＋・・・＋n
＝(((((0＋1)＋2)＋3)・・・)＋n)

は正しいですし成り立ちます。んでもそんな考え方普通のプログラミング言語でするか?
ちょっと待て。

しかし、ここでハタ、と気づく。

「これってSchemeだったら正しい解説だよな……。」

実際、Schemeの書き方として以下のやり方はアリです。

(+ (+ (+ (+ (+ 0 1) 2) 3)・・・) n)

確かにそう言う考え方はします。
でもこの奇妙な一致は何故?
もうちょっと先を読んでみましょう。

ここで、変数"和"を用意して、命令

• 和←和＋k

を実行すれば、変数"和"の中の値がkだけ増加します。したがって、最初に変数"和"の値を0にしておき、その値を2増し、3増し、・・・、n増せば、最終的に求める結果が変数"和"の中にあることになります。すなわち、次のように分解された命令を、順番に実行すればよいことになります。

• 和←0


• 和←和＋1


• 和←和＋2


• 和←和＋3


• ・・・


• ・・・


• 和←和＋n

最初に変数"和"に0を代入していることに注意しましょう。変数に最初から0が入っているという保証はありません。
さて、コンピュータは数学等でよく使う省略≦である"・・・"を使って、上のように命令を与えても理解できません。しかし、これは同じことの繰り返しを表現しているのですから、制御構造の1つである反復を使って次のように記述することができます。

• 和＝0


• kを1からnまでとして次を繰り返す
  {
  
  
  
  • 和←和＋k
  
  
  
  }
  

下線部:亀田

がああああああああああああああああ!!!!!!!
ダメだ、もう我慢が出来ません(笑)。

確かに上の通大用語である「疑似プログラム」の通り書けば良いのは明らか、です。
が、その「繰り返し」をさせる辺りが初心者が躓くトコなんじゃないのか???

ちょっと下線部引いたトコに注目して下さい。
これら抜き書きして見ると手順としては次の3段ステップになってる事が分かるでしょう(0≦k≦nと言う変位幅である事に注意して下さい)。

1. 入力nがn<0の場合は計算が不可能である。


2. n＝0の時は和＝0である。


3. 和←和＋n

もうこうなると、Schemeユーザーとしては次のように書いちゃうのです。一回コード提示しておきますが、上の3ステップとの対応を(Scheme選んだ人以外も)見てみてください。

(define (Summation n)
(cond ((< n 0) (error n))              ;手順1
      ((zero? n) 0)                    ;手順2
      (else (+ (Summation (- n 1)) n)) ;手順3←ここが重要!!!
      ))

これで実は[課題1・1]はもう解けちゃってる、んです。「ウソ????」って思うかもしれませんが、本当です。
念のため、もう一回だけ、上のSchemeコードを手順に書き換えてみます。

1. 入力nがn<0の場合は計算が不可能である。：0以下のnが入力されたらエラーを返す。


2. n＝0の時は和＝0である。：nが0だったらそのまま0を返せば良い。


3. 和←和＋n：n番目のSummationはn-1番目のSummationにnを足したものである(ここが重要!!!)。

3番目が大事なのが分かるでしょうか?分かんなかったら上のSchemeコードの4行目を目に穴が開くほど見てください。
これは数学的には次と等価なんです。

$$a_{n} = a_{n-1} + n$$

これをプログラミングの用語で再帰(recursion)と呼びます。そして、数学の用語では帰納(induction)と呼びます(※)。
そして、上のSchemeのコードの一つの特徴は、「分岐」を使っているけど全く「反復」を使っていません。と言うか、「反復は分岐で書くことが出来る」と言うのを指摘した事を覚えているでしょうか?これが「プログラミングに於ける制御の基本2構造で十分だ」と言った最大の理由です。数学では「反復」はいらないのです(が、再帰を用いると自然に反復を表しているのです)。
また、通大のテキストのここまでの解説は、中心的な部分を抜き出してみたら、原理的にこの「再帰」を説明していて、Scheme等のLisp系プログラミング言語での説明だったら「ピッタシカンカン」なんです。
何でこんな事が起こっているのでしょうか?種明かしをしましょう。

亀田が初めてこのテキストを読んだ時、

この説明はLispやSchemeだったら合ってるのにな。

と感じました。
先にも書きましたが、

計算モデルを論じるのだったらLisp系言語が最適

なんです。かつ、明らかにこの数値計算のセクションでは「Lispっぽい説明」が随所に見られます。
学生に「数値計算モデル」を最速で教えるにはLispが最適である。特に薄い、分量が決まったテキストであればあるほど「Lispによる説明」の方が最速で効率的、なんです(だから多くの有名大学の授業ではSchemeが用いられているのです)。

「おっかしいなあ、何でだろ?」

と思ったら、このテキスト後半の筆者、菅原昭博氏、現玉川大学工学部電子工学科准教授のプロフィール見た時、謎が氷解したんです。

「謎は解けたよ、ワトソン君。」

そこにはこんな事が書いてあった。

東京工業大学大学院理工学研究科博士課程修了

「東工大か!!!!!」とか思って(笑)。
いや、東京工業大学、ってのは過去、Lisp専用のコンピュータ、通称「Lispマシン」の開発実績がある程の大学なんです。従って、「東工大」で「情報工学を学んだ」って事は当然Lispを知っています(恐らくSchemeも知ってますよ)。
このセンセ、「Lisp型の解説を」「Pascalでやろう」としてたんですね。道理で随所で歯切れ悪いのも当然だよ、と(笑)。結構、無茶苦茶承知でこのテキスト書いてるんですよ(笑)。
では、だったらどうしてScheme等のLisp系言語でこのテキストを書かなかったのでしょうか?理由は単純ですよね。1990年代初頭だから、だったんです。
当時のパソコンはとても非力だったんです。そして元々Lisp系言語は大容量のメモリとCPUパワーを必要とする言語で、「大型コンピュータ」でしか動かなかった、んです。パソコンで扱えるような代物じゃなかった、んですね。

大型コンピュータの例

PDP-11 名機、と呼ばれるミニコン(ミニ、とは言ってもコッチの感覚ではやっぱり巨大)である。大学/研究所で絶大な人気を誇った。これはまだ古い機械の部類だが、これを生産してたDECと言うメーカーはこの後もこのテの大型コンピュータを作り売りつづけていた。 なお、DECはそのうちCompaqに買収されて、そのCompaqもヒューレッド・パッカート社に買収された。

この辺で、「何故Lisp系言語が知名度が低いのか?」その理由も分かるとは思います。歴史的には、大型コンピュータを所有出来るような大学、なんてのは数が限られていましたから。国家から購入予算をぶんどってこれる大学と言えば……。そう言うわけ、なんです。そして当然東京工業大学なんてのはそう言う数少ない大学なのは間違いありません。
21世紀に入ってパソコンの能力が飛躍的に上がって過去の大型コンピュータの能力を遥に凌駕しています。要するに現代は、中学生〜高校生辺りでも「自宅で楽々Lispを扱えるようになった」空前絶後の状態なんですね(考えてみれば、亀田が90年代に人生初めて購入したパソコンなんかは、今ではUSBメモリに丸まる入ってなお余ります・笑)。
一般人の逆襲はこれから、です(笑)。パソコンの能力が桁違いに上がった以上、もはや大学/研究機関じゃなくっても彼らが愛用している「便利ツール」は自宅でも楽々扱えるのです。

取り合えずこのテキストの特徴と言えば「Lisp系言語っぽい説明を」「Pascal(を模した疑似コード)で無理矢理やろうとしている」って事です。これを把握しておいてください。解説がチグハグで、プログラミング未経験者が「分かりづらい」って思うのは当然、なんです。
多分このセンセもLispで書けたら書きたかった、ってのが本音なんじゃねえのかな、とか思います。時代がそれを許さなかった(そしてパソコンではPascalが当時はそこそこ人気があった)、って事なんでしょう。

では、再帰はPython、Ruby、R辺りでも使えるのか?使えます。元々Lisp系言語の影響受けてるんで、これらの言語はこう言うのも大得意、なんですよ(笑)。ちょっと書いてみましょう(Schemeが苦手だ、って人はこっちの方が分かりやすいでしょうし)。

# -*- coding: utf-8 -*-
# Pythonの場合

def Summation(n):
  if n < 0:
      raise ValueError
  elif n == 0:
      return 0
  else:
      return Summation(n - 1) + n　# この部分が再帰

# Rubyの場合

def Summation n
if n < 0
  raise
elsif n == 0
  0
else
  Summation(n - 1) + n  #この部分が再帰
end
end

## Rの場合

Summation <- function(n) {
if (n < 0) {
  return(NA)
}
else if (n == 0) {
  return(0)
}
else {
  return(Summation(n - 1) + n) # この部分が再帰
}
}

こんな感じですね。何を行っているのか、もう分かりますね?「現在設計している関数内」で「作っている最中の関数を(nを一個減らして)呼び出している」のです。
比べてみると……この中で一番シンプルなのはRubyかしら?Pythonだと明示的にreturn噛まさないとエラーになるんですが、一方Rubyではへっちゃらけのけ、ですね。コードの見てくれ、そしてタイピング量は結果一番短いと思います。Rもまあまあ、ですね(C言語っぽさは、やっぱり個人的には好きじゃない、んですが・笑)。
そして、最初の方に掲げた「Summation」、あれらは通大のテキストのPascalのコード例にわざと合わせた、んですが、こっちの「再帰版」の方が遥に短くシンプルに書けてるのが分かると思います。もちろん入出力の分も引数と返り値で解消しているんで当たり前なんですが、forループ系を使うよりメンド臭くないのが分かるでしょう。数学的定義を厳密に置き換えれば一丁上がり、なのですから。ループであれこれ悩む必要が無い、のです。
前の方で「一生何らかの形でプログラミング言語と付き合っていける事を目標とする」と書きました。んで、別にここに掲げた言語じゃなくても構わないんですけど、プログラミング言語を選ぶ際、大事なポイントが一つだけあります。世の中にはオブジェクト指向言語であるとか、新しくはアスペクト指向言語とか、まあ、色々あるんですけど、その辺はどうでも良くって、一番注目しなければならない事は次の一点です。それは

再帰を難なく扱えるプログラミング言語が良い言語

です。再帰を扱うのが難しいプログラミング言語はそもそも勉強するに値しません(例えばVBAとか)。これは絶対的な鉄則です。
何故なら、高級言語を使う目的は「短くコードを書けるから」の一点なんですよ。ここの数列の和の例を見れば分かる通り、forループを使うより再帰を使った方が簡単なんです。これは一体何を表しているのか?
反復ってのは「コンピュータは得意」ですが、元々人間は「反復が嫌い」なのです。従って、「反復を考える」事自体が苦痛です。書くのも嫌ですし、そもそも人間の思考回路としては「反復は不自然」なのです(だからプログラミング初心者にとっては、ループを書く事が一番難しく見えるのです)。
再帰を使う方が単純で済むのに「ループ構文を書かなければならない」と言う事は、これはそもそも人間が「ループ構文を書く」事によって一種「(プログラミング言語の為の)人間コンパイラになっている」って事ですね。「機械が得意な事は機械にやらせれば良い」のだったら、人間が反復を考えるんじゃなくって、「勝手に反復に翻訳してくれる」プログラミング言語を使った方が良い、と言うのは自明でしょう。
よって、プログラミング言語を選択するにあたって一番重要なのは「再帰を簡単に書けるかどうか」をチェックする事になるんです。

注:なお、これが人間の不思議なところなんですが、先にも書いた通り、プログラミング初心者が、必ず最初に躓くのがとにかく「反復」なのです。しかし、「反復をガリガリ書く」練習をしてしまうと、今度は「反復は簡単だけど再帰は難しい」と言う風に概念が「逆転」してしまうんです。慣れってのは恐ろしいモノです(笑)。
事実、多くのプログラミング言語の入門書ですと、最初に「反復」をガリガリ練習させておいて「反復思考の不自然さ」に初心者を慣れさせるんですが、反面、再帰の取り上げ方は「プログラミングの奥義」「難しい概念」っぽい扱いになっています。繰り返しますが、これは本来は逆なんです。再帰の方が実は簡単に書けて、スピードを稼いだり、メモリ効率を良くする為に、後により難しい反復で書き直すのが本来は正しいのです。こっちの方が順番から言うと人間にとって「優しい」のは間違いありません。
では、どうしてこう言う悪習(反復の後の再帰)が根づいたままなのか、と言うと、元々再帰の方が、工学的に「コストがかかってた」からなんです。過去のハードウェア上の制限への対応が今も引きずられているから、に過ぎません。そう言う古い時代にプログラミングを覚えた人たちがプログラミング入門書を書くと、やっぱり「反復の方が簡単だ(慣れちゃったから)」「再帰はコストがかかる(今じゃ大したコストじゃないのに)」と言う思考から抜けきれないまま初心者に語る羽目になるわけです。確かにそれは、ある種のプログラミング言語(例えばC言語やPascal)では「正解」ですが、その他では「それほどでもない」無駄な「方便」になってしまってるのです。
と言うわけで、ここではより自然な「再帰」に最初に慣れるべきだ、って事を言っておきます。特にプログラミング初心者こそ「再帰」を最初にやるべきです。少なくとも作成すべきコードと数学とが一対一対応になりやすいんで「ややこしい思考の強制」は極力減ります。そして「徐々に」反復に慣れていった方が遥に「学習がラク」です。これが「Lisp系言語の知恵」なのです。

さて、こう言う風に、原理的にはここまでは背後ではLispっぽい「再帰」ベースで解説されてるのが通大のテキストなんですが、これ以降の疑似コードでPascal調の「疑似プログラム」が提示されています。今までの話を鑑みながら読んでみてください。どっちがより複雑で技巧的なのか、分かると思います。

これまでをまとめると、目的のプログラムは次のようになります。

• プログラム　　「1からnまでの和」
  
  変数　n, k, 和:整数型
  
  {
  
  nの値を読み込む
  もし　(n≦0)　ならば　プログラム終了
  和←0
  kは1からnまでとして次を繰り返す
  {
  
  和←和＋k
  
  }
  
  和の値を出力する
  
  }
  

なお、実はPascalでもC言語でも「再帰」は可能です。ただし、一般的にメモリ管理が無茶苦茶難しくなります。
また、十進BASICなんかでも

再帰呼び出し可能な手続き定義

組込み関数にない関数は，DEF文のほか，複数行での記述が可能な関数定義を用いて利用者自身が定義して用いることができます。また，副プログラム定義を利用すれば，アルゴリズムを定義しておき，それを呼び出して利用することができます。関数定義や副プログラム定義のなかで自分自身を利用することもできるので，再帰的なアルゴリズムも簡単に実現できます。

とか書かれているんですが、どうなんでしょうねえ?
こんな感じか。

REM 十進BASICの場合
DECLARE EXTERNAL FUNCTION Summation
INPUT n
PRINT Summation(n)
END
EXTERNAL FUNCTION Summation(n)
IF n<0 THEN
 LET Summation$="ERROR!"
ELSEIF n=0 THEN
 LET Summation=0
ELSE
 LET Summation=Summation(n-1)+n
END IF
END FUNCTION

まあ、出来なくはないけど……。何じゃこりゃ、ゴチャゴチャしてて汚ねえなあ(爆)。
大体、外部関数定義、って何やねん(苦笑)。そもそも何で「必ず」入力命令経由しなきゃなんないんだか(笑)。不自由過ぎるにも程があります(苦笑)。
一つ提案。上の十進BASICヴァージョン見れば分かりますが、、一応十進BASICでも再帰は可能なようなんで(ホント一応、ですが)レポートやテストを「全部再帰で書いて」提出してやれや(笑)。
いくら何でも「91年製のテキスト」を現行で使いつづける、ってのはダメとしか思えないので、そう言う「反逆」もアリだよ、って事です(笑)。何せ「動くことは動く」んで減点のしようがありません(笑)。
そう言う形で、

「再帰はメモリ効率が悪い」

とか言ってきたら

「僕等、メモリ効率とか習ってませんから」

とか言い返せます(笑)。そもそも「再帰がダメ」とか減点してくる教授がいたら、そいつら本当に「ダメ教官」で確定ですし(笑)。いや、ホント、マジな話ですよ、これ(笑)。
まあ、もっともPython、Ruby辺りやったら十進BASICで何が何でも書きたい、とか思わなくなるでしょうけどね。「どうせだったらCかPascalの方がマシっぽい」とか思うようになるとは思います。その辺がレポートで「使いたい」って思う言語になるでしょうね。

---

[課題1・2]　次の一般項を持つ数列{$a_{k}$}の、第1項から第n項までの和を求めよ。

$a_{k} = k^2 + \sqrt{k}$、k = 1, 2, 3,・・・

もうこの辺も、前問題解ければ別段難しくないでしょう。
「整数型」も「実数型」もこれらは静的型付け言語の話なんで、動的型付け言語には一切関係ありません。まずは「ロジックが正しくて」「動くことは動く」と言う事を確認してから、C言語やPascalに「どうやって翻訳しよう?」って考えれば良い。ロジック自体はどんな言語にも移植可能なわけですから、それ以外の「言語特有の部分で」初めて「型」を考えれば良いのです(しかも十進BASICでは型を考えなくて済むし)。最初に知らなければならない事は、「どんな結果が返るか?」です。
その辺に「動く疑似コード」を使う利点がある、のです。

# -*- coding: utf-8 -*-
# Pythonの場合

import math                             # これがPythonの場合必要

def Summation(n):
  if n < 0:
      raise ValueError
  elif n == 0:
      return 0
  else:
      return Summation(n - 1) + n ** 2 + math.sqrt(n)

# Rubyの場合

include Math                    # これがRubyの場合必要

def Summation n
if n < 0
  raise
elsif n == 0
  0
else
  Summation(n - 1) + n ** 2 + sqrt(n)
end
end

;; Schemeの場合

(define (Summation n)
(cond ((< n 0) (error n))           
      ((zero? n) 0)
      (else (+ (Summation (- n 1)) (expt n 2) (sqrt n)))
      ))

## Rの場合

Summation <- function(n) {
if (n < 0) {
  return(NA)
}
else if (n == 0) {
  return(0)
}
else {
  return(Summation(n - 1) + n ^ 2 + sqrt(n))
}
}

さて、一つだけ注意点があります。
PythonとRubyの場合、(ある意味)欠点があって、それは「平方根を取る」と言う簡単な数学的操作でさえ、「数学関係のライブラリ」をインポートしないと使えない、と言う事です。
この辺、言語設計者の好み、ってのもあるんですが、ある主義によると「言語の中核部分はなるべく小さくしたい」と言う流儀があるようで、Python、Rubyはその流儀に従っています。
確かに、通常のプログラミングに於いては「数学的な計算」ってそんなにやらないんですよ(笑)。そこで、Python、Rubyは「数学関係の機能」を本体から切り離しちゃっている、のです。よって、数学的計算をやる場合、明示的に「数学関係のライブラリを使います」と宣言しないとならないのです。
反面、Schemeは数学出身なんで、数学的関数はたくさん揃っています。また、Rは元々「統計解析用」なんで、当然数学的関数はそのままで使い放題なんですね。
平たく言うと、どうして高校数学の窓で紹介する言語としてPythonが最終候補から落ちたか、と言うと理由はそんなトコ、なんです。いちいち毎回import mathって書くのがメンド臭かったから、です(笑)。
(ここ、良く覚えておいてください。「メンド臭い」って言うのがプログラミングに於いて、如何に強力な理由になるのか、を・笑)
まあ、Python、Rubyは「数学には恒常的に使うにはメンド臭い」って思っただけで、日常用のプログラミング言語として、とか、情報工学系の初心者用言語としては、いずれにせよ優れているとは思います。

さて、余談ですが、こう言う「機能」の「本体との切り離し」、ってのはプログラミング言語設計に於いて、結構良く見かけるんです。
例えば。
一番典型的な例としては、やっぱりC言語がありますね。こいつはクセモノで、何と「本体だけ」では入出力機能さえ無いんです。
C言語で有名な「一番最初に書くべきプログラム」として、通称「HelloWorld」プログラム、って言うものがあります。単純に"Hello World!"って画面に表示させるだけ、のしょーもないプログラムですね(笑)。
典型的なHelloWorldプログラムは次のように書きます。

#include <stdio.h>  /* ここだ!!!これは一体何だ? */

int main(void)
{
  printf("Hello World!\n");

  return 0;
}

まあ、大体、プログラミング初心者はこのコード見るだけでも「わけが分からない」って不安に陥る、んですよ(笑)。どーしてたかが"Hello World!"って表示させる為だけにこんなにいっぱい書かなきゃならんのか?と。
やはり冒頭ですよね。ここです。

#include <stdio.h>

これで「入出力関係のライブラリをインポートします」って言ってるわけなんです。何せ、Cには入出力機能がない。先に見た、「Python、Rubyには数学的機能が本体には無い」と言うのと対比してみれば良く分かるでしょう。「必要となるライブラリは明示的に呼び出す」ってのがある種のプログラミング言語の流儀、なんです。
ちなみに、一番簡単なCのプログラムは次のようなプログラムです。

int main(void)
{
  return 0;
}

酷いでしょ(笑)?このプログラムは実は「何もしない」プログラムなのです(笑)。入出力が使えない、となると「これくらいしか」やる事無いんですよ。それは「何もしない」事です(笑)。
まあ、いずれにせよ、この「ライブラリのインポート」と言うのは、どのみちいつかは経験する羽目になるんで(例えばC言語とか、で)、Python、Ruby組は「数学やるときは数学ライブラリをインポートする」と念仏のように唱えてても良いでしょう。ここでもいずれ、もっと多用する羽目になるでしょうから。

さて、そこまで了承して、以降は流していきます。
上の4つの「走る疑似コード」をどうやってPascal(あるいはC言語)へと翻訳するのか、と言う説明だと考えれば以下はそれほど難しくもありません。結構重要なのは「型に関する」説明ですね。
また、Pascalとかが「如何にメンド臭い言語なのか」大変分かりやすい解説になっている、と思います(それはC言語に付いても、です)。

1段落目の問題の分解は、課題1・1と同様に、

• nを入力する


• $a_1 + a_2 + \ldots + a_n$を計算する


• 上の計算結果を出力する

となります。当然、問題となるのは2番目の命令です。$a_k$の値を求めることと、その値のk=1からnまでの和を求めることとは別々に分けて考えることができます。そこで、$a_k$の値を計算する実数値関数a(k)があるとすれば、実数型変数"和"を導入して、この課題のプログラムは、次のように書けます。

• プログラム　　「数列の第n項までの和」
  
  変数　n, k : 整数型
  　　　　和 : 実数型
  
  
  {
  
  nの値を読み込む
  もし　(n≦0)　ならば　プログラム終了
  和←0
  kは1からnまでとして次を繰り返す
  {
  
  和←和＋a(k)
  
  }
  
  和の値を出力する
  
  }
  

関数a(k)の仕様は問題の中に与えられています。したがって、そのサブプログラムをすぐに次のように書くことができます。

• 関数　a(k : 整数) : 実数型
  {
  
  $a \leftarrow k^2 + \sqrt{k}$
  
  }
  

前のメインプログラムとこの関数のプログラムを一つにして、課題1・2のプログラムとなります。
上の関数a(k)のプログラムは、なにも問題ないように見えますが、実引数に負の整数が与えられたときは、正しく機能しないことに注意してください。負の平方根は存在しません。今の場合、これを呼び出すメインのプログラムでは、実引き数として負の値を与えることは確かにありません。しかし、この関数を他のプログラムで流用したりする場合も考えて、メインプログラムのnの値の判定と同様に、引き数が本当に非負の値であるか検査する部分を追加することにより信頼性を増すことにします。このような姿勢によって、プログラムをコンピュータで実際に動かしたときでるエラー(実行時エラー)を減らすことができます。そこで、上の関数のプログラムを次のように書きかえることにします。

• 関数　a(k : 整数) : 実数型
  {
  
  もし　($k\le 0$)　ならば　プログラム終了
  $a \leftarrow k^2 + \sqrt{k}$
  
  }
  

この節では、同じ変数に繰り返し代入することで数学的にはΣを用いて表されるものを計算できることを学習しました。

<練習問題>

1. n!(nは非負の整数)を求めるプログラムを作成せよ。


2. 1.のプログラムにおいて、nが大きいとき整数型の最大値32767を超えるが、どのように処理すればよいかを考えよ。

<回答例>

1.においては0!=1である、と言う数学上の約束さえ思い出せば、今まで書いたプログラムを改造してすぐ作成可能です。
これもプログラミングの学習に於いて「再帰の例」としては良く使われます。
(つまり、通大のテキストのように「繰り返しで」書く事は滅多にありません。)

# -*- coding: utf-8 -*-
# Pythonの場合

def Factorial(n):
    if n < 0:
        raise ValueError
    elif n == 0:
        return 1
    else:
        return Factorial(n - 1) * n     # ここが再帰

# Rubyの場合

def Factorial n
  if n < 0
    raise
  elsif n == 0
    1
  else
    Factorial(n - 1) * n        # ここが再帰
  end
end

;; Schemeの場合

(define (Factorial n)
  (cond ((< n 0) (error n))             
        ((zero? n) 1)
        (else (* (Factorial (- n 1)) n)) ; ここが再帰
        ))

## Rの場合

Factorial <- function(n) {
  if (n < 0) {
    return(NA)
  }
  else if (n == 0) {
    return(1)
  }
  else {
    return(Factorial(n - 1) * n)                #ここが再帰
  }
}

まあ、試しにforループとかwhileループで書いてみてください。練習代わり、としては良いでしょう。
2.に関して言うと、動的型付け言語を使う以上「そんな事知るか!!!」です(笑)。その辺はプログラミング言語の方で回避出来る範囲では回避してくれるでしょうから(笑)。
真面目に考えると次の方策が考えられます。

• 単精度の整数型ではなくって倍精度の整数型を宣言して使う。


• あるいは、32767を超える最小のnを先に計算しておいて、そのn以上の数値が入力された場合、プログラムが停止するかエラーを返すかするように仕込んでおく。

辺りでしょうね。
なお、本格的な数値計算に於いては、

$$n! = 1 \times 2 \times 3 \times \ldots \times n$$

と言うのはなかなか大変な計算なのは確か、です。すぐ整数が巨大化してしまう。
こう言う場合、トリックとしては対数を取って、

$$\log{1} + \log{2} + \ldots + \log{n}$$

と和の形にしてしまう事が良く行われています。
と言うのも、

1. 浮動小数点型である対数の方が、数値の増加率を抑えられてコンピュータで扱いやすい。


2. 一般的にコンピュータでは、乗算よりも加算の方が計算スピードが速い。

と言う特徴があるから、なんです。必要になったら指数で元の形に戻す、と言うトリックを良く使います。
ここではそれを書きませんが(と言うか、すぐ書けるでしょう)、興味のある人は実装してみて下さい。

※:あるいは単に「漸化式」って言った方が通りが良いかもしれません。
なお、「再帰の方が簡単だ」と再三書いてますが、これは本当です。と言うことは、主張しているのは「漸化式が簡単だ」と言う事です。果たしてこれは本当か?数学が苦手な人間でも「漸化式が簡単だ」と思えるのかどうか?
結論から言ってしまえば「その通り」です。実は数学が苦手な人間でも漸化式自体にはあまり抵抗を示さないもの、なのです。

ウッソ〜〜〜〜!!!!!

と言う声が聞こえてきますが(笑)、本当です。
高校教育現場等で、数列が苦手、な生徒は事実大量に存在しているでしょうし、「漸化式なんか点数取れない分野だよ」って思う人もいるでしょう。はい、それは事実だと思います。ただし、そこに勘違いがあります。
「数学が苦手な人」が嫌なのは、「漸化式そのもの」が嫌いなんじゃなくって、「漸化式を"解け"」って言われるのが嫌、なんです。この二つは全然意味が違います。「解け」って言われた段階で、Σが出てきたり、計算が技巧的でメンド臭かったりで「嫌だ、と感じる」のが本当のところなのです。
十中八九、「漸化式の"意味"を述べよ」とか「書け」とか言われたら割にスラスラ読めるだけは読める/書けるだけは書ける、って生徒の方が多いだろ、と思います。連中は「解く」のが嫌なだけ、なんです(笑)。
これを鑑みると、「再帰」って方法論は「漸化式を設定して」、"解く"作業はプログラミング言語に丸投げ、って方法論です。一方、「反復」はΣの中身を想像して「動作を書き下す」と言うのが行われている内容です。果たしてどっちが楽なのか?と言うと「漸化式を作るだけ作っておいてあとは知らんぷり」の方が圧倒的にラクだろ、と思います。