I am trying to recursively define a function which satisfies the following system of equations and which depends on two parameters $n$ and $l$,

$$ \begin{align} A(x, n, l) &= F[ A(x,n-1,l) ]\\ A(x, n, l) &= x^l \mbox{ if } l = n \\ A(x, n, l) &= 0 \mbox{ if } l < n \\ \end{align} $$

In order to do this I used the following code (here I make the expression for $F$ explicit):

A[x_, n_, l_]:=
  Boole[n > l]((1 - x)/(1 + x^l) * (Sum[A[x, n-1-i, l] * x^i, {i,0,l-1}])
  + x^l/(1 + x^l)) + Boole[n == l] * x ^ l

The function defined in this way, $A(x, n, l)\;$, gives the probability that tossing a coin $n$ times gives exactly one run of $l$ consecutive $1$s, where $x$ is the probability getting $1$ on single toss and $(1-x)$ is the probability getting $0$ on single toss.

When I try to plot one of these functions, for instance,

Plot[A[x, 7, 7], {x, 0, 1}]

I encounter the following error:

RecursionLimit::reclim: Recursion depth of 256 exceeded.

Is my code wrong? Is there an other way to recursively define a function, taking into account the fact that the third condition must be satisfied for all the values $l<n$, where $l$ and $n$ are not specified at the moment of the definition.

  • $\begingroup$ You can use NestWhile to implement recursive functions. $\endgroup$ Jan 9, 2013 at 11:46
  • $\begingroup$ You need to define a starting value for A[x,0,l], and memoize your function, I think. $\endgroup$
    – Verbeia
    Jan 9, 2013 at 11:47
  • 1
    $\begingroup$ Your code doesn't seem to match your definition. For instance f depends on x not on A[x,n-1,l] as you write initially. Could you write out what F[input_] is supposed to be? $\endgroup$
    – jVincent
    Jan 9, 2013 at 14:10
  • $\begingroup$ The reason your code gives a recursion error is because Boole[condition] * expr causes expr to be evaluated whether condition is True or False. So when you evaluate A[x,7,7] Mathematica will evaluate the Sum. The first term of the Sum is A[x,6,7], and of course evaluating that leads to a Sum whose first term is A[x,5,7] and so on. $\endgroup$ Jan 9, 2013 at 16:33

2 Answers 2


I am sorry, but have hard time understanding your code with the use of Bool.

This does the same thing as you have, using Piecewise which is easier to understand

Also, hard to read l as variable name, it looks like 1. It is not a good idea to use l for variable. Also, not good idea to user UpperCase A. Changed to f.

f[x_, n_, r_] :=
   {(1 - x)/(1 + x^r)*(Sum[f[x,n-1-i,r]*x^i,{i, 0, r - 1}])+x^r/(1 + x^r),n>r},
   {x^r, n == r},
   {0, True}

Plot[f[x, 7, 7], {x, 0, 1}]

Mathematica graphics

  • $\begingroup$ Thank you. This was really usefull! Although I would like to understand why my example doesn't work... $\endgroup$
    – Lorenzo
    Jan 9, 2013 at 14:17
  • 1
    $\begingroup$ Lorenzo, did you notice that f[x,n,0] is always $1/2$ for positive $n$? (Its other values tend to be incorrect, too, which becomes obvious when you plot them.) I think the problem is not with Nasser's solution, but with your recurrence: it does not correctly give the probability you are hoping to compute. $\endgroup$
    – whuber
    Jan 9, 2013 at 16:27

Here is an alternate way of structuring the definition of your function that avoids the use of If completely by employing a combination of conditional expression evaluation and argument pattern matching:

j[x_, n_, l_] := 0 /; l < n
j[x_, l_, l_] := x^l
j[x_, n_, l_] := (1-x)/(1 + x^l)*(Sum[j[x, n-1-i,l]*x^i, {i,0,l-1}]) + x^l/(1+x^l)

And plotted:

Plot[j[x, 7, 7], {x, 0, 1}]

Mathematica graphics

  • 1
    $\begingroup$ This example works only for l=n, I have just tried... $\endgroup$
    – Lorenzo
    Jan 9, 2013 at 14:13
  • $\begingroup$ @Lorenzo, the third condition in your question uses the condition l < n when it should be n < l. image_doctor has reproduced that error in the first definition for j. $\endgroup$ Jan 9, 2013 at 16:36
  • $\begingroup$ @Lorenzo As far as I can tell there is no terminating condition in your definition of A when l > n as n is being decremented and will never equal or exceed l. $\endgroup$ Jan 9, 2013 at 16:59

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.