Multiplication cannot be obtained from zero, successor, and identity by composition without recursion

Question

The task is to show that multiplication cannot be obtained by zero, successor, or identity functions by composition without using recursion at least twice.

I'm primarily confused because it doesn't seem like you can define multiplication just in terms of these functions anyway. We have $mult(x,0) = 0$, but how can $mult(x,succ(y))$ be defined in terms of zero, successor, and identity alone? And why must recursion be used twice? I can see that successor requires some recursion, but "twice" seems like an oddly specific requirement.

Answer 1

Hint: You can use one round of recursion to define add:

add(x,0) = x

add(x, Sy) = S(add(x,y))

Then you can use another round of recursion to define mult:

mult(x,0) = 0

mult(x,Sy) = add(x, mult(x,y))

To show that composition alone does not suffice, you'll want to first show that any function defined from the basic elements in an expression of length k is bounded by id + f(k). Then show that having a single round of recursion does not get you anything grower faster than linear, i.e. is bounded by $f(k) * (x + y)$.