Recursive Functions
Explore how recursive functions form the backbone of functional programming by replacing loops with expression-based recursion in OCaml and Haskell. Understand the difference between non-tail and tail-recursive functions, learn about stack overflow issues, and discover tail-recursion optimization that enables safe, efficient loops without stack growth.
We'll cover the following...
Where are the for/while loops?
Assume you want to calculate the sum, 1 + 2 + 3 + ... + n, for a given n natural number.
In a non-functional programming language, we typically use a for or while loop:
int sum (int n) {
int s = 0;
for (int i = 1; i <= n; i++) {
s = s + i;
}
return s;
}
This way of programming is inherently imperative because we explicitly specify the steps required to update s via variable assignment within a loop.
In the functional paradigm, however, we express sum as an expression. In particular, we can have a mathematical definition of sum as follows:
...