# Need help coding/creating a recursive list

I have two lists A and B, each with 99 real numbers. I want to form a list, C, whose elements are functions (F[]) of A and B, and also previous elements of C itself.

C ={F[A1/B1], F[A2/(B2-A1/C1)], F[A3/(B3-A1/C1-A2/C2)], ..., F[A99/(B99-A1/C1...-A98/C98.)]}


where the integers after A, B, and C, are element indices.

I appreciate any tips on how to code this in Mathematica.

-

A pretty good puzzle, perhaps best solved using FoldList. :-)

Note: you should not start user Symbol names with capital letters as these may conflict with internal functions.

I use the carried expression of FoldList to keep track of three elements that are (re)used at each step. These are {sum, a0, c}:

sum: the denominator apart from the current $b$ value.
a0: The $a$ value from the previous step.
c: the $c$ value from the previous step.

This triplet is then fed, along with the "current" $(a, b)$ pair to the function next.
At the end we take the third element of every list (the $c$ values), and drop the seed list {0, 0, 1}, done concisely with Part using [[2;;, 3]].

aList = {"a1", "a2", "a3", "a4"}; (* example data *)
bList = {"b1", "b2", "b3", "b4"}; (* example data *)

next[{sum_, a0_, c_}, {a_, b_}] := With[{x = sum - a0/c}, {x, a, f[a/(b + x)]}]

FoldList[next, {0, 0, 1}, {aList, bList}\[Transpose]][[2 ;;, 3]] // Column


If you wish to carry out this operation with arbitrary functions rather than a hard-coded f you might rewrite next to use a SubValues pattern:

next[f_][{sum_, a0_, c_}, {a_, b_}] := With[{x = sum - a0/c}, {x, a, f[a/(b + x)]}]


To use function func now in place of f:

FoldList[next[func], {0, 0, 1}, {aList, bList}\[Transpose]][[2 ;;, 3]]


Alternatively, and especially if your f is compilable you may wish to do something like this:

nextC[f_] :=
Compile[{{old, _Real, 1}, {new, _Real, 1}},
With[{x = old[[1]] - old[[2]]/old[[3]]}, {x, new[[1]], f[new[[1]]/(new[[2]] + x)]}]
]


This is an order of magnitude faster than the simple version on my test:

aList = RandomReal[99, 150000];
bList = RandomReal[77, 150000];

FoldList[next[Mod[#, 7] &], {0, 0, 1}, {aList, bList}\[Transpose]][[2 ;;, 3]] //
Timing // First

FoldList[nextC[Mod[#, 7] &], {0, 0, 1}, {aList, bList}\[Transpose]][[2 ;;, 3]] //
Timing // First

0.624

0.062


Note my use of the backtick () to declare the seed values as machine-precision Real numbers, to match the Compile function's specification. See this for more information.

-
Wow! Great! Thanks! –  Garcia Mar 14 at 2:25
@Garcia I realize this may not be easy to read; as I said your question was a pretty good puzzle. If you have trouble please let me know and I shall do my best to explain it. I think I'll add a few notes to the answer proactively. –  Mr.Wizard Mar 14 at 2:26
I am a retired scientist with years of experience with programming, but practically none with Mathematica. (I actually tried MuSimp/MuMath on a TRS-80 yrs ago :-) But I really enjoyed your answer....yea, enjoyed. I have a lot to learn.... thanks again. –  Garcia Mar 14 at 3:05
@Garcia Thanks, it makes me happy to hear that. I think you'll enjoy Mathematica. –  Mr.Wizard Mar 14 at 3:08
@Garcia in case you read my Addendum and were confused by it: I pasted the wrong code into the body of the nextC function when I posted it; please look again. –  Mr.Wizard Mar 14 at 4:36

A little late to this question, but here is a fairly straightforward way to handle this. Define the two variable arrays by

m=4;
aa = Array[a, m];
bb = Array[b, m];


and then define functions that will create the arguments of f. For convenience, this can be broken into two pieces: den is the repetitive part of the denominator and arg is the argument of the function at the nth iteration. bigC calculates the intermediate values, and then the Table command creates the full desired vector (the C in the OPs notation, with the C's fully substituted in).

den[n_] := Sum[aa[[i]]/c[i], {i, n}];
arg[n_] := aa[[n]]/(bb[[n]] - den[n - 1]);
bigC = f /@ arg /@ Range[m];
Table[c[i] = bigC[[i]], {i, m}]
`

-
@Mr. Wizard --- I missed that the c's were to be created from the previous entries in the big vector. I think I've fixed it up so it now agrees with the OPs request. –  bill s Jul 18 at 2:38
Nice simple fix. +1 :-) –  Mr.Wizard Jul 18 at 7:16