Recursion
Intro
Recursion is a different way of thinking about writing solutions.
It is a function/procedure/method/process that calls it self with new input until the base case is reached and a final result is produced.
It is a form of looping except without using things like for, while, etc.
Some algorithms are much simpler if implemented using recursion. Some are impossible without recursion. For example, to parse or stringify JSON, recursion is much more appropriate than other sorts of loops. Traversing the DOM or any sort of object traversal, trees, graphs are generally easier using recursion too.
Algorithms making use of recursion must make sure to:
-
handle the base case
-
Pass different input in each invocation so that it will eventually reach the base case
Recursion also involves the call stack, and some languages offer techniques like Tail Call Optimization (TCO) or Tail Call Elimination (TCE) to improve performance and make recursion on larger data sets possible at all.
ECMAScript does not feature TCO or TCE, so recursion must be used responsibly in this language.
Recursion can also be done using pure recursion or helper function recursion.
|
Sometimes people seem to think that things that mention “script” imply a notion of inferiority. For example, “Shell scripting is not really programming, it is merely creating scripts.” Or, “JavaScript is a scripting language” (therefore, inferior to a real language). Sure, some languages do have pros and cons, good and bad design choices, and are better or worse suited to solve a given problem. It doesn’t mean, however, that whatever contains “script” in the name or description is inherently inferior. It is a tool to be used for whatever and whenever it makes sense. The same with recursion, pure recursion and helper function recursion. Recursion is not inherently better than vanilla, plain good old loops. It is a suitable approach for many problems. But it is not always the best approach for every problem. Also, pure recursion does not mean better. Sometimes it will be elegant, easy to read and solve the problem, and sometimes helper function recursion will be the better approach. Don’t let names and descriptions trap you into the wrong way of looking at things. Learn the techniques and approaches, and use then judiciously. |
Pure Recursion
Pure recursion involves a single standalone function that calls itself:
function f(n) {
if (n <= 0) return n;
return n + f(n - 1);
}Helper Function Recursion
Helper function recursion is when there is a public, outer function that client code can call, which itself is not recursive, but which contains an inner function (the helper function) that does the recursion. This is used to make the main function easier to use (less parameters to worry about, etc.). The overall idea goes like this:
function fn(n) {
var total = 0; (1)
function helper(x) {
if (x <= 0) return 0; (3)
total += x; (4)
helper(x - 1); (5)
}
helper(n); (2)
return total; (6)
}
log(fn(5));
// → 15| 1 | Defines storage which is captured in a closure. |
| 2 | Invokes the helper function passing n along, which is a parameter from the main function. |
| 3 | Handle the base case of course. |
| 4 | Actually modifies the outer input which is captured through the closure. |
| 5 | Calls the itself (the helper function) recursively with a modified input (some kind of modification which will eventually cause the base case to be reached). |
| 6 | The recursive helper function must have finished for the flow to reach this point and the final result is returned. |
|
This approach works in ECMAScript and other langues that feature closures. |
A more concrete example, just that in this case it is not use a closure-scoped storage variable. The storage is turned into an accumulator parameter as the last parameter of the helper recursive function.
function filter(xs, predicate) { (1)
return (function helper(list, f, acc) { (2)
if (list.length === 0) return acc; (3)
var [head, ...rest] = list;
if (f(head)) (4)
return helper(rest, f, [...acc, head]);
return helper(rest, f, acc); (5)
})(xs, predicate, []);
}
function isEven(n) {
return n % 2 === 0;
}
log(filter([0, 1, 2, 3, 4, 5], isEven));
// → [1, 2, 4]| 1 | The outer function takes two parameters: a list of something and a predicate function that can be applied to each element of that list. |
| 2 | A immediately invoked named function expression.
Note the parentheses between return and function and how it the function expression is invoked with (xs, predicate, [])! |
| 3 | Handles the base case. |
| 4 | If the current element satisfies the predicate, add it to the new list and recurse with the rest of the list and that element added to the filtered list in the accumulator. |
| 5 | The predicate was not satisfied in the previous step, so recurse with the rest of the list and the unmodified accumulator. |
The Call Stack
Almost all programming languages feature the so called call stack, which is an internal data structure to that programming language that stores information about the calling of functions.
When a function is called, it is added to the stack, and when it returns, it is popped from the stack.
If the call stack keeps being added functions, at some point a limit will be reached a stack overflow error/exception will happen.
Tips on Recursion
When writing recursive algorithms, keep these things in mind:
-
Remember the base case.
-
Careful not to overflow the calls stack.
-
Forgetting to return.
-
Return the wrong thing.
-
Trust the recursion.
Resources on Recursion
The most amazing book to learn about recursion is The Little Schemer, of course. The book is theory and practice from beginning to end.
The other amazing book is How to Design Programs. This is the book that mostly changed (for the better) the way I think about designing code and programs in general. It does an amazing job in every regard: TDD, tests as a design tool and documentation, best (not merely good 😅) practices, and recursion.
Vocabulary
There is the word recursion, of course, but sometimes other related, derived words are needed to better describe an idea.
Recur
The book The Little Schemer uses “recur”, in sentences like this:
Recur on the subparts that are of the same nature.
and
Recur with the function f.
and
It recurs o two tups.
The book HtDP has some examples of “recur” too, as in the title of a section:
Auxiliary functions that recur
and
For a structurally recursive function, the accumulator’s value is typically used in the base case, that is, the
condclause that does not recur.
countdown()
A function that logs integers from n down to 0.
TIME COMPLEXITY: \(O(n)\) since all integers from n to 0 have to be worked upon.
The number of recursive invocations is directly proportional to n.
SPACE COMPLEXITY: \(O(1)\) as no extra storage is used. The call stack is not part of T.C big O concern.
/**
* Logs number from `num` to 0.
*
* ASSUME: `num >= 0`.
*
* - T.C: `O(n)`.
* - S.C: `O(1)`.
*
* @sig Number -> Void
*/
function countdown(num) {
if (num <= 0) {
console.log(n);
console.info("All done!");
return;
}
console.log(num);
countdown(--num);
}sumRange(n)
TIME COMPLEXITY: \(O(n)\).
It recurses as many times as is the value of n.
SPACE COMPLEXITY: \(O(1)\). Only one numeric variable is used. The call stack is not considered as part of space complexity.
Unit Tests
Unresolved include directive in modules/ROOT/pages/recursion.adoc - include::example$src/07-recursion/sumFrom1To.test.ts[]v1 using recursion
TIME COMPLEXITY: \(O(n)\).
There are as many recursive calls as the size of n.
SPACE COMPLEXITY: \(O(1)\). No extra space is required.
Unresolved include directive in modules/ROOT/pages/recursion.adoc - include::example$src/07-recursion/sumFrom1To-v1.ts[]| 1 | The base case. |
| 2 | The recursive invocations with modified input. |
It works like this:
Let f be sumRange (for shortness).
f(5)
5 + f(4) → on the call stack
4 + f(3) → ...
3 + f(2) → ...
2 + f(1) → ...
1 → no more recursive calls, start unwinding
2 + 1 → pop f(2) from the call stack
3 + 3 → pop f(3) + result of previous call
4 + 6 → pop f(4) + result of previous call
5 + 10 → pop f(5) + result of previous callFactorial
Unit Tests
Unresolved include directive in modules/ROOT/pages/recursion.adoc - include::example$src/07-recursion/factorial.test.ts[]v1 using recursion
TIME COMPLEXITY: \(`O(n)`\) because the recursion occurs for as many times as the size of n.
SPACE COMPLEXITY: \(O(1)\) as only a numeric value is computed by the algorithm.
|
The base case for factorial is 1 (not zero) because it is the identity property of multiplication. |
Unresolved include directive in modules/ROOT/pages/recursion.adoc - include::example$src/07-recursion/factorial-v1.ts[]Let f be factorial (for shortness).
f(5)
5 * f(4)
4 * f(3)
3 * f(2)
2 * f(1)
1
2 * 1
3 * 3
4 * 6
5 * 24filterOdds()
Problem: write a recursive function that filters odd numbers from a list.
Unit Tests
Unresolved include directive in modules/ROOT/pages/recursion.adoc - include::example$src/07-recursion/filterOdds.test.ts[]v1 helper function
TIME COMPLEXITY: \(O(n)\). Iterate over every element of the input.
SPACE COMPLEXITY: \(O(n)\). The collected odds potentially increases in direct proportion to the input size.
Unresolved include directive in modules/ROOT/pages/recursion.adoc - include::example$src/07-recursion/filterOdds-v1.ts[]v2 helper function
This solution is based on things I learned studying the awesome HtDP book and Lisp/Scheme, purely recursive using an accumulator.
TIME COMPLEXITY: \(O(n)\). Iterate over every element of the input.
SPACE COMPLEXITY: \(O(n)\). The collected odds potentially increases in direct proportion to the input size.
Unresolved include directive in modules/ROOT/pages/recursion.adoc - include::example$src/07-recursion/filterOdds-v2.ts[]v3 concat approach
Solution from Colt Steele. No helper function or extra accumulator parameter is needed.
TIME COMPLEXITY: \(O(n)\). Iterates over every element of the input.
SPACE COMPLEXITY: \(O(n)\). The collected odds potentially increases in direct proportion to the input size.
Unresolved include directive in modules/ROOT/pages/recursion.adoc - include::example$src/07-recursion/filterOdds-v3.ts[]power()
A function that raises a given integer base to a given integer power. Assume that \(e >= 0\).
Unit Tests
Unresolved include directive in modules/ROOT/pages/recursion.adoc - include::example$src/08-recursion-challenges/power.test.ts[]v1 if base case
TIME COMPLEXITY: \(O(n)\).
There are as many recursive invocations as the size of e.
SPACE COMPLEXITY: \(O(1)\). No extra storage is necessary to store results of the computation.
Unresolved include directive in modules/ROOT/pages/recursion.adoc - include::example$src/08-recursion-challenges/power-v1.ts[]v2 ternary
TIME COMPLEXITY: \(O(n)\).
There are as many recursive invocations as the size of e.
SPACE COMPLEXITY: \(O(1)\). No extra storage is necessary to store results of the computation.
Unresolved include directive in modules/ROOT/pages/recursion.adoc - include::example$src/08-recursion-challenges/power-v1.ts[]product()
A function that computes the product of an array of numbers.
sumRange()
A function that sums all integers from 0 to n, inclusive.
Assume \(n > 0\).
Unit Tests
Unresolved include directive in modules/ROOT/pages/recursion.adoc - include::example$src/08-recursion-challenges/sumRange.test.ts[]v1 helper accumulator
This solution uses an accumulator parameter to store the value computed in each invocation.
TIME COMPLEXITY: \(O(n)\).
SPACE COMPLEXITY: \(O(1)\).
Unresolved include directive in modules/ROOT/pages/recursion.adoc - include::example$src/08-recursion-challenges/sumRange-v1.ts[]v2 no accumulator
This solution neither uses an accumulator parameter, nor does it use a helper function. It just uses elegant (yet very simple) logic to do the job.
TIME COMPLEXITY: \(O(n)\).
SPACE COMPLEXITY: \(O(1)\).
Unresolved include directive in modules/ROOT/pages/recursion.adoc - include::example$src/08-recursion-challenges/sumRange-v2.ts[]v3 helper function
TIME COMPLEXITY: \(O(n)\).
SPACE COMPLEXITY: \(O(1)\).
Unresolved include directive in modules/ROOT/pages/recursion.adoc - include::example$src/08-recursion-challenges/sumRange-v3.ts[]v4 no recursion
This example is just to show that some algorithms can be performed in a purely mathematical way, which sometimes greatly improves performance.
In this case, even time is \(O(1)\) (linear) no matter how large x is.
TIME COMPLEXITY: \(O(1)\).
SPACE COMPLEXITY: \(O(1)\).
Unresolved include directive in modules/ROOT/pages/recursion.adoc - include::example$src/08-recursion-challenges/sumRange-v4.ts[]fibonacci()
A recursive function called fib which accepts a number and returns the nth number in the Fibonacci sequence.
Check this article on the Fibonacci Sequence in the MathIsFun website.
Unit Tests
Unresolved include directive in modules/ROOT/pages/recursion.adoc - include::example$src/08-recursion-challenges/fib.test.ts[]strRev()
A function that reverses the characters of a string.
Unit Tests
Unresolved include directive in modules/ROOT/pages/recursion.adoc - include::example$src/09-harder-recursion-challenges/revStr.test.ts[]isPalind()
A function that checks whether a string is a palindrome.
Unresolved include directive in modules/ROOT/pages/recursion.adoc - include::example$src/09-harder-recursion-challenges/isPalind.test.ts[]v1
This is a very standard way to implement the algorithm. Basically, keep recursing while the two ends of the string are the same. If they are, recur with the string stripped of its first and last element.
Unresolved include directive in modules/ROOT/pages/recursion.adoc - include::example$src/09-harder-recursion-challenges/isPalind-v1.ts[]some()
A function that takes an array and a predicate function and returns true if any element in the array satisfies the predicate.
Unit Tests
Unresolved include directive in modules/ROOT/pages/recursion.adoc - include::example$src/09-harder-recursion-challenges/some.test.ts[]v1 simple, pure recursion
TIME COMPLEXITY: \(O(n)\). Potentially recurse for as many times as the length of the input array.
SPACE COMPLEXITY: \(O(1)\). No extra storage is necessary to compute the boolean result.
Unresolved include directive in modules/ROOT/pages/recursion.adoc - include::example$src/09-harder-recursion-challenges/some-v1.ts[]This algorithm recurs until it finds an element (if any) that satisfies the predicate. It does not necessarily recur through the entire array. Still, time complexity is \(O(n)\) because it can potentially recur through the extent of the entire input.
flatten()
A function that takes an array of arrays and return an array with all values flattened.
flatten([1, 2, [3, 4], 5, [6, [7, 8, [9, [10, 11], 12]]]]);
// → [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]Unit Tests
Unresolved include directive in modules/ROOT/pages/recursion.adoc - include::example$src/09-harder-recursion-challenges/flatten.test.ts[]v1 helper function
Unresolved include directive in modules/ROOT/pages/recursion.adoc - include::example$src/09-harder-recursion-challenges/flatten-v1.ts[]The idea behind this algorithm is that a value is only ever placed into the accumulator if it is a non-array value.
| 1 | If the value is an array, then recur with its head and the recursion of its tail.
Note go() is invoked twice in this line! |
| 2 | When an element is a non-array element, then place it at the beginning of the accumulator. |
v2 for + recursion
Unresolved include directive in modules/ROOT/pages/recursion.adoc - include::example$src/09-harder-recursion-challenges/flatten-v2.ts[]This version also ever only adds an element to the accumulator if it is a non-array element.
| 1 | If the current element is itself an array, concatenate what is already flattened with the result of recursively flattening the element (since the element is an array, and we only every add an element to the accumulator if it is a non-array element). |
| 2 | The current element is not an array, so, append it to the accumulator. |
v3 reduce
Unresolved include directive in modules/ROOT/pages/recursion.adoc - include::example$src/09-harder-recursion-challenges/flatten-v3.ts[]This solution uses reduce(), which means it automatically stops after it runs out of elements in the input array, which also means its base case doesn’t need to check whether the element is an array AND empty (like it is the case on the version with pure recursion
without any other sort of loops).
It only checks if the current element is an array and recurs accordingly.
capitalizeAll()
A function that capitalizes the first letter of the given array of strings.
Unit Tests
Unresolved include directive in modules/ROOT/pages/recursion.adoc - include::example$src/09-harder-recursion-challenges/capitalizeAll.test.ts[]v1 helper function
Unresolved include directive in modules/ROOT/pages/recursion.adoc - include::example$src/09-harder-recursion-challenges/capitalizeAll-v1.ts[]nestedEvenSum()
Walks a potentially nested object and sums all values.
{
a: 1,
b: 2,
c: {
d: 3,
e: {
f: 4,
},
g: 5,
},
h: 6,
}
1 + 2 + 3 + 4 + 5 + 6 → 21nestedEvenSum()
Walks a potentially nested object and sums the values of keys which are even numbers.
{
a: 1,
b: 2,
c: {
d: 3,
e: {
f: 4,
},
g: 5,
},
h: 6,
}
2 + 4 + 6 → 10Unit Tests
Unresolved include directive in modules/ROOT/pages/recursion.adoc - include::example$src/09-harder-recursion-challenges/nestedEvenSum.test.ts[]walkNumToStr()
A funtion that walks an object and turns its number leaves to strings.
{
a: 1,
b: [],
c: {
d: 2,
e: "The Force!",
f: {
g: "h",
i: 3,
},
j: 4,
}{
a: "1",
b: [],
c: {
d: "2",
e: "The Force!",
f: {
g: "h",
i: "3",
},
j: "4",
}