Rekursion - Funktion gesucht

Question

Das Thema ist Rekursion.

Folgende Funktion ist definiert:
f: N0 --> N0

f(0)=f(1)=1

Für n = 2m+1, m>0: f(n) = F ((n-1)/2)+f(n-2)

Für n = 2m, m >0: f(n) = f(n/2)

Kann mir wer helfen und mir sagen wie die Funktion lautet, wenn ich bestimmte punkte ausrechnen möchte, zB: F( 864) =

Answer 1

Das ist eine Kleinigkeit für den Iterationsrechner:

http://www.gerdlamprecht.de/Roemisch_JAVA.htm##@N@B0]=@B1]=1;i=2;@N@Bi]=(i%252%3C1)?@Bi/2]:@B(i-1)/2]+@Bi-2];@Ni%3E865@N0@N0@N#

(LINK endet mit N# und beinhaltet den Code)

Sie scheint mit A030067   "Semi-Fibonacci numbers" übereinzustimmen.

Answer 2

f(864)=f(432)=f(216)=f(108)=f(54)=f(27)=f(13)+f(25)
= f(6) + f(11)   +   f(12) + f(23)
= f(3) + f(5)                  +f(9)   +   f(6) + f(11)+f(21)
= f(1)+f(1) + f(2)+f(3)+f(4)+f(7)   +   f(3) + f(5)+f(9)+f(10)+ f(19)

etc bis du überall bei f(0) oder f(1) angekommen bist.

Besser ist vielleicht erstmal von f(2) bis f(10) alles zu berechnen, dann
muss man nicht so sehr lange rekurrieren.