スタックレベルが深すぎる（SystemStackError）

Question

私はこの簡単な計算をしたいが、スタックの深さがそれほど深くないと言うと、nのように4である。ここでは適用できません。なぜなら、ベースケースに達したときに累積された値だけを加算するからです。

RubyVM::InstructionSequence.compile_option = { 
:tailcall_optimization => true, 
:trace_instruction => false 
} 

def recursively_count_paths(x , y, n) 
if x == n && y == n 
    return 1 
    puts " we got a path people" 
elif x == n 
    puts "x is done" 
    return recursively_count_paths(x, y + 1, n) 
elif y == n 
    puts "y is done" 
    return recursively_count_paths(x + 1, y, n) 
else 
return (recursively_count_paths(x + 1, y, n) + 
recursively_count_paths(x, y + 1, n)) 
end 
end 

recursively_count_paths(0, 0, 20) 

私は他の場合に戻ることはありませんか？

Answer 1

この場合、テール再帰は関係ありません。再帰的にメソッドを呼び出すので、コンパイラはその最適化を行うことができません。これらの呼び出しのほとんどは不要です。最初の行が範囲外であり、それらをカウントしないパスを探し

def recursively_count_paths(x, y, n) 
    return 0 if x > n or y > n 
    return 1 if x == n && y == n 
    return recursively_count_paths(x+1, y, n) + recursively_count_paths(x, y+1, n) 
end 

：私はあなたにコードを書き換えることができました。 2行目は、最初のifステートメントに相当します。パスが完了すると1を返します。最後の行は最終的なreturnの文と同じで、単純にすべてのパスを北に、すべてのパスを東に追加します。 recursively_count_pathsを2回呼び出すので、テールコールの最適化はまだ役に立ちません。

n = 20を使用して実行すると、しばらく時間がかかることがあります。これは、グリッドのサイズが大きくなるにつれて指数関数的に長くなるためです。これは同じサブパスを何度も何度もカウントするためです。 Project Euler Problem 15でもありますので、私はここで解決策を提供しません。しかし、私はあなたにヒントを与えます：あなたの仕事を保存します。