将分段递归函数转换为非递归函数

Question

我的数学教育只延伸到微积分，我发现自己渴望将分段递归函数转换为没有递归的函数。 有没有办法在不依赖模式查找或类似蛮力的情况下做到这一点？（甚至可能吗？

具体来说，函数为：（对于所有整数）
f（0） = 1
f（1） = 1
f（2） = 2
f（2n） = f（n） + f（n + 1） + n （对于 n> 1）
f（2n

+ 1） = f（n - 1） + f（n） + 1 （n>= 1）

我知道这个类似的问题，但涉及矩阵的答案超出了我的范围。 如果有一个需要较少知识的解释，我将不胜感激。

Answer 1

编辑：
根据您的评论，您可能需要一些快速的解决方案，而不是必要的交互式解决方案。我已经检查了递归树的大小 - 它非常小 - 大约 250 对于 10^18（大约 - log2(M) 级递归，大约 3 + i 个级别的值）。所以我用记忆（一种DP）实现了递归，这种方法在M = 2^80-1 ~ 10^24时非常快。

M = 1208944266358702884257791
Result = 24682648998311664639366438  
Map Size 321

伪代码：

  function F(Key)
     if Map.Contains(Key)then
        return Map.Value[Key]
      else
         usual recursion calls to get Result
         Map.Add(Key, Result)

从字面上解决问题的旧东西：
如果你不想发现高等数学的一般解决方案，你必须存储计算值。这是用Delphi编写的非递归（迭代）函数的示例，使用队列作为存储：

function ExoticFib(m: Integer): Integer;
var
  Q: TQueue<Integer>;
  n, fnm1, fn, fnp1, n2, n21: integer;
begin
  if m <= 3 then
    Exit(m + Ord(m = 0));  //return 1, 1, 2, 3
  Q := TQueue<Integer>.Create;
  Q.Enqueue(3);
  fn := 1;
  fnp1 := 2;
  for n := 2 to m div 2 do begin
    fnm1 := fn;      //forget the oldest value
    fn := fnp1;
    fnp1 := Q.Dequeue;  //here we have f(n-1), f(n), f(n+1)
    n2 := fn + fnp1 + n;
    Q.Enqueue(n2);
    n21 := fnm1 + fn + 1;
    Q.Enqueue(n21);
  end;
  if Odd(m) then // for m = 2k+1
    Result := n21
  else           // for m = 2k
    Result := n2;
  Q.Free;
end;