Преобразование кусочно-рекурсивной функции в нерекурсивную функцию?

Question

Мое математическое образование распространяется только через исчисление, и я обнаружил, что хочу преобразовать кусочно-рекурсивную функцию в единицу без рекурсии. Есть ли способ сделать это, не полагаясь на поиск паттернов или подобную грубую силу? (Возможно ли это вообще?)

В частности, функция: (для всех целых чисел)
е (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)

Я знаю this similar question, но ответ, связанный с матрицами, находится вне меня. Если есть объяснение, требующее меньше знаний, я бы очень признателен ему.

Answer 1

Edit:
По вашему комментарию, вы, вероятно, потребуется некоторое быстрое решение, не нужно Interative один. Я проверил размер дерева рекурсии - это удивительно мало - около 250 для 10^18 (грубо - log2(M) уровней рекурсии, около 3 + i значений на i-м уровне). Поэтому я реализовал рекурсию с memoization (своего рода 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;