# Speeding Up Recursive Evaluation

I have a recursive function for which I need the values for n=1 through about n=100,000,000 (or more). The function looks as follows, with output of the form ({x,y},a), and f, g, and h some functions.

coordinates[n_]:=coordinates[n]={{coordinates[n-1][[1]][[1]] +f[n, coordinates[n-1][[2]]], coordinates[n-1][[1]][[2]]+g[n, coordinates[n-1][[2]]]}, coordinates[n-1][[2]]+h[n]}


I then compute:

Table[coordinates[n][[All,1]], {n, 100,000,000}.


I can get up to a few million with about 4 hours of calculation time, but 100,000,000 causes my computer to crash and restart, stating "kernel panic" (I am not very familiar with programming unfortunately). Any advice about how to make such a table more easily calculated would be much appreciated!

• In your definition of coordinates[n_] where is n actually being used in the calculation? Also, you say f and g are functions but they have parentheses rather than square brackets. In the Wolfram Language, arguments to functions should be surrounded by square brackets. Is it possible to post f and g, or are they very long? – MassDefect Feb 11 at 19:52
• What are the coordinates[[1]][[1]] supposed to refer to? Should they be something like coordinates[n-1][[1,1]]? – Roman Feb 11 at 19:57
• @MassDefect - yes, f and g are functions... they are rather long, and not really pertinent to the question, so I just gave the structure of the main function! – user413587 Feb 11 at 20:38
• @Roman I was referring to coordinates[n-1][[1]][[1]]... is that the same as coordinates[n-1][[1,1]]? – user413587 Feb 11 at 20:40
• @HighPerformanceMark I am attempting to plot the (x,y) coordinates in the first position of each output, and do need them all (or at lease a representative subset). – user413587 Feb 11 at 20:41

It looks like your recursion only depends on the previous value, but you are still trying to build up an awfully big table, which is possibly crushing your kernel. Use writing to the disk (hopefully an SSD) to capture the data. Simplified problem that hopefully captures the flow:

Simple recursion using memoization

fn[x_] := fn[x] = 1 + fn[x - 1];
fn[0] = 1;


Do it via memoization and capturing results in a table.

memBefore = MemoryInUse[];
res = Table[fn[i], {i, 10000}];
memAfter = MemoryInUse[];
memAfter - memBefore
(*  1813536 *)


Fast, but a memory hog for both the table and memoization.

Now don't memoize, and write each value to the hard drive that then creating a table. It slows the loop, but you'll not soak up any active memory.

memBefore = MemoryInUse[];
last = 1; Do[(current = 1 + last; current >>> "temp.csv"; last = current), {i, 10000}]
memAfter = MemoryInUse[];
memAfter - memBefore
(*  6264  *)

• This should work - thank you!! – user413587 Feb 11 at 22:37
• Is there any way to speed this process up? Even with a SSD, It's taking me about 7 secs per 1000 entries, which is way too slow? Thanks! – user413587 Feb 13 at 19:36
• You could probably "bound" your way through the data, building up a table of 1,000,000 values and writing those to a disk, and then repeating. The disk write for each iteration is no doubt taking too long. – MikeY Feb 13 at 19:48
• Great idea, thank you! – user413587 Feb 13 at 21:40