# defining recursively a function with multiple if conditions

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.

-
You can use NestWhile to implement recursive functions. – image_doctor Jan 9 '13 at 11:46
You need to define a starting value for A[x,0,l], and memoize your function, I think. – Verbeia Jan 9 '13 at 11:47
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? – jVincent Jan 9 '13 at 14:10
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. – Simon Woods Jan 9 '13 at 16:33

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_] :=
Piecewise[{
{(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}]


-
Thank you. This was really usefull! Although I would like to understand why my example doesn't work... – Lorenzo Jan 9 '13 at 14:17
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. – whuber Jan 9 '13 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}]


-
This example works only for l=n, I have just tried... – Lorenzo Jan 9 '13 at 14:13
@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. – Simon Woods Jan 9 '13 at 16:36
@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. – image_doctor Jan 9 '13 at 16:59