I wrote 2 simple recursive functions for calculating the power of a table.

pol3[Tb_List, n_Integer?Positive] := If[n == 1, Tb, Tb.pol3[Tb, n - 1]]


pol4[A, 1] := A 
pol4[A, n_Integer?Positive] := A.pol4[A, n - 1]

Tb, A are 3x3 arrays. Functions works for n<255 but if I try to call them for n=256 or greater then I take wrong results and the message:

$RecursionLimit::reclim: Recursion depth of 256 exceeded

I'm not very familiar with the Mathematica so I would appreciate any ideas on what I'm doing wrong.

  • $\begingroup$ You can find more information here: stackoverflow.com/questions/4481301/…. The main thing is to realize that functions like these "are" replacement rules. $\endgroup$ Commented Apr 9, 2013 at 8:55
  • $\begingroup$ Note that pol4[A_, 1] := A and pol4[A_, n_Integer?Positive] := A.pol4[A, n - 1] (with the underscores) is probably closer to what you want $\endgroup$ Commented Apr 9, 2013 at 9:06
  • $\begingroup$ Thank you. I'll check the previous message a little later. $\endgroup$
    – npap
    Commented Apr 9, 2013 at 9:23

1 Answer 1


Let me walk you through the evaluation of your function. Note that you can use Trace to see how your function evaluates. I particularly like Trace with the Option TraceOriginal-> True.

Anyway in Mathematica there is something called the "Main Loop", determining how expressions get evaluated. It is good to realize that in "simple cases" (non simple cases would include cases in which functions have Attributes or functions like Evaluate or Unevaluated are present) the arguments of any function will be evaluated before rules associated with the function itself will be used.

Suppose for convenience that A is not set. And suppose for convenience that you used the underscores as I suggested in my comment.

pol4[A,10] will evaluate as follows

first Mathematica will evaluate A and 10. As it is, evaluating them will just yield A and 10 again respectively. When Mathematica has evaluated all the arguments, it will find rules associated with "the head" (function that surrounds the expression being evaluated) pol4. It finds your rule pol4[A_, 1] := A (or maybe you can think of it like HoldPattern[pol4[A_,1]]:> A (which is really a rule that was generated by your definition that can be retrieved by doing DownValues[pol4])). This rule does not match however, so Mathematica moves on to the next rule, which is the rule associated with pol4[A_, n_Integer?Positive] := A.pol4[A, n - 1]. So far so good.

We get, after applying this rule

A.pol4[A, 9]

This expression has as its fullForm

A.pol4[A, 9] // FullForm

-> Dot[A,pol4[A, 9]]

Mathematica looks at the first argument of Dot, A, but there is nothing to do. Then it looks as the second argument (before evaluating Dot). This is where you might start to feel worried. We are going to evaluate pol4[A,9] before evaluating Dot. pol4[A,9] will evaluate similarly to pol4[A,10] and there will be another Dot function that will be evaluated only after all the pol4's are evaluated. If more than 255 Dots are generated this way, your recursionlimit is reached.

I like to think of the stack as just a tree of expressions. We would have after two iterations

Dot[A, evaluating ----> Dot[A, pol4[A, 8]]]

and after three iterations

Dot[A, Dot[A, evaluating ----> Dot[A, pol4[A, 7]]]]

Do you see all how a lot of Dot's get put on the Stack?


I'm not exactly sure what kind of solution you are after. If you just want to take the power of a matrix, you can do

MatrixPower[A, 1000]

If you want to apply some function iteratively, you can do

With[{A = A},
 Nest[A.# &, A, 1000]

The "what Jacob calls the Mr.Wizard style of doing things" would be

ggg[n_, total_] := ggg[n + 1, A.total];
ggg[1000, total_] := total

ggg[1, A]

Which is a nice example of an "tail recursion" that does not reach $RecursionLimit. If you want to have tools for automatically getting tail recursions, you might want to use (not study, it is very advanced) Leonids Answer here. Below that is the answer what the "Mr.Wizard style of doing things" refers to.

I suppose Mr.Wizard would argue that something like the above can always be written as

Fold[A.# &, A, Range[1000 - 1]]

Which he would never use as there is the possibility to use Nest and of course MatrixPower in this case... But still :). The last two approaches can be ideas for cases in which you want to "do something with your counter".

  • $\begingroup$ ggg[n_, total_, a_] := ggg[n + 1, a.total, a]; ggg[1000, total_, a_] := total; A = {{2, 0}, {0, 2}}; ggg[1, A, A] $\endgroup$ Commented Apr 9, 2013 at 12:22
  • $\begingroup$ @belisarius Ah, of course, it is nice to pass A rather than refering to at is a constant. Much more "functional", but let me correct the Nest example first! $\endgroup$ Commented Apr 9, 2013 at 12:44

Your Answer

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

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