# Recursion evaluate Table power exceeded limit

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]]


and

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. • You can find more information here: stackoverflow.com/questions/4481301/…. The main thing is to realize that functions like these "are" replacement rules. – Jacob Akkerboom Apr 9 '13 at 8:55 • 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 – Jacob Akkerboom Apr 9 '13 at 9:06 • Thank you. I'll check the previous message a little later. – npap Apr 9 '13 at 9:23 ## 1 Answer 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? Solution 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".

• ggg[n_, total_, a_] := ggg[n + 1, a.total, a]; ggg[1000, total_, a_] := total; A = {{2, 0}, {0, 2}}; ggg[1, A, A] – Dr. belisarius Apr 9 '13 at 12:22
• @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! – Jacob Akkerboom Apr 9 '13 at 12:44