10

アッカーマン関数がどのように機能するかを理解するのが難しいと感じています。再帰についての私の理解に欠陥があると思いますか?

Python のコードは次のとおりです。

  def naive_ackermann(m, n):
    global calls
    calls += 1
    if m == 0:
        return n + 1
    elif n == 0:
        return naive_ackermann(m - 1, 1)
    else:
        return naive_ackermann(m - 1, naive_ackermann(m, n - 1))

naive_ackermann(3,4) の関数呼び出しを行うと、125 になるのはなぜですか?

コメントをお待ちしております。

ありがとう

4

4 に答える 4

16

A(3,4)の計算は、引数の小さな値から最初に見えるほど簡単でも短くもありません。アッカーマン関数の複雑さ (反復ステップの数) は、計算結果と同様に、その引数とともに急速に増大します。

ウィキペディアからのアッカーマン関数の定義は次のとおりです。

ここに画像の説明を入力

ご覧のとおり、すべての反復でmの値が減少し、最終ステップで0に達し、その時点でn (+1) の最終値が答えになります。したがって、答えを得るには、再帰的な反復を行うときにnがどのように変化するかを追跡するだけで済みます。アッカーマン関数が急速に成長する理由については、wiki のこのサブセクションを参照してください。

Joran Beasley が既に述べたように、ウィキペディアに書かれているように、A(3,4)は確かに 125 です。ただし、この結果に至るまでのプロセスはそれほど短くはありません。実際、私が知ったように、A(3,4)を取得するには、再帰315アッカーマン関数の値を計算する必要があり、必要な反復回数はそれにほぼ比例します。

この結果がどのように得られるかをまだ視覚化したい場合は、このページを見てください。このページでは、すべての再帰ステップの計算がアニメーション化されています。ただし、ここでA(3,4) のアニメーションが完了するまでには永遠に時間がかかることに注意してください。

于 2012-10-01T18:13:08.553 に答える
9

説明を出力するバージョンは次のとおりです。

def A(m, n, s="%s"):
    print s % ("A(%d,%d)" % (m, n))
    if m == 0:
        return n + 1
    if n == 0:
        return A(m - 1, 1, s)
    n2 = A(m, n - 1, s % ("A(%d,%%s)" % (m - 1)))
    return A(m - 1, n2, s)

print A(2,2)

引数が 2,2 の場合、出力は次のようになります。(3,4ではもうちょっとやり過ぎです)

A(2,2)
A(1,A(2,1))
A(1,A(1,A(2,0)))
A(1,A(1,A(1,1)))
A(1,A(1,A(0,A(1,0))))
A(1,A(1,A(0,A(0,1))))
A(1,A(1,A(0,2)))
A(1,A(1,3))
A(1,A(0,A(1,2)))
A(1,A(0,A(0,A(1,1))))
A(1,A(0,A(0,A(0,A(1,0)))))
A(1,A(0,A(0,A(0,A(0,1)))))
A(1,A(0,A(0,A(0,2))))
A(1,A(0,A(0,3)))
A(1,A(0,4))
A(1,5)
A(0,A(1,4))
A(0,A(0,A(1,3)))
A(0,A(0,A(0,A(1,2))))
A(0,A(0,A(0,A(0,A(1,1)))))
A(0,A(0,A(0,A(0,A(0,A(1,0))))))
A(0,A(0,A(0,A(0,A(0,A(0,1))))))
A(0,A(0,A(0,A(0,A(0,2)))))
A(0,A(0,A(0,A(0,3))))
A(0,A(0,A(0,4)))
A(0,A(0,5))
A(0,6)
7
于 2012-10-01T18:30:24.617 に答える
3 
ackerman(3,4) 

=ackerman(2,ackerman(3,3)) = ackerman(2,61)    #ackerman(3,3) = 61 ...
=ackerman(1,ackerman(2,60)) = ackerman (1,123)  #ackerman(2,60) = 123...
=ackerman(0,ackerman(1,122)) = ackerman (0,124)  #ackerman(1,122) = 124...
= 124+1 = 125

視覚化するには、http: //goo.gl/jDDEAを参照してください ( 視覚化するackerman(2,3) には長すぎました 3,4)。

于 2012-10-01T17:36:34.830 に答える