# Recursive functions taking list arguments

I wish to create a function that takes lists (e.g. {plus,plus,minus,0,minus,plus}) and uses the input list to calculate a corresponding value using a set of recursive rules.

I want the function to apply the following algorithm:

1) Read the first element of the list

2) Calculate the numbers of 'plus' in the rest of the list (i.e. the list not including the first element).

3) Based on whether the answer to part 2 is odd or even, a starting value (==1 for simplicity) is multiplied by a value, and the first element of the input list is removed.

4) Steps 1-3 are applied to the list until there is only one element left in the list. (The value of the list with one element is already known.

To take an example: Say I want to calculate the value for the list {plus,plus,minus}. It is already known that f[{minus}] = $\alpha_2$ (I define this previously) We have:

• f[plus,{...}] = ($\alpha_1-\beta_1$)*f[{...}] (even # of plus in {..})
• f[plus,{...}] = $\alpha_2$*f[{...}] (odd # of plus in {..})
• f[minus,{...}] = $\alpha_2$*f[{...}] (even # of plus in {..})
• f[minus,{...}] = $\alpha_1-\beta_1$*f[{...}] (odd # of plus in {..})

(There are also rules for f[{0,...}] but I have left them out for simplicity as they are not relevant to this example.)

f[{plus,plus,minus}] = $\alpha_2$*f[{plus,minus}] = $\alpha_2*(\alpha_1-\beta_1)$f[{minus}] = $\alpha_2^2*(\alpha_1-\beta_1)$

I would like to be able to apply this list to lists of arbitrary length (and also incorporate more rules if necessary.

I am a novice in Mathematica, and have tried using recursive functions as described in the documentation, but I am unfamiliar as to what sort of syntax I would need to use to manipulate the lists in the way I want. I have also considered using For loops to automate this process but I am aware this would make the process very inefficient, and this is also an issue as I would need to run the function many, many times.

• Please, consider updating your question to include what you have tried and where you are getting stuck. That way, people on this site will know exactly what help you need.
– user9660
Nov 16, 2014 at 15:56
• Your example contains a mistake, the final form should be a_2(a_1-b_a*a_2)
– Timo
Nov 16, 2014 at 16:43

One thing to look into to better understand MMA programming is how to define functions with variable arity (number of arguments). The normal way to define a function of x is f[x_]:=.... Functions of two variables are f[x_,y_]:=... etc. However when you don't know the number of arguments beforehand you can use __ (two underscores) and ___ (three underscores) which mean "one or more" and "zero or more" arguments respectively.

Using these I would start by constructing a recursive function like f[i_,j__]:=g[i]f[j] where g[i] now should take care of the rules you mention.

Your particular problem calls for lots of different rules based on possibly more than one condition, so I would construct a Switch statement with an expression that includes the various conditional parameters. E.g., EvenQ@Count[list, pattern] will answer the question of even or odd remaining elements in a list.

Using 1 and -1 as substitutes for "plus" and "minus" The following will do your minimal example and is easily expandable to more rules:

f[-1] = a2;
f[i_, j__] := Switch[
{i, EvenQ@Count[{j}, i]}, (* The list of conditional parameters *)
{ 1, True }, a1 - b1*f[j],
{ 1, False}, a2*f[j],
{-1, True }, a2*f[j],
{-1, False}, a1 - b1*f[j]
];


Which will give

In := f[1, 1, -1]
Out := a2 (a1 - a2 b1)


EDIT: I just noticed you want a function that takes lists as arguments. Here is the above solution but using lists:

g[{-1}] = a2;
g[i_] := Switch[
{First@i, EvenQ@Count[Rest@i, First@i]},
{1, True}, a1 - b1*g[Rest@i],
{1, False}, a2*g[Rest@i],
{-1, True}, a2*g[Rest@i],
{-1, False}, a1 - b1*g[Rest@i]
];


And again

In := g[{1, 1, -1}]
Out := a2 (a1 - a2 b1)


And since MMA is nothing if not versatile, you could also use the original f[] but just use Apply (or it's shorthand @@)

In := f@@{1, 1, -1}
Out := a2 (a1 - a2 b1)

• Btw. you are going to run into $RecursionLimit pretty fast using this method. If you want to raise it consider using a Block[{$RecursionLimit = 10000}, your code here] statement so you don't globally relax the limit.
– Timo
Nov 16, 2014 at 17:37