再帰的なアルゴリズムの実例集

10
いいね
0
コメント

HMMNRST

2016年12月31日に投稿

再帰的なアルゴリズムの考え方に慣れるためにいくつかの有名な例を集めた。それぞれについてサンプルコードと「問題を小さくする方法」「終了条件」を記している。

注意事項：

アルゴリズムの細かい効率よりも、論理の分かりやすさに重点を置いている
問題の前提に沿わない入力（例えば負の整数や小数）のチェックは省いている
再帰的なデータ構造や再帰を除去する方法については扱わない
サンプルコードはRubyで書いている

基本的な再帰

階乗

「1からnまでの整数の積」と言われたらfor文などのループで書きたくなるが、再帰的な計算もできる。

factorial.rb

def factorial(n)
    return 1 if n == 0

    n * factorial(n - 1)
end

p factorial(5) #=> 120

問題を小さくする方法
- ひとつ小さい値(n-1)での計算結果に n を掛ける
終了条件
- nが0なら値は1。そう定めておくのが色々な状況で自然

最大公約数（GCD）

公約数を見つけて割っていく方法や素因数分解する方法は計算が大変。ユークリッドの互除法を使うと効率よく求められる。

gcd.rb

def gcd(a, b)
    return a.abs if b == 0

    gcd(b, a % b)
end

p gcd(1920, 1080) #=> 120

以下の説明では簡単のために a, b が0以上の整数であるとする。負の整数へ対応するにはサンプルコードの通り絶対値を返せばいい。

問題を小さくする方法
- aとbの最大公約数は、bとa%b（aをbで割った余り）の最大公約数と等しい。b > a%b なので第2引数は必ず元より小さくなる
終了条件
- bがゼロのとき、aが最大公約数。ちょうどa%bがゼロ除算で計算できない
備考
- 数学的な説明のときは a ≧ b という前提をおくことがあるが、実装の際は考慮不要。a < b なら再帰呼び出しによって gcd(a, b) → gcd(b, a) → ... と自動で入れ替わる
- 再帰は十進の桁数の5倍以下で済むので、64bit整数（20桁）程度ならスタックオーバーフローはまず起きない
- 関数の最後の処理が再帰呼び出しである末尾再帰は、再帰を簡単に除去できる。コンパイラが自動で除去してくれる可能性がある

ハノイの塔

有名なパズル。3本の棒のひとつにささってピラミッド状に積まれているn枚の円盤を、大きさを逆転させないように1枚ずつ移動させて、全て別の1本の棒に積み直す手順を考える。~~重ねて収納する鍋と3ヶ所の収納スペースで試してもいい。~~

hanoi.rb

RODS = ["A", "B", "C"]

def hanoi(n, from, to)
    return if n == 0 # do nothing

    temp, = RODS - [from, to]
    hanoi(n - 1, from, temp)
    puts "move disk##{n} from #{from} to #{to}"
    hanoi(n - 1, temp, to)
end

hanoi(4, RODS.first, RODS.last)

output

move disk#1 from A to B
move disk#2 from A to C
move disk#1 from B to C
move disk#3 from A to B
move disk#1 from C to A
move disk#2 from C to B
move disk#1 from A to B
move disk#4 from A to C
move disk#1 from B to C
move disk#2 from B to A
move disk#1 from C to A
move disk#3 from B to C
move disk#1 from A to B
move disk#2 from A to C
move disk#1 from B to C

問題を小さくする方法
- 円盤の山を「上n-1枚の塊」と「下1枚」とみて考える
- 上側を仮置き場に退避させてから下側を目的地へ移動させ、上側を仮置き場から目的地に移動させる
終了条件
- 円盤が0枚なら何もしない。円盤の無いパズルというのは奇妙だが、認めれば短く実装できる
- それが嫌なら、円盤が1枚ならただfromからtoへ動かすだけ、と実装してもいい

分割統治法

大きな問題を小さな問題に分割してそれぞれ解き、結果をまとめて元の問題の解を得る手法。解法が分からないときの手掛かりになるだけでなく、計算時間が問題サイズに従って急激に伸びる場合には直接全体を解くより高速になることが多々ある。

分割してできた小さな問題をどう解くかは自由で、同じアルゴリズムを適用して再帰的に解いていくのが一番分かりやすい。分割できないところまで小さくするのがアルゴリズムとして綺麗だが、適度に小さくなった段階で別のアルゴリズムに切り替えたほうが高速だったりする。

クイックソート

一般的な用途では最も速いソート方法。

quick_sort.rb

def quick_sort(ary)
    ary = ary.dup   # preserve the input array
    n = ary.size
    return ary if n <= 1

    pivot = ary.delete_at(rand(n))
    ary_less_eq, ary_greater = ary.partition { |x| x <= pivot }
    quick_sort(ary_less_eq) + [pivot] + quick_sort(ary_greater)
end


if $0 == __FILE__
    ary = 10.times.map { rand(10) }
    puts "input:  #{ary}"
    puts "output: #{quick_sort(ary)}"
end

問題を小さくする方法
- 適当な値（ピボット）を選び、それより小さいものと大きいものに分けた配列を作る。ピボットを抜いておけば、分けた配列の要素数は必ず元より小さくなる
- 分けた配列それぞれをソートして結合するとソート完了
終了条件
- 要素数が0なら空の配列をそのまま返す¹。ピボットを選べないため再帰的処理が成立しない
- 要素数が1でも、ソート済みとみなせるので配列をそのまま返していい¹
備考
- 元の配列内で前後に要素を寄せれば、新しい配列を作らずに分割できて結合の手間もなくなる。それを再帰的に繰り返せば内部ソートとなる
- 分割した配列が同じ大きさになると高速だが、片寄り続けるとバブルソート並みに遅くなる
  - 単純な実装では、ソート済みの配列や全て同じ値の配列に弱いことがある
  - 最悪に近いケースでは再帰呼び出しも増え、スタックオーバーフローの危険がある（例：quick_sort([1] * 10**4)）

マージソート

分割統治法を使った別のソート方法。クイックソートは分割時の処理でソートするのに対し、マージソートは併合時の処理でソートする。ソートの性質も両者で色々と異なる。

merge_sort.rb

def merge_sort(ary)
    n = ary.size
    return ary.dup if n <= 1

    ary_left  = merge_sort(ary[0...(n/2)])
    ary_right = merge_sort(ary[(n/2)..-1])
    ary = []
    loop do
        if ary_left.empty?
            ary.concat(ary_right)
            break
        elsif ary_right.empty?
            ary.concat(ary_left)
            break
        elsif ary_left[0] <= ary_right[0] # stable
            ary << ary_left.shift
        else
            ary << ary_right.shift
        end
    end
    ary
end


if $0 == __FILE__
    ary = 10.times.map { rand(10) }
    puts "input:  #{ary}"
    puts "output: #{merge_sort(ary)}"
end

問題を小さくする方法
- 配列を2分割し、それぞれソートしておく
- 2つの配列を比較しながら小さい順に要素を抜き出していき、ソートされた1つの配列を作る
終了条件
- 要素数が0か1なら、配列をそのまま返す¹。分割しようとすると無限ループに陥る
備考
- 均等に分割できるので最悪ケースでも高速に動作する
- 自然と安定ソートを実装できる

高速フーリエ変換（FFT）

離散フーリエ変換（DFT）を高速に計算するアルゴリズム。データの「波」を扱う様々な処理を実用化する基礎になっている。

一口にFFTと言っても状況に応じて種類があるが、ここでは最もよく使われるCooley-Tukey型FFTを扱う。原理は難しいので説明を省くが、速度差を実感できるようサンプルコードにベンチマークを付属している。

参考：

FFT (高速フーリエ・コサイン・サイン変換) の概略と設計法: 1.2.3. 混合基数アルゴリズム
Cooley–Tukey FFT algorithm: 3. General factorizations

fft.rb

require 'prime'

def twiddle_factor(n, m)
    Complex.polar(1, -2 * Math::PI * m / n)
end

def dft(ary)
    n = ary.size
    w = n.times.collect { |m| twiddle_factor(n, m) }

    n.times.collect do |k|
        n.times.collect do |j|
            ary[j] * w[j * k % n]
        end.inject(:+)
    end
end

def fft(ary)
    n = ary.size
    return ary.dup if n <= 1

    n1 = Prime.instance.find { |p| n % p == 0 }
    n2 = n / n1
    return dft(ary) if n == n1

    w = n.times.collect { |m| twiddle_factor(n, m) }
    ary.each_slice(n1).to_a.transpose.collect! do |ary2|
        fft(ary2)   # length: n2
    end.collect!.with_index do |ary2,j1|
        # 0 <= j1 < n1, 0 <= k2 < n2
        ary2.collect!.with_index { |a,k2| a * w[j1 * k2] }
    end.transpose.collect! do |ary1|
        fft(ary1)   # length: n1
    end.transpose.flatten!
end


if $0 == __FILE__
    require 'benchmark'

    # test data: sin(kx)
    n = 2**3 * 3**2 * 5**2   #=> 1800
    k = 7
    ary = n.times.map { |j| Math.sin(2 * Math::PI * j * k / n) }
    puts "test data: sin(#{k}x)"
    puts "samples:   #{n}"
    puts

    # benchmark
    result_dft = result_fft = nil
    Benchmark.bm(5) do |rep|
        rep.report('DFT:') { result_dft = dft(ary) }   # slow
        rep.report('FFT:') { result_fft = fft(ary) }   # fast
    end
    puts

    # error
    def calc_error(n, k, result)
        return 0 if n == 0
        diff = result.dup
        diff[k]   -= -n / 2.0 * Complex::I
        diff[n-k] -=  n / 2.0 * Complex::I
        Math.sqrt(diff.map(&:abs2).inject(:+))
    end

    puts "exact solution: c[#{k}] = #{-n/2.0}i, c[#{-k}] = #{n/2.0}i"
    puts "DFT error: #{calc_error(n, k, result_dft)}"
    puts "FFT error: #{calc_error(n, k, result_fft)}"
    puts
end

問題を小さくする方法
- 長さ N=PQ のDFTは、長さ P のDFTを Q 回、長さ Q のDFTを P 回計算することで求められる。途中で回転因子 W を掛ける必要がある
終了条件
- Nが0か1なら変換後も同じ値¹。素因数を探す際に不都合なので最初に弾く
- Nが素数なら他のDFTアルゴリズムで計算する。分割しようとすると無限ループに陥る
  - n1 は必ず素数なので、if文にせずループ内で dft(ary1) と直接呼び出してもいい
備考
- Nが2の累乗のときは、細かく分割できるだけでなくほとんどの回転因子が±1で計算を簡略化でき、適切に実装すれば非常に高速となる

fft のメイン計算部分がごちゃごちゃしているが、簡単に言うと ary.each_slice(nx).to_a.xxx.flatten! という構造で、配列を一時的に2次元化して縦横にDFTを計算している。2次元配列の走査方向が入出力時で異なることに注意。

メモ化再帰

メモ化という手法を再帰計算に適用する。考え方は簡単で、「以前に計算結果をメモしたので答えを知っている」ということを再帰の終了条件に追加する。これによって、同じ部分問題を何度も解く羽目になるタイプの再帰アルゴリズムを高速化できる。特に最適化問題を再帰で解くときによく現れ、動的計画法の実現方法のひとつとなっている。

ちなみに、メモ化しただけではスタックオーバーフローは防げないが、あらかじめ小さい問題を解いてメモを埋めることでひとまず対処できる。

以下の例では、「メモが無ければ計算・保存したうえでメモの値を返す」という処理には ||= を利用している。これが利用できない状況では、ダミーの値などでメモの有無を判別して処理を分ければいい。

フィボナッチ数列

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... と、前2つの数を足すことで求まる数列。単純ながら色々なところで登場するので興味深い。（例えば、隣り合う数はユークリッドの互除法の最悪ケースとなる）

定義自体が再帰的なので再帰関数を実装するのは簡単。しかしそのままでは計算に時間がかかるので、メモ化を施す必要がある。

fibonacci.rb

$table = []

def fibonacci(n)
    $table[n] ||= begin
        case n
        when 0 then 0
        when 1 then 1
        else fibonacci(n - 2) + fibonacci(n - 1)
        end
    end
end

p fibonacci(30) #=> 832040

問題を小さくする方法
- 前項2つを求めて足す
終了条件
- nが0と1のときの値は決められている
備考
- テーブル初期化時に終了条件を組み込むと、以下のように終了条件の分岐を省略できる

fibonacci2.rb

$table = [0, 1]

def fibonacci(n)
    $table[n] ||= fibonacci(n - 2) + fibonacci(n - 1)
end

p fibonacci(30) #=> 832040

ナップサック問題

重さと価値の分かっている品物のリストが与えられたときに、あるナップサックに詰める品物を決められた重さ以内で価値最大となるよう選ぶ問題。日常生活でも使える場面が多そうな最適化問題。

問題のバリエーションのひとつに同じ品物を複数選べるかがある。サンプルコードは各品物を1個までしか選べない「0-1 ナップサック問題」について。

knapsack.rb

class Item
    attr_reader :weight, :value

    def initialize(weight, value, info = nil)
        @weight = weight
        @value  = value
        @info   = info
    end
end

class Knapsack
    def calc(items, weight_limit)
        n = items.size
        @items = [nil] + items   # one-based indexing

        @table = Array.new(n + 1) { Array.new(weight_limit + 1) }
        __calc__(n, weight_limit)
    end

    def select_items(items, weight_limit)
        n = items.size
        @items = [nil] + items   # one-based indexing

        @table = Array.new(n + 1) { Array.new(weight_limit + 1) }
        __select_items__(n, weight_limit)
    end

    private

    # memoized function
    def __calc__(n, weight_limit)
        @table[n][weight_limit] ||= __calc_org__(n, weight_limit)
    end

    # original function (renamed from "__calc__")
    def __calc_org__(n, weight_limit)
        return 0 if n == 0

        item = @items[n]
        bound = [weight_limit / item.weight, 1].min   # 0 or 1

        values = (0..bound).collect do |k|
            __calc__(n - 1, weight_limit - item.weight * k) + item.value * k
        end

        values.max
    end

    def __select_items__(n, weight_limit)
        return [] if n == 0

        item = @items[n]
        bound = [weight_limit / item.weight, 1].min   # 0 or 1
        value_max = __calc__(n, weight_limit)

        num = (0..bound).find do |k|
            __calc__(n - 1, weight_limit - item.weight * k) + item.value * k == value_max
        end

        __select_items__(n - 1, weight_limit - item.weight * num) << [item, num]
    end
end


if $0 == __FILE__
    items = [
        # weight [g], value [yen], name
        Item.new(90, 108, "cookie"),
        Item.new(60,  74, "potato chips"),
        Item.new(85, 138, "gummi"),
        Item.new(50,  95, "chocolate"),
        Item.new(58,  70, "youkan"),
    ]
    weight_limit = 200

    selected_items = Knapsack.new.select_items(items, weight_limit)
    weight = value_max = 0
    selected_items.each do |item,num|
        weight    += item.weight * num
        value_max += item.value  * num
    end

    puts "weight         : #{weight} (<= #{weight_limit})"
    puts "value_max      : #{value_max}"
    puts "selected_items : "
    selected_items.each do |item,num|
        puts "    #{num} * #{item.inspect}"
    end
end

output

weight         : 195 (<= 200)
value_max      : 307
selected_items :
    0 * #<Item:0x00000002c85080 @weight=90, @value=108, @info="cookie">
    1 * #<Item:0x00000002c85008 @weight=60, @value=74, @info="potato chips">
    1 * #<Item:0x00000002c84fb8 @weight=85, @value=138, @info="gummi">
    1 * #<Item:0x00000002c84f68 @weight=50, @value=95, @info="chocolate">
    0 * #<Item:0x00000002c84f18 @weight=58, @value=70, @info="youkan">

最大値を求めることがアルゴリズムの核なので、以下では Knapsack#calc 関連の部分を説明する。

問題を小さくする方法
- 品物リストがひとつ少ない場合については、任意の重さ制限に対する最大価値が全て分かっていると仮定する
- 新しい品物 @items[n] を入れる場合と入れない場合の価値を計算し、大きいほうを選ぶ
  - 入れる場合というのは、重さ制限から新しい品物分を抜いたときの最大価値＋新しい品物の価値、と計算できる
  - ただし新しい品物を入れる余裕がないときは、入れない場合の一択になる
終了条件
- 品物リストが空なら、何も詰められないので合計価値は0
備考
- 品物が少なくて重さ制限がゆるい場合は、メモ済みの状態に当たる可能性が低いので、全探索で計算したほうが効率いいことがある

レーベンシュタイン距離

ある文字列から別の文字列へ編集するには最小で何文字だけ挿入・削除・置換すればいいかを数える。文字列がどれくらい似ているかを測る方法のひとつ。

levenshtein_distance.rb

class LevenshteinDistance
    def calc(str1, str2)
        @str1 = str1
        @str2 = str2
        n1 = @str1.length
        n2 = @str2.length
        @table = Array.new(n1 + 1) { Array.new(n2 + 1) }
        __calc__(n1, n2)
    end

    private

    # distance between @str1[0...n1] and @str2[0...n2]
    def __calc__(n1, n2)
        @table[n1][n2] ||= begin
            if n1 == 0
                1 * n2   # insert all characters
            elsif n2 == 0
                1 * n1   # delete all characters
            else
                ins = __calc__(n1    , n2 - 1) + 1
                del = __calc__(n1 - 1, n2    ) + 1
                sub = __calc__(n1 - 1, n2 - 1) + sub_score(n1, n2)
                [ins, del, sub].min
            end
        end
    end

    def sub_score(n1, n2)
        @str1[n1-1] == @str2[n2-1] ? 0 : 1
    end
end


if $0 == __FILE__
    p LevenshteinDistance.new.calc("Tuesday", "Thursday") #=> 2
end

問題を小さくする方法
- より短い部分文字列の距離については分かっていると仮定する
- 末尾の文字を挿入・削除・置換したと仮定してスコアを計算し、最良のものを採用する
終了条件
- 片方の文字列が空なら、もう片方の文字列の長さがスコア（全追加or全削除ということ）
備考
- 文字列間の距離だけでなく実際の編集方法を知りたいときは、完成した表をゴールからスタートへ向かって低スコア部分をたどればいい

dump_table

   |       T   h   u   r   s   d   a   y
---+------------------------------------
   |  *0   1   2   3   4   5   6   7   8
 T |   1  *0  *1   2   3   4   5   6   7
 u |   2   1   1  *1   2   3   4   5   6
 e |   3   2   2   2  *2   3   4   5   6
 s |   4   3   3   3   3  *2   3   4   5
 d |   5   4   4   4   4   3  *2   3   4
 a |   6   5   5   5   5   4   3  *2   3
 y |   7   6   6   6   6   5   4   3  *2

相互再帰

これまでの再帰関数は自分自身を呼び出していたが、複数の関数がお互いを呼び出してもいい。問題が小さくなっているのか自明でないこともあり、正しい論理を組み立てられず処理が終わらなくなる危険が大きい。

偶奇判定

実用性は無いが簡単な例。（参考）

even_odd.rb

def even?(n)
    n == 0 ? true : odd?(n - 1)
end

def odd?(n)
    n == 0 ? false : even?(n - 1)
end

p even?(4) #=> true
p even?(7) #=> false

問題を小さくする方法
- ひとつ小さい値の偶奇は逆
終了条件
- 0は偶数

再帰下降構文解析

文字列の構造を読み取る方法のひとつで、相互再帰になっている構文定義の各規則をそのまま関数にする。構文解析器のコードを書くのは手作業でも比較的簡単で、さらに構文定義から自動生成するコードも実装しやすい。

ここでは「1桁の整数・加算・乗算・括弧のみの数式を解釈して計算結果を返す」構文解析器を作ってみる。構文はParsing Expression Grammar（PEG）に基づいて定義する。

参考：

The Packrat Parsing and Parsing Expression Grammars Page
- Parsing Expression Grammars: A Recognition-Based Syntactic Foundation
PEG.js

parsing_expression_grammar

additive  <- multitive ('+' multitive)*
multitive <- primary   ('*' primary  )*
primary   <- decimal / '(' additive ')'
decimal   <- [0-9]

expr_parser.rb

class ExprParser
    def parse(str)
        @str = str
        index, value = additive(0)
        index == @str.length ? value : nil
    end

    private

    FAILED_RESULT = [nil, nil]
    private_constant :FAILED_RESULT

    def additive(idx)
        idx, val = multitive(idx)
        return FAILED_RESULT unless val

        loop do
            break if @str[idx] != '+'
            i, v = multitive(idx + 1)
            break unless v
            idx = i
            val += v
        end
        [idx, val]
    end

    def multitive(idx)
        idx, val = primary(idx)
        return FAILED_RESULT unless val

        loop do
            break if @str[idx] != '*'
            i, v = primary(idx + 1)
            break unless v
            idx = i
            val *= v
        end
        [idx, val]
    end

    def primary(idx)
        i, v = decimal(idx)
        return [i, v] if v

        return FAILED_RESULT if @str[idx] != '('
        idx, val = additive(idx + 1)
        return FAILED_RESULT unless val
        return FAILED_RESULT if @str[idx] != ')'
        [idx + 1, val]
    end

    def decimal(idx)
        if /\A[0-9]/ =~ @str[idx..-1]
            [idx + $&.length, $&.to_i]   # $&: matched string
        else
            FAILED_RESULT
        end
    end
end


if $0 == __FILE__
    p ExprParser.new.parse("1+2*(3*(4+5)+6)*(7+8)+9") #=> 1000
    p ExprParser.new.parse("1+2*(3*(4+5)+6*78)+9")    #=> nil
end

自己再帰では「問題を小さくする」「再帰呼び出しせず終了する」役割を自分自身で持たなければいけなかったが、相互再帰ではそれらが全体のどこかにあればいい。なので構造が非常に分かりにくい上に、それらの役割が必ず呼ばれることも保証しづらい。

問題を小さくする方法
- それぞれの構文規則は、文字列や他の規則を組み合わせた再帰的な表現から成る。各表現は規則全体と同じかより短い文字列にマッチする
- 以下のパターンは無限ループになるのでダメ
  - 規則の先頭で同じ規則を参照する（左再帰）。直接でなくても相互再帰の結果としてなることがある
  - 空文字列にマッチする表現を * などで無限に繰り返す
終了条件
- 「再帰呼び出しをせず」という意味では、文字列を読み取ることが終了条件にあたる。読み取り専用の規則に切り出しておくと分かりやすい
再帰関数の実装方法
- 構文規則に対応する関数を用意する。まずは入出力の仕様だけ決めておく
  - 引数は文字列の読み取り位置
  - 解析成功なら、読み進めた位置と解析結果を返す
  - 解析失敗なら、失敗を表す何かを返す
  - 関数の副作用（インスタンス変数の書き換えなど）は無し
- 構文解析するように関数を実装する
  - 読み取り位置を常に管理する。失敗時の差し戻し地点も必要なので、値の上書きには要注意
  - 現在位置で期待する規則の関数を呼び出し、解析結果を受け取る。文字列を期待するなら直接調べてもいい
  - 受け取った結果をもとに、読み進めた先で解析を続けたり、失敗前の位置から別の解析を試したりする
  - 規則の終わりまでいったら解析成功、途中で詰まったら解析失敗
備考
- 正しい数式の後に余計な文字列が続かないことは ExprParser#parse の最後で確認している。PEGでは構文定義に含めることもできる
- 例では同じ関数に同じ位置を与えると常に同じ結果を返す。よってメモ化することで高速化が図れる（パックラット構文解析）

おまけ

再帰呼び出しの限界

再帰呼び出しはいくらでも深く実行できるわけではなく、どこかでスタックオーバーフローを起こす。その限界を簡単なコードで測ってみる。

recurse_limit.rb

def recurse_limit(count = 1)
    recurse_limit(count + 1)
rescue SystemStackError
    count
end

begin
    p recurse_limit
rescue SystemStackError
    p 0
end

問題を小さくする方法
- 関数呼び出しでスタックを消費する
終了条件
- 呼び出しできず、何かしらのエラーが発生する
備考
- 引数が多いなどでスタックをより消費していると呼び出せる回数が減る

まとめ

問題を小さくする方法
- より小さい問題については解けると仮定して、その結果から元の解を得る
- 問題の大きさを n から n-1 に減らすパターンが基本的
- 問題を2つ以上の小さい問題に分割することもある
- 複数の問題を行き来してもいい。問題が小さくなっているか分かりにくいので注意がいる
終了条件
- 問題をこれ以上小さくできない場合については必須
  - 大きさが0や1などのときが基本的。解が自明なことが多い
  - 再帰処理がエラーを起こすような場合は気づきやすい
- まだ再帰できるときに終了しても構わない
  - 再帰でやり切るよりも、ある程度まで小さくなった段階でアルゴリズムを変えたほうが効率いいことがある
  - 「すでに同じ計算をしていて答えを知っている」でも終了できる

例では n ≧ 2 の場合と一貫性を持たせるために、常に新しい配列を作って返している ↩

注意事項：

- アルゴリズムの細かい効率よりも、論理の分かりやすさに重点を置いている
- 問題の前提に沿わない入力（例えば負の整数や小数）のチェックは省いている
- 再帰的なデータ構造や再帰を除去する方法については扱わない
- サンプルコードはRubyで書いている

## 基本的な再帰
### [階乗](https://ja.wikipedia.org/wiki/階乗)
「1からnまでの整数の積」と言われたらfor文などのループで書きたくなるが、再帰的な計算もできる。

```ruby:factorial.rb
def factorial(n)
	return 1 if n == 0

n * factorial(n - 1)
end

p factorial(5) #=> 120
```

- 問題を小さくする方法
	- *ひとつ小さい値(n-1)での計算結果*に n を掛ける
- 終了条件
	- nが0なら値は1。そう定めておくのが色々な状況で自然

### [最大公約数](https://ja.wikipedia.org/wiki/最大公約数)（GCD）
公約数を見つけて割っていく方法や素因数分解する方法は計算が大変。[ユークリッドの互除法](https://ja.wikipedia.org/wiki/ユークリッドの互除法)を使うと効率よく求められる。

```ruby:gcd.rb
def gcd(a, b)
	return a.abs if b == 0

gcd(b, a % b)
end

p gcd(1920, 1080) #=> 120
```

以下の説明では簡単のために a, b が0以上の整数であるとする。負の整数へ対応するにはサンプルコードの通り絶対値を返せばいい。

- 問題を小さくする方法
	- aとbの最大公約数は、*bとa%b（aをbで割った余り）の最大公約数*と等しい。b > a%b なので第2引数は必ず元より小さくなる
- 終了条件
	- bがゼロのとき、aが最大公約数。ちょうどa%bがゼロ除算で計算できない
- 備考
	- 数学的な説明のときは a ≧ b という前提をおくことがあるが、実装の際は考慮不要。a < b なら再帰呼び出しによって `gcd(a, b)` → `gcd(b, a)` → `...` と自動で入れ替わる
	- 再帰は十進の桁数の5倍以下で済むので、64bit整数（20桁）程度ならスタックオーバーフローはまず起きない
	- 関数の最後の処理が再帰呼び出しである[末尾再帰](https://ja.wikipedia.org/wiki/末尾再帰)は、再帰を簡単に除去できる。コンパイラが自動で除去してくれる可能性がある

### [ハノイの塔](https://ja.wikipedia.org/wiki/ハノイの塔)
有名なパズル。3本の棒のひとつにささってピラミッド状に積まれているn枚の円盤を、大きさを逆転させないように1枚ずつ移動させて、全て別の1本の棒に積み直す手順を考える。~~重ねて収納する鍋と3ヶ所の収納スペースで試してもいい。~~

```ruby:hanoi.rb
RODS = ["A", "B", "C"]

def hanoi(n, from, to)
	return if n == 0 # do nothing

temp, = RODS - [from, to]
	hanoi(n - 1, from, temp)
	puts "move disk##{n} from #{from} to #{to}"
	hanoi(n - 1, temp, to)
end

hanoi(4, RODS.first, RODS.last)
```

```text:output
move disk#1 from A to B
move disk#2 from A to C
move disk#1 from B to C
move disk#3 from A to B
move disk#1 from C to A
move disk#2 from C to B
move disk#1 from A to B
move disk#4 from A to C
move disk#1 from B to C
move disk#2 from B to A
move disk#1 from C to A
move disk#3 from B to C
move disk#1 from A to B
move disk#2 from A to C
move disk#1 from B to C
```

- 問題を小さくする方法
	- 円盤の山を「*上n-1枚の塊*」と「下1枚」とみて考える
	- *上側を仮置き場に退避*させてから下側を目的地へ移動させ、*上側を仮置き場から目的地に移動*させる
- 終了条件
	- 円盤が0枚なら何もしない。円盤の無いパズルというのは奇妙だが、認めれば短く実装できる
	- それが嫌なら、円盤が1枚ならただfromからtoへ動かすだけ、と実装してもいい

## [分割統治法](https://ja.wikipedia.org/wiki/分割統治法)
大きな問題を小さな問題に分割してそれぞれ解き、結果をまとめて元の問題の解を得る手法。解法が分からないときの手掛かりになるだけでなく、計算時間が問題サイズに従って急激に伸びる場合には直接全体を解くより高速になることが多々ある。

### [クイックソート](https://ja.wikipedia.org/wiki/クイックソート)
一般的な用途では最も速いソート方法。

```ruby:quick_sort.rb
def quick_sort(ary)
	ary = ary.dup   # preserve the input array
	n = ary.size
	return ary if n <= 1

pivot = ary.delete_at(rand(n))
	ary_less_eq, ary_greater = ary.partition { |x| x <= pivot }
	quick_sort(ary_less_eq) + [pivot] + quick_sort(ary_greater)
end

if $0 == __FILE__
	ary = 10.times.map { rand(10) }
	puts "input:  #{ary}"
	puts "output: #{quick_sort(ary)}"
end
```

- 問題を小さくする方法
	- 適当な値（ピボット）を選び、それより小さいものと大きいものに分けた配列を作る。ピボットを抜いておけば、分けた配列の要素数は必ず元より小さくなる
	- *分けた配列それぞれをソート*して結合するとソート完了
- 終了条件
	- 要素数が0なら空の配列をそのまま返す[^ary_dup]。ピボットを選べないため再帰的処理が成立しない
	- 要素数が1でも、ソート済みとみなせるので配列をそのまま返していい[^ary_dup]
- 備考
	- 元の配列内で前後に要素を寄せれば、新しい配列を作らずに分割できて結合の手間もなくなる。それを再帰的に繰り返せば内部ソートとなる
	- 分割した配列が同じ大きさになると高速だが、片寄り続けるとバブルソート並みに遅くなる
		- 単純な実装では、ソート済みの配列や全て同じ値の配列に弱いことがある
		- 最悪に近いケースでは再帰呼び出しも増え、スタックオーバーフローの危険がある（例：`quick_sort([1] * 10**4)`）

[^ary_dup]: 例では n ≧ 2 の場合と一貫性を持たせるために、常に新しい配列を作って返している

### [マージソート](https://ja.wikipedia.org/wiki/マージソート)
分割統治法を使った別のソート方法。クイックソートは分割時の処理でソートするのに対し、マージソートは併合時の処理でソートする。ソートの性質も両者で色々と異なる。

```ruby:merge_sort.rb
def merge_sort(ary)
	n = ary.size
	return ary.dup if n <= 1

ary_left  = merge_sort(ary[0...(n/2)])
	ary_right = merge_sort(ary[(n/2)..-1])
	ary = []
	loop do
		if ary_left.empty?
			ary.concat(ary_right)
			break
		elsif ary_right.empty?
			ary.concat(ary_left)
			break
		elsif ary_left[0] <= ary_right[0] # stable
			ary << ary_left.shift
		else
			ary << ary_right.shift
		end
	end
	ary
end

if $0 == __FILE__
	ary = 10.times.map { rand(10) }
	puts "input:  #{ary}"
	puts "output: #{merge_sort(ary)}"
end
```

- 問題を小さくする方法
	- 配列を2分割し、*それぞれソート*しておく
	- 2つの配列を比較しながら小さい順に要素を抜き出していき、ソートされた1つの配列を作る
- 終了条件
	- 要素数が0か1なら、配列をそのまま返す[^ary_dup]。分割しようとすると無限ループに陥る
- 備考
	- 均等に分割できるので最悪ケースでも高速に動作する
	- 自然と安定ソートを実装できる

### [高速フーリエ変換](https://ja.wikipedia.org/wiki/高速フーリエ変換)（FFT）
[離散フーリエ変換](https://ja.wikipedia.org/wiki/離散フーリエ変換)（DFT）を高速に計算するアルゴリズム。データの「波」を扱う様々な処理を実用化する基礎になっている。

参考：

- [FFT (高速フーリエ・コサイン・サイン変換) の概略と設計法](http://www.kurims.kyoto-u.ac.jp/~ooura/fftman/): 1.2.3. 混合基数アルゴリズム
- [Cooley–Tukey FFT algorithm](https://en.wikipedia.org/wiki/Cooley–Tukey_FFT_algorithm): 3. General factorizations

```ruby:fft.rb
require 'prime'

def twiddle_factor(n, m)
	Complex.polar(1, -2 * Math::PI * m / n)
end

def dft(ary)
	n = ary.size
	w = n.times.collect { |m| twiddle_factor(n, m) }

n.times.collect do |k|
		n.times.collect do |j|
			ary[j] * w[j * k % n]
		end.inject(:+)
	end
end

def fft(ary)
	n = ary.size
	return ary.dup if n <= 1

n1 = Prime.instance.find { |p| n % p == 0 }
	n2 = n / n1
	return dft(ary) if n == n1

w = n.times.collect { |m| twiddle_factor(n, m) }
	ary.each_slice(n1).to_a.transpose.collect! do |ary2|
		fft(ary2)   # length: n2
	end.collect!.with_index do |ary2,j1|
		# 0 <= j1 < n1, 0 <= k2 < n2
		ary2.collect!.with_index { |a,k2| a * w[j1 * k2] }
	end.transpose.collect! do |ary1|
		fft(ary1)   # length: n1
	end.transpose.flatten!
end

if $0 == __FILE__
	require 'benchmark'

# test data: sin(kx)
	n = 2**3 * 3**2 * 5**2   #=> 1800
	k = 7
	ary = n.times.map { |j| Math.sin(2 * Math::PI * j * k / n) }
	puts "test data: sin(#{k}x)"
	puts "samples:   #{n}"
	puts

# benchmark
	result_dft = result_fft = nil
	Benchmark.bm(5) do |rep|
		rep.report('DFT:') { result_dft = dft(ary) }   # slow
		rep.report('FFT:') { result_fft = fft(ary) }   # fast
	end
	puts

# error
	def calc_error(n, k, result)
		return 0 if n == 0
		diff = result.dup
		diff[k]   -= -n / 2.0 * Complex::I
		diff[n-k] -=  n / 2.0 * Complex::I
		Math.sqrt(diff.map(&:abs2).inject(:+))
	end

puts "exact solution: c[#{k}] = #{-n/2.0}i, c[#{-k}] = #{n/2.0}i"
	puts "DFT error: #{calc_error(n, k, result_dft)}"
	puts "FFT error: #{calc_error(n, k, result_fft)}"
	puts
end
```

- 問題を小さくする方法
	- 長さ N=PQ のDFTは、*長さ P のDFT*を Q 回、*長さ Q のDFT*を P 回計算することで求められる。途中で回転因子 W を掛ける必要がある
- 終了条件
	- Nが0か1なら変換後も同じ値[^ary_dup]。素因数を探す際に不都合なので最初に弾く
	- Nが素数なら他のDFTアルゴリズムで計算する。分割しようとすると無限ループに陥る
		- `n1` は必ず素数なので、if文にせずループ内で `dft(ary1)` と直接呼び出してもいい
- 備考
	- Nが2の累乗のときは、細かく分割できるだけでなくほとんどの回転因子が±1で計算を簡略化でき、適切に実装すれば非常に高速となる

`fft` のメイン計算部分がごちゃごちゃしているが、簡単に言うと `ary.each_slice(nx).to_a.xxx.flatten!` という構造で、配列を一時的に2次元化して縦横にDFTを計算している。2次元配列の走査方向が入出力時で異なることに注意。

## メモ化再帰
[メモ化](https://ja.wikipedia.org/wiki/メモ化)という手法を再帰計算に適用する。考え方は簡単で、「以前に計算結果をメモしたので答えを知っている」ということを再帰の終了条件に追加する。これによって、同じ部分問題を何度も解く羽目になるタイプの再帰アルゴリズムを高速化できる。特に最適化問題を再帰で解くときによく現れ、[動的計画法](https://ja.wikipedia.org/wiki/動的計画法)の実現方法のひとつとなっている。

ちなみに、メモ化しただけではスタックオーバーフローは防げないが、あらかじめ小さい問題を解いてメモを埋めることでひとまず対処できる。

以下の例では、「メモが無ければ計算・保存したうえでメモの値を返す」という処理には [`||=`](https://docs.ruby-lang.org/ja/latest/doc/spec=2foperator.html#selfassign) を利用している。これが利用できない状況では、ダミーの値などでメモの有無を判別して処理を分ければいい。

### [フィボナッチ数列](https://ja.wikipedia.org/wiki/フィボナッチ数)
`0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...` と、前2つの数を足すことで求まる数列。単純ながら色々なところで登場するので興味深い。（例えば、隣り合う数はユークリッドの互除法の最悪ケースとなる）

定義自体が再帰的なので再帰関数を実装するのは簡単。しかしそのままでは計算に時間がかかるので、メモ化を施す必要がある。

```ruby:fibonacci.rb
$table = []

def fibonacci(n)
	$table[n] ||= begin
		case n
		when 0 then 0
		when 1 then 1
		else fibonacci(n - 2) + fibonacci(n - 1)
		end
	end
end

p fibonacci(30) #=> 832040
```

- 問題を小さくする方法
	- *前項2つを求めて*足す
- 終了条件
	- nが0と1のときの値は決められている
- 備考
	- テーブル初期化時に終了条件を組み込むと、以下のように終了条件の分岐を省略できる

```ruby:fibonacci2.rb
$table = [0, 1]

def fibonacci(n)
	$table[n] ||= fibonacci(n - 2) + fibonacci(n - 1)
end

p fibonacci(30) #=> 832040
```

### [ナップサック問題](https://ja.wikipedia.org/wiki/ナップサック問題)
重さと価値の分かっている品物のリストが与えられたときに、あるナップサックに詰める品物を決められた重さ以内で価値最大となるよう選ぶ問題。日常生活でも使える場面が多そうな最適化問題。

```knapsack.rb
class Item
	attr_reader :weight, :value

def initialize(weight, value, info = nil)
		@weight = weight
		@value  = value
		@info   = info
	end
end

class Knapsack
	def calc(items, weight_limit)
		n = items.size
		@items = [nil] + items   # one-based indexing

@table = Array.new(n + 1) { Array.new(weight_limit + 1) }
		__calc__(n, weight_limit)
	end

def select_items(items, weight_limit)
		n = items.size
		@items = [nil] + items   # one-based indexing

@table = Array.new(n + 1) { Array.new(weight_limit + 1) }
		__select_items__(n, weight_limit)
	end

private

# memoized function
	def __calc__(n, weight_limit)
		@table[n][weight_limit] ||= __calc_org__(n, weight_limit)
	end

# original function (renamed from "__calc__")
	def __calc_org__(n, weight_limit)
		return 0 if n == 0

item = @items[n]
		bound = [weight_limit / item.weight, 1].min   # 0 or 1

values = (0..bound).collect do |k|
			__calc__(n - 1, weight_limit - item.weight * k) + item.value * k
		end

values.max
	end

def __select_items__(n, weight_limit)
		return [] if n == 0

item = @items[n]
		bound = [weight_limit / item.weight, 1].min   # 0 or 1
		value_max = __calc__(n, weight_limit)

num = (0..bound).find do |k|
			__calc__(n - 1, weight_limit - item.weight * k) + item.value * k == value_max
		end

__select_items__(n - 1, weight_limit - item.weight * num) << [item, num]
	end
end

if $0 == __FILE__
	items = [
		# weight [g], value [yen], name
		Item.new(90, 108, "cookie"),
		Item.new(60,  74, "potato chips"),
		Item.new(85, 138, "gummi"),
		Item.new(50,  95, "chocolate"),
		Item.new(58,  70, "youkan"),
	]
	weight_limit = 200

selected_items = Knapsack.new.select_items(items, weight_limit)
	weight = value_max = 0
	selected_items.each do |item,num|
		weight    += item.weight * num
		value_max += item.value  * num
	end

puts "weight         : #{weight} (<= #{weight_limit})"
	puts "value_max      : #{value_max}"
	puts "selected_items : "
	selected_items.each do |item,num|
		puts "    #{num} * #{item.inspect}"
	end
end
```

```text:output
weight         : 195 (<= 200)
value_max      : 307
selected_items :
    0 * #<Item:0x00000002c85080 @weight=90, @value=108, @info="cookie">
    1 * #<Item:0x00000002c85008 @weight=60, @value=74, @info="potato chips">
    1 * #<Item:0x00000002c84fb8 @weight=85, @value=138, @info="gummi">
    1 * #<Item:0x00000002c84f68 @weight=50, @value=95, @info="chocolate">
    0 * #<Item:0x00000002c84f18 @weight=58, @value=70, @info="youkan">
```

最大値を求めることがアルゴリズムの核なので、以下では `Knapsack#calc` 関連の部分を説明する。

- 問題を小さくする方法
	- *品物リストがひとつ少ない場合については、任意の重さ制限に対する最大価値が全て分かっている*と仮定する
	- 新しい品物 `@items[n]` を入れる場合と入れない場合の価値を計算し、大きいほうを選ぶ
		- 入れる場合というのは、*重さ制限から新しい品物分を抜いたときの最大価値*＋新しい品物の価値、と計算できる
		- ただし新しい品物を入れる余裕がないときは、入れない場合の一択になる
- 終了条件
	- 品物リストが空なら、何も詰められないので合計価値は0
- 備考
	- 品物が少なくて重さ制限がゆるい場合は、メモ済みの状態に当たる可能性が低いので、全探索で計算したほうが効率いいことがある

### [レーベンシュタイン距離](https://ja.wikipedia.org/wiki/レーベンシュタイン距離)
ある文字列から別の文字列へ編集するには最小で何文字だけ挿入・削除・置換すればいいかを数える。文字列がどれくらい似ているかを測る方法のひとつ。

```ruby:levenshtein_distance.rb
class LevenshteinDistance
	def calc(str1, str2)
		@str1 = str1
		@str2 = str2
		n1 = @str1.length
		n2 = @str2.length
		@table = Array.new(n1 + 1) { Array.new(n2 + 1) }
		__calc__(n1, n2)
	end

private

# distance between @str1[0...n1] and @str2[0...n2]
	def __calc__(n1, n2)
		@table[n1][n2] ||= begin
			if n1 == 0
				1 * n2   # insert all characters
			elsif n2 == 0
				1 * n1   # delete all characters
			else
				ins = __calc__(n1    , n2 - 1) + 1
				del = __calc__(n1 - 1, n2    ) + 1
				sub = __calc__(n1 - 1, n2 - 1) + sub_score(n1, n2)
				[ins, del, sub].min
			end
		end
	end

def sub_score(n1, n2)
		@str1[n1-1] == @str2[n2-1] ? 0 : 1
	end
end

if $0 == __FILE__
	p LevenshteinDistance.new.calc("Tuesday", "Thursday") #=> 2
end
```

- 問題を小さくする方法
	- *より短い部分文字列の距離については分かっている*と仮定する
	- 末尾の文字を挿入・削除・置換したと仮定してスコアを計算し、最良のものを採用する
- 終了条件
	- 片方の文字列が空なら、もう片方の文字列の長さがスコア（全追加or全削除ということ）
- 備考
	- 文字列間の距離だけでなく実際の編集方法を知りたいときは、完成した表をゴールからスタートへ向かって低スコア部分をたどればいい

```text:dump_table
   |       T   h   u   r   s   d   a   y
---+------------------------------------
   |  *0   1   2   3   4   5   6   7   8
 T |   1  *0  *1   2   3   4   5   6   7
 u |   2   1   1  *1   2   3   4   5   6
 e |   3   2   2   2  *2   3   4   5   6
 s |   4   3   3   3   3  *2   3   4   5
 d |   5   4   4   4   4   3  *2   3   4
 a |   6   5   5   5   5   4   3  *2   3
 y |   7   6   6   6   6   5   4   3  *2
```

## [相互再帰](https://ja.wikipedia.org/wiki/相互再帰)
これまでの再帰関数は自分自身を呼び出していたが、複数の関数がお互いを呼び出してもいい。問題が小さくなっているのか自明でないこともあり、正しい論理を組み立てられず処理が終わらなくなる危険が大きい。

### 偶奇判定
実用性は無いが簡単な例。（[参考](https://en.wikipedia.org/wiki/Mutual_recursion#Basic_examples)）

```ruby:even_odd.rb
def even?(n)
	n == 0 ? true : odd?(n - 1)
end

def odd?(n)
	n == 0 ? false : even?(n - 1)
end

p even?(4) #=> true
p even?(7) #=> false
```

- 問題を小さくする方法
	- *ひとつ小さい値の偶奇*は逆
- 終了条件
	- 0は偶数

### [再帰下降構文解析](https://ja.wikipedia.org/wiki/再帰下降構文解析)
文字列の構造を読み取る方法のひとつで、相互再帰になっている構文定義の各規則をそのまま関数にする。構文解析器のコードを書くのは手作業でも比較的簡単で、さらに構文定義から自動生成するコードも実装しやすい。

ここでは「1桁の整数・加算・乗算・括弧のみの数式を解釈して計算結果を返す」構文解析器を作ってみる。構文は[Parsing Expression Grammar](https://ja.wikipedia.org/wiki/Parsing Expression Grammar)（PEG）に基づいて定義する。

参考：

- [The Packrat Parsing and Parsing Expression Grammars Page](http://bford.info/packrat/)
	- Parsing Expression Grammars: A Recognition-Based Syntactic Foundation
- [PEG.js](http://pegjs.org/)

```text:parsing_expression_grammar
additive  <- multitive ('+' multitive)*
multitive <- primary   ('*' primary  )*
primary   <- decimal / '(' additive ')'
decimal   <- [0-9]
```

```ruby:expr_parser.rb
class ExprParser
	def parse(str)
		@str = str
		index, value = additive(0)
		index == @str.length ? value : nil
	end

private

FAILED_RESULT = [nil, nil]
	private_constant :FAILED_RESULT

def additive(idx)
		idx, val = multitive(idx)
		return FAILED_RESULT unless val

loop do
			break if @str[idx] != '+'
			i, v = multitive(idx + 1)
			break unless v
			idx = i
			val += v
		end
		[idx, val]
	end

def multitive(idx)
		idx, val = primary(idx)
		return FAILED_RESULT unless val

loop do
			break if @str[idx] != '*'
			i, v = primary(idx + 1)
			break unless v
			idx = i
			val *= v
		end
		[idx, val]
	end

def primary(idx)
		i, v = decimal(idx)
		return [i, v] if v

return FAILED_RESULT if @str[idx] != '('
		idx, val = additive(idx + 1)
		return FAILED_RESULT unless val
		return FAILED_RESULT if @str[idx] != ')'
		[idx + 1, val]
	end

def decimal(idx)
		if /\A[0-9]/ =~ @str[idx..-1]
			[idx + $&.length, $&.to_i]   # $&: matched string
		else
			FAILED_RESULT
		end
	end
end

if $0 == __FILE__
	p ExprParser.new.parse("1+2*(3*(4+5)+6)*(7+8)+9") #=> 1000
	p ExprParser.new.parse("1+2*(3*(4+5)+6*78)+9")    #=> nil
end
```

- 問題を小さくする方法
	- それぞれの構文規則は、文字列や*他の規則*を組み合わせた再帰的な表現から成る。各表現は規則全体と同じかより短い文字列にマッチする
	- 以下のパターンは無限ループになるのでダメ
		- 規則の先頭で同じ規則を参照する（左再帰）。直接でなくても相互再帰の結果としてなることがある
		- 空文字列にマッチする表現を `*` などで無限に繰り返す
- 終了条件
	- 「再帰呼び出しをせず」という意味では、文字列を読み取ることが終了条件にあたる。読み取り専用の規則に切り出しておくと分かりやすい
- 再帰関数の実装方法
	- 構文規則に対応する関数を用意する。まずは入出力の仕様だけ決めておく
		- 引数は文字列の読み取り位置
		- 解析成功なら、読み進めた位置と解析結果を返す
		- 解析失敗なら、失敗を表す何かを返す
		- 関数の副作用（インスタンス変数の書き換えなど）は無し
	- 構文解析するように関数を実装する
		- 読み取り位置を常に管理する。失敗時の差し戻し地点も必要なので、値の上書きには要注意
		- 現在位置で*期待する規則の関数を呼び出し*、解析結果を受け取る。文字列を期待するなら直接調べてもいい
		- 受け取った結果をもとに、読み進めた先で解析を続けたり、失敗前の位置から別の解析を試したりする
		- 規則の終わりまでいったら解析成功、途中で詰まったら解析失敗
- 備考
	- 正しい数式の後に余計な文字列が続かないことは `ExprParser#parse` の最後で確認している。PEGでは構文定義に含めることもできる
	- 例では同じ関数に同じ位置を与えると常に同じ結果を返す。よってメモ化することで高速化が図れる（パックラット構文解析）

## おまけ
### 再帰呼び出しの限界
再帰呼び出しはいくらでも深く実行できるわけではなく、どこかで[スタックオーバーフロー](https://ja.wikipedia.org/wiki/スタックオーバーフロー)を起こす。その限界を簡単なコードで測ってみる。

```ruby:recurse_limit.rb
def recurse_limit(count = 1)
	recurse_limit(count + 1)
rescue SystemStackError
	count
end

begin
	p recurse_limit
rescue SystemStackError
	p 0
end
```

- 問題を小さくする方法
	- 関数呼び出しでスタックを消費する
- 終了条件
	- 呼び出しできず、何かしらのエラーが発生する
- 備考
	- 引数が多いなどでスタックをより消費していると呼び出せる回数が減る

## まとめ

- 問題を小さくする方法
	- より小さい問題については解けると仮定して、その結果から元の解を得る
	- 問題の大きさを n から n-1 に減らすパターンが基本的
	- 問題を2つ以上の小さい問題に分割することもある
	- 複数の問題を行き来してもいい。問題が小さくなっているか分かりにくいので注意がいる
- 終了条件
	- 問題をこれ以上小さくできない場合については必須
		- 大きさが0や1などのときが基本的。解が自明なことが多い
		- 再帰処理がエラーを起こすような場合は気づきやすい
	- まだ再帰できるときに終了しても構わない
		- 再帰でやり切るよりも、ある程度まで小さくなった段階でアルゴリズムを変えたほうが効率いいことがある
		- 「すでに同じ計算をしていて答えを知っている」でも終了できる

HMMNRST

44Contribution

再帰的なアルゴリズムの実例集

基本的な再帰

最大公約数（GCD）

高速フーリエ変換（FFT）

メモ化再帰

偶奇判定

おまけ

再帰呼び出しの限界

まとめ

人気の投稿

問題がある投稿を報告する

ご意見