# Different ways to program a recursive algorithm

Construct f (a numeric function) which takes multiple arguments with the following property:

The single argument case $f(x_1)$ is meaningless, and the two-argument function $f(x_1,x_2)$ is the base case. The multivariable function $f(x_1,x_2,x_3,x_4,\ldots)$ is determined from those with fewer arguments as follows:

$$f(x_1,x_2,\ldots,x_n) = f(x_1 x_2 \ldots x_{n-1}, x_n) + f(x_1,x_2,\ldots,x_n)$$

Here are some examples of the expected output:

f[a, b, c]
(*  f[a, b] + f[a b, c]  *)

f[a, b, c, d, e]
(*  f[a, b] + f[a b, c] + f[a b c, d] + f[a b c d, e]  *)


Here is my (recursive) implementation:

f[args : PatternSequence[_, __], last_] := f[Times[args], last] + f[args]


Are there other ways the implement this in Mathematica? How about using iteration? Can it be done using recursive pure functions?

• If[Length[{##}] > 2, #0[Times @@ Most[{##}], Last[{##}]] + #0 @@ Most[{##}], f[##]] &[a, b, c, d, e]? – J. M. is away Apr 14 '16 at 15:16
• Total[NestList[Most, f[a, b, c, d], 2]] will probably be faster. – C. E. Apr 14 '16 at 15:21
• @C.E. the appropriate arguments are not multiplied altogether in that case, tho. The replacement rule f[args__, last_] :> f[Times[args], last] will of course take care of that. – J. M. is away Apr 14 '16 at 15:29
• @J.M. That's true, I misread. – C. E. Apr 14 '16 at 16:06