この関数をテール再帰にするにはどうすればいいですか？

Question

let rec hf0 k n = 
if n <= k then n 
else 
    let rec loop i = 
     if i > k then 0 else hf0 k (n - i) + loop (i + 1) 
    in 
    loop 1 

そこに再帰関数の合計があるので、どのように行うのかわかりません。

（コードのおかげで@Jeffreyスコフィールド）

Answer 1

末尾再帰はここにあなたの最大の問題ではありません。再帰的な関数を尾部の再帰的なものにすることは、通常、スタックからヒープへの線形または近似的な再帰のメモリ使用量を移動させるのに役立ちます。後者があふれにくいために実行されます。

あなたのケースでは、はるかに早い（それははるかに小さいですがn-k）あなたは極端な実行時間に遭遇するので、スタックオーバーフローが問題の多くを見ることができません。その理由は、あなたの再帰が線形から非常に遠いということです。それはkで分岐します。

適用する手法は動的プログラミングです。副次的な注意（実装にもよる）として、スタック使用量を一定にすることもできます。

[編集] コメントでは、あなたの質問は学問的だと指摘しています。尾の再帰を主張する場合、いくつかのオプションがあります。

1. 関数呼び出しには1つのテールしか指定できません。したがって、厳密に言うと、末尾再帰は、すべての再帰呼び出しではなく、最後の再帰呼び出しにのみ適用できます。この場合、アキュムレータを使用して簡単に達成できます。非テール再帰を使用して1つのターム以外のすべての合計を計算し、最後のタームにテール再帰を使用して、アキュムレータを介してパーシャルサムを渡します。

2. 再帰関数の実行により、呼び出しツリーを関連付けることができます。あなたの場合、ツリーの高さはn-k、非リーフの子はkになります。コントロールの流れは、その木を深く先ず歩くことを模倣します。この深さ優先ウォークは、1つのループでシミュレートできます。 （追跡する必要があるツリー内の位置は、呼び出しスタックとなる位置に密接に対応しています。）次に、末尾再帰を使用してこのループを実装できます。

Answer 2

あなたのコードはOCamlではなく、完全に理解できません。

let hf k n = 
    let prev = Array.make k 0 in 
    let rec ihf m = 
     let res = 
      if m <= k then m else Array.fold_left (+) 0 prev 
     in 
     if m >= n then 
      res 
     else 
      begin 
      Array.blit prev 0 prev 1 (k - 1); 
      prev.(0) <- res; 
      ihf (m + 1) 
      end 
    in 
    if n <= k then n 
    else if k <= 1 then k 
    else ihf 0 

このコードは@kneとしてのk> = 0

を前提として簡単にするために：

let rec hf0 k n = 
    if n <= k then n 
    else 
     let rec loop i = 
      if i > k then 0 else hf0 k (n - i) + loop (i + 1) 
     in 
     loop 1 

ここで末尾再帰バージョンがあります：しかし、私の推測では、あなたがこの機能を探しているということです中間計算をスタックからヒープに移動することで動作します。特に、配列prevの以前の値を追跡します。

更新

この関数は、フィボナッチのような計算の簡単な一般化だから変換するのはかなり簡単です。

一般に、continuation passing styleを使用して任意の計算を末尾再帰的に変換することができます。