To understand recursion, you must first understand recursion.
Recursion is a technique well suited to certain types of tasks. In this first lesson we’ll look at solving a problem that requires the flattening of arrays without using recursion. Showing the shortcoming of a non-recursive solution first will help you to understand why it’s so valuable and why sometimes it's the only solution to many problem.
In this lesson we manage to remove all of the nested loops that helped us towards a partial solution in the first lesson. We create a function getTasks
, that can, only under certain conditions, call itself. This is the basis of recursion and often leads to cleaner, shorter code that can handle more dynamic input.
Our previous solution used forEach
and a globally available array that could be mutated from inside our function. We can improve upon this and create a function that is easier to maintain & test by swapping our forEach
loop for reduce
. By removing the global array and instead making getTasks
return a value directly we end up with a pure function.
When using recursion, you must be mindful of the dreaded infinite loop
. Using the recursive function that we’ve built up over the previous lessons, we look at how a simple duplicated configuration item could cause chaos for our program as it has no context of which items it has previously seen. We fix this problem by introducing a parents
array, which can keep track of which top-level commands have already been accessed.