この用語はまだ監査を通っていません（未確認）。
再帰アルゴリズム
さいきあるごりずむ ／ 再帰 1対1で対応recursion
名詞 ・話し言葉 別の言い方 recursive algorithm
式と読み方
the gcd of a and b equals the gcd of b and a mod b
定義
問題を同じ形のより小さな問題に分け、自分自身を呼び出して解く手順（再帰）。いちばん小さな場合（基底）は直接答えを返す。
A procedure that solves a problem by calling itself on smaller instances of the same problem. The smallest cases, called base cases, are answered directly.
例文
話し言葉 The idea of recursion is that the function calls itself on a smaller input, so you always need a base case or it never stops. 再帰の考え方は、関数がより小さな入力で自分自身を呼び出すこと。だから基底の場合が必ず要る。無いと止まらない。
書き言葉・答案 Write a recursive algorithm that computes gcd(a, b), and use it to find gcd(252, 198). gcd(a, b) を計算する再帰アルゴリズムを書き、それを用いて gcd(252, 198) を求めよ。
言い間違えやすいところ
- recursion は「再帰」という考え方全体、recursive algorithm はその考え方で書いた手順。Levin は数列の節（4.1 Describing Sequences・4.4 Exponential Sequences）でも recursion を使う（各 1 件）。
- 日本語の「帰納的」も「再帰的」も英語では recursive になることが多い（帰納的定義 = recursive definition）。
- 用例コーパスで recursion は話し言葉のほうが多く（ほとんどが MIT OCW）、書き言葉には少ない。recursive algorithm は話し言葉・書き言葉とも少ない（すべて MIT）。