# Problem with a simple recursive function

f[2 x_] := f[x]
f := 3
f := 0
f[2 x_ + 1] := f[x] + f[x + 1]
a[x_] := f[x]/f[x + 1]


Will this work as an recursive function ? I think there's something wrong with this because every integer will get an output of 3

any help would be appreciated, thank you so much

• From what I'm guessing you're trying to get, I think you'll find fn = NestList[1/(1 - # + 2 Floor[#]) &, 0, #] &; most efficient to generate the first n terms, e.g. fn will generate the result from index 0 to 1000000.
– ciao
Apr 15, 2019 at 7:34
• The reason this does not work, is because you can't match an integer to something like 2 x_ + 1: MatchQ[7, 2 x_ + 1] (* False *). An integer is just an integer: it's not structurally equal to an addition. The pattern matcher is not for matching mathematical patterns like these. Only structural ones. Besides, there's nothing in the pattern 2 x_ + 1 that even limits x to be an integer. Apr 15, 2019 at 12:25

Perhaps try this

f := 0;
f := 3;
f[x_/;EvenQ[x]] := f[x/2];
f[x_/;OddQ[x]] := f[(x-1)/2] + f[(x-1)/2 + 1];
a[x_] := f[x]/f[x + 1];
Table[{i,a[i]},{i,0,6}]


with output

{{0, 0}, {1, 1}, {2, 1/2}, {3, 2}, {4, 1/3}, {5, 3/2}, {6, 2/3}}


Please check this carefully to make certain I haven't made any mistakes

• This is close to just nitpicking, but I'd personally use ?EvenQ and ?OddQ instead of /;EvenQ[x] etc here. For more complicated pattern matches, the ? notation seems to be faster typically. In this case, the difference isn't noticeable until x values of around 2^1024 on my machine and the recursion limit comes into play first, but I figured it should be noted. Apr 14, 2019 at 6:34
• Thank you so much, I really appreciated your help. Apr 14, 2019 at 8:24

If you want to go to large values of $$x$$, then some memoization will speed up your recursion dramatically:

f = 0;
f = 3;
f[x_?EvenQ] := f[x] = f[x/2];
f[x_?OddQ] := f[x] = f[(x - 1)/2] + f[(x + 1)/2];
a[x_] := f[x]/f[x + 1]


try it out:

f // AbsoluteTiming


{0.000245, 32838}