1
$\begingroup$

I'm trying to create a certain "excel-like" recursive function, which runs through a pre-defined list and performs an operation dependent upon the current position (similar to the "drag down" type functionality of Excel). Here is some example code, where "m" is the list:

alt[x_] := If[Mod[x, 4] == 3 || Mod[x, 4] == 1, 0, If[Mod[x, 4] == 2, 1, -1]]

ex[x_] := ex[x] = ex[x - 1] + alt[x]*m[[x]]

ex[1] = 0
(* 0 *)

$RecursionLimit = Infinity
(* ∞ *)    

ex[10000]

However when evaluating at a large point, the program quits the calculation without an error. Thanks so much for any advice!

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Can you provide a minimal example of what you want to happen given a simple input? It sounds like what you want should be fairly simple in Mathematica, but I'm not clear on what it is that you're looking for. If you have a list list1 = {1, 2, 3, 4, 5} and you want to multiply each by 2, you can easily do that with 2*list1. If what you're doing depends on the position in the list, try something like Table[list1[[i]] * i, {i, 1, Length[list1]} (this outputs {1, 4, 9, 16, 25}), where i becomes the position in the list. $\endgroup$
    – MassDefect
    Jan 28, 2019 at 2:08
  • $\begingroup$ I just updated the post with part of what I'm working on... I hope that clarifies! Thanks for this tip. I tried something similar, but am still running into the issue... $\endgroup$
    – user413587
    Jan 28, 2019 at 4:02
  • $\begingroup$ Recursion can often be much more memory hungry than a direct algorithm. The system has to keep track of the huge numbers of calls on the stack and Mathematica is clearly running out of memory. Try writing a direct algorithm to do this, eg using nest. You’ll probably get significantly better performance too. $\endgroup$
    – b3m2a1
    Jan 28, 2019 at 17:50

2 Answers 2

Reset to default
0
$\begingroup$

Your example illustrates what you're looking for fairly nicely. One thing I might recommend in the future is sample code for generating m such as:

SeedRandom[1234];
m = RandomInteger[{-100, 100}, 10000];

This produces a random set of integers between -100 and 100 that anyone with Mathematica can reproduce for themselves.

[With your example, I think the problem is that the recursive function takes up too much memory. Unfortunately, the Mathematica front-end is still 32-bit (although I believe that will change in the next few months with the release of MMA 12).] EDIT: As b3m2a1 pointed out, this reason is not correct, however the following should still work:

mylist = Table[ex[i], {i, 10000}]

Due to the memoization you have defined in your function, once ex[2] is called, MMA now knows the value of ex[2] so that on the subsequent call of ex[3] it does not have to do any recursion but instead calls ex[2] + alt[3]*m[[3]] which evaluates to 6 + 0 * -93, rather than ex[2] + 0 * -93. With the Table each step of ex[i] is stored before ex[i + 1] is called.

Improve this answer
$\endgroup$
2
  • $\begingroup$ This should fundamentally be a kernel issue. If you’re not trying to display things it’s not gonna be an FE issue and in any case when the FE crashes it takes everything with it. $\endgroup$
    – b3m2a1
    Jan 28, 2019 at 16:57
  • $\begingroup$ @b3m2a1Hmmm, you're right. I thought it was because the output wasn't being suppressed in the call to the recursive function, but it actually only outputs a single number to the FE, doesn't it? I didn't think that the recursion would take up that much memory, but I suppose it does. $\endgroup$
    – MassDefect
    Jan 28, 2019 at 17:22
2
$\begingroup$

If you can write a non-recursive algorithm, generally you should. The system has to keep track of each call on the stack when using recursion and this quickly becomes prohibitively expensive. Intelligent programming languages will sometimes optimize this away, but Mathematica is unable to do that.

Instead, here's a direct method you can use that works much better:

m=BlockRandom[RandomReal[{}, 1000000]];

alt[x_] := If[Mod[x, 4] == 3 || Mod[x, 4] == 1, 0, If[Mod[x, 4] == 2, 1, -1]]
ex//Clear
ex[x_] := ex[x] = ex[x - 1] + alt[x]*m[[x]]
ex[1] = 0;

Block[{$RecursionLimit=Infinity}, ex[10000]]//AbsoluteTiming

{0.167177,-22.8191}

bleh[list_, n_]:=
 Module[
  {
   alts=Which[Mod[#, 4] == 3 || Mod[#, 4] == 1, 0, Mod[#, 4] == 2, 1, True,-1]&/@Range[2, n],
   vaccuum
   },
  vaccuum=alts*list[[2;;n]];
  Total[vaccuum]
  ]

bleh[m, 10000]//AbsoluteTiming

{0.005237,-22.8191}

bleh[m, 1000000]//AbsoluteTiming

{0.258926,-202.234}

Notice that it doesn't crash at n=1000000

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks so much for the help! I'm new to Mathematica and trying to figure out this code, which I'm sure is the best solution. I accepted @MassDefect simply because I was familiar with the code he used. $\endgroup$
    – user413587
    Jan 29, 2019 at 4:31
  • $\begingroup$ @user413587 I do not mind in the slightest. It is a good idea to get used to restructuring a recursive algorithm as a more direct one. This will help you no matter what the language. Recursion can be very expensive. $\endgroup$
    – b3m2a1
    Jan 29, 2019 at 4:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.