なぜパラメータベースの定義は再帰よりも効率的ですか？

Question

私は再帰関数sumdown :: Int - > Intを持っています。これは、その引数からゼロまでのすべての自然数を の合計で返します。 sumdown 3は、合計3 + 2 + 1 + 0 = 6

sumdown :: Int -> Int 
sumdown 0 = 0 
sumdown x = x + sumdown(x-1) 

を返す必要があります私はまた、誰かが私のためにこれを評価し、その理由よりも、その潜在的に、より効率的な教えてください可能性があり、私は完全に理解しないこの定義を持っています上記の定義は？

sumdown n = sumd n 0 
sumd 0 a = a 
sumd n a = sumd (n-1) (n+a) 

ありがとうございます。

Answer 1

第再帰和は、その端部（n）から出発[0..n]値、このような：この方法で

1+(2+(3+(... + ((n-1) + n)) ...))) 

、プログラムは最初の完全なシーケンスを生成する、すべての番号を列挙しており、後にのみその加算は実際に実行することができる。

これには、O（n）メモリとO（n）時間が必要です。第二の再帰で

我々が以前に行ったように、我々は0からnに数えるが、私たちが行くように、我々は3にカウントアップする前に

(((1+2)+3)+4)+ ... 

に我々は1+2合計することができますように、今、私たちは、数字を合計します。その後、前の合計の結果をそのまま残すことができます。1+2、1と2をメモリから破棄します。したがって、プロセス全体において、我々は1）今までに遭遇した数の合計の結果と、2）シーケンスの次の数だけを記憶しておく。

したがって、O（1）メモリとO（n）時間だけが必要です。

注：Haskellは遅延型であるため、上記の議論は、部分集計がすべての再帰で実際に強制される場合にのみ保持されます。この強制は、コンパイラオプティマイザによって静かに追加されるかもしれませんが、明示的にすることをお勧めします。 in

sumdown n = sumd n 0 
sumd 0 !a = a 
sumd n !a = sumd (n-1) (n+a) 
-- here I am using the BangPatterns extension, 
-- otherwise, seq can be used instead 

第2回目の再帰は、通常「アキュムレータスタイル」と呼ばれ、「末尾再帰」の特定のケースです。

（注2：末尾再帰は常にHaskellのような怠惰な言語では良いアイデアではありませんが、周りに渡されたデータは、シンプルであれば、例えば番号のようではなく、リストが好き、末尾再帰は通常有益である。）

Answer 2

2番目の関数はtail-recursiveです。これを実行する理由は、削減手順に従うと明確に見えます。 （ハスケルの怠惰な性質に起因ますが、次は純粋に正しいではありませんが、それは再帰関数をより効率的にすることができますどのように尾のアイデアを提供します。）ほとんどの言語でさらに

sumdown 3 
// 3 + sumdown 2 
// 3 + (2 + sumdown 1) 
// 3 + (2 + (1 + sumdown 0) 
// 3 + (2 + (1 + 0)) 
// 3 + (2 + 1) 
// 3 + 3 
// 6 


sumdown 3 0 
// sumdown 2 3 
// sumdown 1 5 
// sumdown 0 6 
// 6 

、末尾再帰コード同じスタックを再利用するように最適化されています（再帰関数の最後の操作と同じです）。