Recursion
The functions and datatypes we have written so far are limited in power:
- We lack a mechanism to repeat a number of computation steps. If we want some computation to be repeated five times, we explicitly have to write five function calls. If we want six instead, we have to modify the program and add a sixth call.
- Similarly, we lack a mechanism to arbitrarily extend the size of a data structure. If we want a data structure that holds five values, we have to write an algebraic datatype (ADT) definition with a constructor that has five fields. If five is not enough, and we want six instead, we need to modify existing definitions.
These extensions of existing definitions quickly become unwieldy for larger sizes, and we cannot dynamically determine the number at runtime (at least not beyond the cases we have explicitly foreseen while writing the program).
Imperative programs solve this problem in two different ways for repeated computations and data structure...
