조각 별 재귀 함수를 비 재귀 함수로 변환 하시겠습니까?

Question

나의 수학 교육은 미적분을 통해서만 확장되며, 나 자신이 재귀없이 조각 별 재귀 함수를 하나의 것으로 변환하고자하는 것을 발견했습니다. 패턴을 찾는 것과 비슷한 무력에 의존하지 않고 이것을 할 수있는 방법이 있습니까? (전혀에도 가능한가?)

즉, 함수는 (모든 정수에 대해)
F (0) 1
F (1) = 1
F (2) = 2
를 = (2n + 1) = f (n-1) + f (n) + 1 (n (n)에 대해) f (2n) + f > = 1)

나는 this similar question을 알고 있지만 행렬에 관련된 대답은 나를 넘어선 다. 지식이 부족한 설명이 있다면 크게 감사하겠습니다.

Answer 1

편집 :
귀하의 의견에 따르면, 당신은 아마도 빠른 해결책을 필요로하지 않을 것입니다. 재귀 트리의 크기를 확인했습니다 - 놀랍도록 작은 - 10^18 (대략 -재귀 수준, i 번째 수준의 값은 3 + 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) 

오래된 물건 그대로 질문을 주소 : 고급 수학에 대한 일반적인 해결책을 발견하지 않으려면
, 당신이 계산 된 값을 저장해야합니다. 그렇지 않은 프로그램에 대해, 수학에 대한 때문에

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;