Roughly speaking, the number of steps they take can't be larger than the size of the program. To obtain the computing power of ordinary lan- guages, or Turing machines, etc., we need a way to repeat computations. Most languages support loops. Pure functional programs use recursive functions instead of iteration to achieve repetition. Crucial difference is that each recursive activation of a func- tion provides new actual parameters to be bound to the function's formal parameters.
Recursive definition is one that mentions the thing being defined in the body of the definition.
Note direct correspondence to induction. Given a list of integers, return the same list with zeroes inserted between each.