domain and codomain
A function's inputs are known as its domain and the function's return type is known as its codomain. These types can effectively guide us when writing our implementation -
range : (number, number) -> number array
fill in the blanks
This helpful template can get you started on almost any recursive function. It may seem challenging at first, but things become easier as we fill in the pieces. According to the types for range, we already know 2 and 3 must return some array -
// range : (number, number) -> number array
function range(start, end) {
if (...) // 1
return ... // 2 (must return array)
else
return ... // 3 (must return array)
}
1. base case
Each recursive function needs a base case, which does not result in a recursive call, allowing the function to eventually exit. Under what conditions does the range function exit?
// range : (number, number) -> number array
function range(start, end) {
if (end < start) // 1 ✅ when end subceeds start, exit
return ... // 2
else
return ... // 3
}
2. base value
When the exit condition is met, we need to return the base value. Typically it is the empty value of our function's return type, or codomain. Since we must return an array, what is the empty value for arrays?
// range : (number, number) -> number array
function range(start, end) {
if (end < start) // 1 ✅
return [] // 2 ✅ an empty array is []
else
return ...
}
3. inductive case(s)
We must specify what happens when the exit condition is not met in the else branch, known as the inductive cases. If end < start is not true, by induction we know that end >= start. In this case we solve the problem for the current start and end, and append it to the result of the smaller sub-problem. In other words, if I have range(P,Q) the answer is -
append Q to the result of range(P, Q - 1)
Remember the type for range gives us a hint. When range is called with new arguments, the first and second arguments are both number. The return value will be an array of numbers, or number array.
In JavaScript we write that as -
// range : (number, number) -> number array
function range(start, end) {
if (end < start) // 1 ✅
return [] // 2 ✅
else
return [...range(start, end - 1), end] // 3 ✅ minus and append
}
substitution model
Recursion is a functional heritage and so using it with functional style yields the best results. This means writing functions with referential transparency, meaning there are no observable side-effects and the function will always return the same value when the same inputs are used. Using the substitution model we can substitute any function call for its return value -
range(3,6)
[...range(3, 6 - 1), 6]
[...range(3, 5), 6]
[...[...range(3, 5 - 1), 5], 6]
[...[...range(3, 4), 5], 6]
[...[...[...range(3, 4 - 1), 4], 5], 6]
[...[...[...range(3, 3), 4], 5], 6]
[...[...[...[...range(3, 3 - 1), 3], 4], 5], 6]
[...[...[...[...range(3, 2), 3], 4], 5], 6]
[...[...[...[...[], 3], 4], 5], 6] // base case
[...[...[...[3], 4], 5], 6]
[...[...[3, 4], 5], 6]
[...[3, 4, 5], 6]
[3, 4, 5, 6]
using plus instead of minus
It should be helpful for us to see that we can solve range using + and prepend instead of - and append -
// range : (number, number) -> number array
function range(start, end) {
if (start > end) // ✅ when start exceeds end, exit
return []
else
return [start, ...range(start + 1, end)] // ✅ plus and prepend
}
range(3,6)
[3, ...range(3 + 1, 6)]
[3, ...range(4, 6)]
[3, ...[4, ...range(4 + 1, 6)]]
[3, ...[4, ...range(5, 6)]]
[3, ...[4, ...[5, ...range(5 + 1, 6)]]]
[3, ...[4, ...[5, ...range(6, 6)]]]
[3, ...[4, ...[5, ...[6, ...range(6 + 1, 6)]]]]
[3, ...[4, ...[5, ...[6, ...range(7, 6)]]]]
[3, ...[4, ...[5, ...[6, ...[]]]]] // base case
[3, ...[4, ...[5, ...[6]]]]
[3, ...[4, ...[5, 6]]]
[3, ...[4, 5, 6]]
[3, 4, 5, 6]
demo
function rangeplus(start, end) {
if (start > end)
return []
else
return [start, ...rangeplus(start + 1, end)]
}
function rangeminus(start, end) {
if (end < start)
return []
else
return [...rangeminus(start, end - 1), end]
}
console.log(rangeplus(3,6))
// [3, 4, 5, 6]
console.log(rangeminus(3,6))
// [3, 4, 5, 6]
