Recursion is often applied to tree structures, such as lists. Indeed, a list can be described as a tree, whose components are either leaves , or nodes . A leaf is a termination of a tree, a node is another list that can, also, contain leaves of nodes.
We would like to add 1 to each number in a tree with many sublists : 1 + ( ((1 2 3)(4 5 6)) (4) ((6 7))) ) .
In other words, we want to increment – increase the value of – the terminal items of the list. But we cannot just apply om+1 to the list : om+ cannot reach each atom directly. It must go through each level of the tree.
We will apply the following recursive function to the tree : IncrListElements (LIST) = for each ELEMENT in the LIST, do :
The whole tree is ran through and all terminal items are incremented. Hence, the termination condition of a recursive function, when applied to a tree structure, is to reach a leaf, or extremity of a tree.
This patch illustrates the previous case :
"Input" yields values or lists of values to be processed.
If an element is an atom, "input" is incremented directly.
If an element is not an atom, – that is, a list –, the patch is applied recursively to each element of the list...
Mapcar allows to apply the patch on "lambda" mode successively to each element of a list. An alternative would be using an OMLoop to call the sub patch successively on each element of the list.