Problem with a simple recursive function

Question

f[2 x_] := f[x]
f[1] := 3
f[0] := 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[1000000] 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. — Sjoerd Smit, Apr 15, 2019 at 12:25

Bill · Accepted Answer · 2019-04-14 06:24:36Z

2

Perhaps try this

f[0] := 0;
f[1] := 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

answered Apr 14, 2019 at 6:24

Bill

11.8k12 silver badges13 bronze badges

2

$\begingroup$ 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. $\endgroup$
– eyorble
Apr 14, 2019 at 6:34
$\begingroup$ Thank you so much, I really appreciated your help. $\endgroup$
– Gokturk gokturk
Apr 14, 2019 at 8:24

Add a comment |

Roman · Accepted Answer · 2019-04-14 09:30:22Z

1

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

f[0] = 0;
f[1] = 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[873813] // AbsoluteTiming

{0.000245, 32838}

answered Apr 14, 2019 at 9:30

Roman

46.2k2 gold badges50 silver badges120 bronze badges

Add a comment |

2 Answers 2