Recursivity

Recursivity

> LeekScript Tutorial

Prerequisites:

----

Recursion, generally speaking, is the ability of an object to refer to itself. In the real world, this shows up most obviously through fractals, as well as when you put two mirrors facing each other. We also find this notion in sentences like: "I dream that I dream that I dream." or "I think that I write that I dream that I think that I write...", etc. In programming, it mainly shows up with functions that call themselves:

function loop() { loop(); }

The function above is the simplest recursive function there can be. When called, it does nothing but call itself. This amounts to the same thing as using an infinite loop (e.g. while(true);). We'll use this function as a base skeleton for all our future recursive functions.

Recursion

Recursion is analogous to deconstruction. We mainly find it in ''Divide and Conquer'' type algorithms. To solve our problem, we start by subdividing it into sub-problems that are simpler to solve, we repeat the process until we find a problem we know how to solve directly, and from there, we solve the higher problems by combining our previous solutions.

Defining the Sum from 0 to n

We want to define a function taking an integer n as a parameter and returning the sum from 0 to n (e.g. 0 + 1 + ... + n). Reusing our base skeleton, we can start with the following function:

function sumN(n) { sumN(?); return ?; }

For now, we have the following information:

When we work with recursion, it's always a good idea to start with the stopping condition. In the case of recursion, we want to stop creating sub-problems when we've found something we can solve. In this case, the sum from 0 to 0 is something we know how to solve. 0 is therefore our base case, we can directly return the corresponding sum.

function sumN(n) { if (n === 0) { return 0; } else { sumN(?); return ?; } }

Now we need to find how to reach the base case. We could subtract n from itself, but in that case it would be impossible to sum the integers between 0 and n, we would only have 0 and n available. So we'll need to create a sub-problem that can solve a sum with an n closer to our base case.

function sumN(n) { if (n === 0) { return 0; } else { sumN(n - 1); return ?; } }

All that's left is to actually do the sum, which is what we were asked at the start. Here, the sum from 0 to n is also the sum of the sum from 0 to n - 1 and n.

function sumN(n) { if (n === 0) { return 0; } else { return n + sumN(n - 1); } }

With a ternary:

function sumN(n) { return n === 0 ? 0 : n + sumN(n - 1); }

Don't hesitate to try the code in your Leekwars editor. Maybe you'll discover the main problem of recursion. You can also visualise the execution (in a basic way) on this site or use this library by Hazurl for debugging recursive functions.

Corecursion

/!\ Section to redo, what is shown is mainly tail recursion. Unsuited to several branches. /!\ Corecursion is analogous to construction. Unlike recursion where we sought to reach a base case starting from our main problem, in corecursion, we start directly with our base case, and we move towards the solution of the main problem.

Mutual Recursion

We've already touched on mutual recursion with mirrors and sentences. In programming, with functions, this translates into two or more functions that call each other. We present below the simplest case of mutual recursion:

function mutualLoop() { mutualHelper(); }

function mutualHelper() { mutualLoop(); }

Not really more complicated than simple recursion, but rarely more useful with functions, this form of recursion shows its full interest when the language used offers the possibility of defining recursive data structures. However we won't cover this subject unless Leekscript 2 comes to gain this capability (probably already possible although relatively improper) or unless readers request it.

Defining isOdd and isEven

Here we want to define two functions: isOdd takes a natural integer and returns whether this number is odd or not, isEven takes a natural integer and returns whether this number is even or not. We'll also apply the following restrictions:

As usual, we start by reusing the base skeleton:

The base case, 0 for natural integers:

function isOdd(n) { if (n === 0) { return false; } else { isEven(?); return ?; } }

function isEven(n) { if (n === 0) { return true; } else { isOdd(?); return ?; } }

We get closer to the base case:

All that's left is to determine how to use the return value of isEven and isOdd. Assuming n = 1, in the case of isOdd, isEven will return true because 1 - 1 = 0, so we can return the same value; in the case of isEven, isOdd will return false because 1 - 1 = 0, again, we can afford to return the same value. We thus obtain the following functions:

function isOdd(n) { if (n === 0) { return false; } else { return isEven(n - 1); } }

function isEven(n) { if (n === 0) { return true; } else { return isOdd(n - 1); } }

As always, don't hesitate to check with your editor. Try also rewriting them with ternaries, and why not in a corecursive way, any practice is good to get your hands in. Be careful not to make the task needlessly complicated.

Exercises

Define the factorial function recursively.

factorial 0 = 1 factorial n = n * (n - 1) * ... * 1

Define the fibonacci function recursively.

fibonacci 0 = 1 fibonacci 1 = 1 fibonacci n = fibonacci (n - 1) + fibonacci (n - 2)

It is possible to write isOdd and isEven with simple recursion. Keeping the same restrictions, rewrite these two functions recursively.

Call Stack Overflow

Or otherwise called Stack Overflow. Making function calls isn't free. The processor needs a workspace to store the function's arguments and its local variables. This space is kept as long as the function hasn't returned a value. When a function calls a function, a new workspace is generated for the latter. But the old one remains, because the first function hasn't been able to return a value yet. When we call the function loop, we generate an infinity of workspaces. And even though loop has neither an argument nor a local variable, it still needs to call itself. That means it needs a little bit of room to make that call. And an infinity of little bits is really a lot. So much so that no computer in the world can stack all the workspaces needed to run loop. In order to avoid having ''too many'' call stack overflow problems, some languages impose a limit on the depth of recursive calls possible. This is the case for Leekscript. If you've read the tutorial available on the official site, you may have noticed that a limit of 200 calls was announced. This value is no longer current, but in principle it means that on the 201st call to loop the Leekscript interpreter would stop your script, and announce a crash with a ''stack overflow'' error. At the time of writing this article, the author estimates that the Leekscript interpreter is based on a maximum call stack size. Not all functions need the same workspace size. Having a very light function should be able to repeat more times on a given computer than a heavy function. Having a limit based on the size of the program's workspace rather than on an arbitrary depth that might needlessly restrict some code seems more interesting for the language's user.

Tail Call

This notion isn't exclusive to recursion, but it appeared thanks to the call stack overflow problem. We've seen that a function's workspace didn't disappear as long as no value was returned. If we look at the recursive definition of sumN, it's easy to understand why. When we make an internal call to sumN, we still have an addition left to do before we can return a result. However, if we did the addition before our call, there would be no need to do extra work. Some languages, of which Leekscript is not one at the time of writing this section, perform an optimisation called ''tail call elimination'' which consists of destroying (or reusing) the workspace of the calling function and replacing it with that of the called function when the former merely returns the result of the latter. Let's take the case of the function loop. When called, the only thing it does is call itself. (It doesn't return, but it doesn't do any more work afterwards either.) That means that with the elimination of its workspace at each sub-call, instead of having a program that uses an infinitely large workspace, we would have a program with a workspace that stays minimal, even if it never stops.

Defining the Sum from 0 to n

Again, by reusing our function skeleton:

function tailSumN(n) { tailSumN(?); return ?; }

Unlike previously, we have less useful information than before:

We're in almost exactly the same situation as before, and if we repeat the same process as before, we'll get the same result as before.

The simplest modification to make is to return the result directly:

function tailSumN(n) { return tailSumN(?); }

We also need to decide where to place the addition. We can't use the result of tailSumN, so we have to do it before the call: in a variable before the call, or directly as an argument of the call:

function tailSumN(n) { return tailSumN(? + ?); }

We could use n as an operand for our addition, but we also have to consider the stopping condition. In both cases, we need two new values. Either a base case and a part of the addition, or two parts of the addition. We'll keep n for our stopping condition. That means we'll have a value to compare with, and that this value will have to tend towards n. It will therefore be the part that is added to the sum (x), and the other value is therefore the sum so far (acc).

function tailSumN(n, x, acc) { if (? === n) { return ?; } else { return tailSumN(n, ? , x + acc); } }

Quite easily, we can deduce that x will be compared to n. Likewise, x being the part modified at each step of the addition, and knowing that 0 and that x tends towards n, we simply have to add 1 to get closer to n.

function tailSumN(n, x, acc) { if (x == n) { return ?; } else { return tailSumN(n, x + 1, acc + x); } }

It remains for us to decide what to return when our stopping condition is satisfied. n only serves to control our sum, so we won't use it. x alone makes no sense since the sum of the previous steps is contained in acc. We have two possibilities: either acc alone, or acc + x. To choose between the two, we can compare the results of applying the two possibilities first with:

We can see quite quickly that the expected result is given by acc + x.

function tailSumN(n, x, acc) { if (x == n) { return acc + x; } else { return tailSumN(n, x + 1, acc + x); } }

It is possible to use acc alone as the final return value by using x = 1 for the initial call, but the choice made here makes the two branches of the function more similar. In both cases, we perform an addition, but when the stopping condition is satisfied, we don't call tailSumN again.

Using this function requires the user to know how tailSumN works. It needs an n, the base case, and an accumulator. But we simply want to get the sum from 0 to n. So we need to define an intermediate function that will take care of calling tailSumN with the right arguments.

function sumN(n) { return tailSumN(n, 0, 0); }

function tailSumN(n, x, acc) { if (x === n) { return acc + x; } else { return tailSumN(n, x + 1, acc + x); } }

The user can now call sumN without thinking about it further. Go ahead, don't hesitate to try in your Leekwars editor, or observe on this site. Using a ternary and a closure:

function sumN(n) { var go = function(x, acc) { return x === n ? x + acc : go(x + 1, acc + x); }; return go(0, 0); }

For your information, go is called a helper function (helper function or helper).

It is sometimes possible to use the original argument(s) (here n) to reach the stopping condition. So I invite you to rewrite tailSumN without the intermediate x. Keep it simple, take inspiration from what you already know.

Exercises

Take the functions from the previous exercises and rewrite them with tail recursion.

Recursive Data Structures

List

A list is defined as being either an empty list (generally called Nil), or an element and the rest of the list (in the form of a pair). In LS1, we'll translate Nil as an empty array: [], and the pair as a two-element array: [a, List a]. Thus, a list containing the elements 1, 2, 3, 4 will be translated as [1, [2, [3, [4, []]]]]. We'll also define a few functions useful for manipulating this type of data:

function nil() { return []; } // () -> List a // To instantiate an empty list. function cons(x, xs) { return [x, xs]; } // (a, List a) -> List a // To add an element to a list (i.e. create a longer list). function head(xs) { return xs[0]; } // List a -> List a // To get the head, crashes if the list is empty (returns null in reality). function tail(xs) { return xs[1]; } // List a -> List a // To get the tail, same comment. function empty(xs) { return xs == nil(); } // List a -> Bool

Since the goal of this article is to practise recursion, the code for a fromArray function is given directly:

function fromArray(xs) { return arrayFoldRight(xs, cons, nil()); }

It is possible to recode it recursively, don't hesitate to do so, you can compare the results of your implementation with the one above.

To manipulate the elements of a list, we need to decompose it in order to work on the head element and later the rest of the elements. As a first exercise, you'll have to implement a recursive function that displays the elements of the list given as a parameter. A first version will display them from outside to inside (pre order): 1, 2, 3, 4 -> 1 2 3 4, then a second version that handles it from inside to outside (post order): 1, 2, 3, 4 -> 4 3 2 1. Nil won't be displayed. You can manipulate the arrays directly, but it's preferable to use the functions provided for this purpose defined above. Variables are useless, the keyword var and the assignment operator = shouldn't appear in your code.

Remember, start with the stopping condition first. This type of data is very simple, it has only two possible cases, which makes it very easy to decide when to stop the recursion.

Skeleton function:

function printInOrder(xs) { /* code */ } // List a -> ()

printInOrder(fromArray([1, 2, 3, 4])); > [LeekySquash] 1 > [LeekySquash] 2 > [LeekySquash] 3 > [LeekySquash] 4

function printPostOrder(xs) { /* code */ } // List a -> ()

printPostOrder(fromArray([1, 2, 3, 4])); > [LeekySquash] 4 > [LeekySquash] 3 > [LeekySquash] 2 > [LeekySquash] 1

Now that you know how to go through a list and manipulate the elements in one order or the other. You'll implement a toArray function that takes a list as a parameter, and returns an array with the elements in the same order. Thus: [1, 2, 3, 4] == toArray(fromArray([1, 2, 3, 4])). Once again, prefer using the list manipulation functions rather than manipulating the arrays directly (apart from the resulting array, of course).

function toArray(xs) { /* code */ } // List a -> Array a

debug([1, 2, 3, 4] == toArray(fromArray([1, 2, 3, 4]))); > [LeekySquash] true

Several implementations are valid, but the simplest is done without a variable or assignment.

Now that you have a way to display your lists in a compact and readable way with debug(toArray(xs)), you'll be able to examine the results of your functions more easily.

During the implementation of toArray, it's possible that at some point you had the requested array reversed. The following exercise will do the same thing, but with a list as a result. You'll implement a reverse function that takes a list as a parameter and returns a new list with the elements ordered the other way. (This function already exists for arrays, but nobody uses it, so don't hesitate to reuse the name.) Again, make an effort to use only the functions provided rather than touching the arrays.

function reverse(xs) { /* code */ } // List a -> List a

debug([4, 3, 2, 1] == toArray(reverse(fromArray([1, 2, 3, 4])))); debug(fromArray([1, 2, 3, 4]) == reverse(reverse(fromArray([1, 2, 3, 4])))); > [LeekySquash] true > [LeekySquash] true

The equality operator == works implicitly for our lists because they're made of arrays, but if we had really created a new data type, we would have had to implement this operator. So that's what you're going to do. At a minimum, you should implement equ (==) and lesserThan (), lesserEqu (=).

Well, all this is fun, but you probably want to use lists a bit more than on the surface. For example, computing the size, getting an element at a given index, transforming the content, etc. So here is a list (hehe) of functions you should implement in order to better understand this data structure and how to manipulate it:

Solutions

printInOrder

function printInOrder(xs) { if (empty(xs)) {} else { debug(head(xs)); printInOrder(tail(xs)); } }

printPostOrder

function printPostOrder(xs) { if (empty(xs)) {} else { printPostOrder(tail(xs)); debug(head(xs)); } }

toArray

function toArray(xs) { if (empty(xs)) { return []; } else { return [head(xs)] + toArray(tail(xs)); } }

reverse

function reverse(xs) { var go = function(ys, acc) { return empty(ys) ? acc : go(tail(ys), cons(head(ys), acc)); }; return go(xs, nil()); }

Binary Tree

Lists are nice, (not too much in LS1), but they have limited interest in the context of Leek Wars due to arrays. We'll now discover a slightly more complex data structure. If we define a list in the following way, List a = Nil | Cons a (List a), a binary tree will be defined almost the same way: Tree a = Nil | Node a (Tree a) (Tree a). We can easily see that a list is a tree in which one of the branches always contains Nil. We can also consider that lists and binary trees are special cases of more general data structures, but we'll see that later.

We'll first define the functions for manipulating binary trees:

function nil() { return []; } // () -> Tree elem // Instantiates an empty tree. function node(x, ls, rs) { return [x, ls, rs]; } // (elem, Tree elem, Tree elem) -> Tree elem // Assembles two trees and an element into a new tree. function head(xs) { return xs[0]; } // Tree elem -> elem // To get the head, crashes if the tree is empty (returns null in reality). function left(xs) { return xs[1]; } // Tree elem -> Tree elem // Gets the left tree, same comment as for head function right(xs) { return xs[2]; } // Tree elem -> Tree elem // Gets the right tree, same comment as for head function empty(xs) { return xs == nil(); } // Tree elem -> Bool

Forest

Relationship Between Recursive and Iterative

Continuation Passing Style

Dynamic Programming

Or elegant brute force.

If you haven't done the exercise with fibonacci yet, start there.

Now try values such as 120. Leekscript doesn't automatically convert numbers to Bignum so don't worry if the results are wrong. On the other hand, if you've correctly implemented both versions, you'll have noticed that the recursive version didn't manage to return a result to you, while the tail-recursive one has no problem continuing, and we don't even have tail call elimination. This comes from the fact that for each n > 1, fibonacci is called twice, which brings us to a function whose algorithmic time complexity is O(2^n). (Not exactly, but what interests us here is the exponential aspect.) In comparison, the tail-recursive version of fibonacci runs in O(n). We don't repeat any work throughout the resolution of fibonacci(n). However, the recursive definition of fibonacci is much simpler to implement and understand than the tail-recursive definition. So we would like to be able to enjoy the ease of one and the performance of the other. For that, we therefore need to make sure not to recompute needlessly. We need to keep the intermediate results. The method that consists of defining a function that checks whether a result has already been computed and cached then returns the result, or computes it, stores it, and returns it, is called ''memoization''. Below is a basic example of memoized fibonacci:

global fibmem = [];

function fibonacci(n) { var ret = fibmem[n]; if (ret !== null) { return ret; } else { if (n memoize is a function that takes as a parameter a function expecting one argument and returns that same function but memoized, we can define fibonacci like this:

global fibonacci = memoize(function(n) { return n fibonacci with a time complexity of O(n), but with a space complexity of O(n) compared to the O(1) of the tail-recursive definition.

Side Notes

Interesting things but that probably won't be useful to you.

See also