> LeekScript Tutorial
Prerequisites:
----
Generally speaking, recursion is the ability of an object to refer to itself. In the real world, the most obvious examples are fractals, or two mirrors facing each other. You also find it 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...", and so on. In programming, it mostly shows up as functions that call themselves:
function loop() { loop(); }
The function above is the simplest possible recursive function. When called, it does nothing but call itself. It amounts to an infinite loop (e.g. while(true);). We'll use this function as the basic skeleton for all our future recursive functions.
Recursion is analogous to deconstruction. It mainly appears in divide and conquer algorithms. To solve a problem, you first split it into sub-problems that are easier to solve, and repeat the process until you reach a problem you know how to solve directly. From there, you solve the higher-level problems by combining the solutions you already have.
We want to define a function that takes an integer n and returns the sum from 0 to n (i.e. 0 + 1 + ... + n). Starting from our basic skeleton, we can begin with the following function:
function sumN(n) { sumN(?); return ?; }
Here is what we know so far:
n is known;sumN with a new value;sumN must return a number;loop, sumN never stops. We'll need to find a way to stop it.When working recursively, it's always a good idea to start with the stopping condition. With recursion, we want to stop creating sub-problems once we've reached something we can solve. Here, the sum from 0 to 0 is something we know how to solve. So 0 is our base case: we can return the corresponding sum directly.
function sumN(n) { if (n === 0) { return 0; } else { sumN(?); return ?; } }
Now we need to find a way to reach the base case. We could subtract n from itself, but then we couldn't add up the integers between 0 and n: we would only have 0 and n to work with. So we need to create a sub-problem that solves 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 compute the sum, which is what we set out to do. Here, the sum from 0 to n is also the sum from 0 to n - 1, plus 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); }
Feel free to try the code in your Leek Wars editor. You might discover the main problem with recursion. You can also visualize the execution (in a basic way) on this site, or use this library by Hazurl to debug recursive functions.
/!\ This section needs to be redone: what it shows is mostly tail recursion, which doesn't suit multiple branches. /!\ Corecursion is analogous to construction. In recursion, we worked our way down from the main problem to a base case; in corecursion, we start directly from the base case and work our way up to the solution of the main problem.
We've already come across mutual recursion with the mirrors and the sentences. In programming, with functions, it means two or more functions calling each other. Here is the simplest case of mutual recursion:
function mutualLoop() { mutualHelper(); }
function mutualHelper() { mutualLoop(); }
This form of recursion isn't really more complicated than simple recursion, and with functions alone it's rarely more useful; it really shines when the language lets you define recursive data structures. However, we won't cover that topic here (it has been possible since LeekScript 2 thanks to classes) unless readers ask for it.
Here we want to define two functions: isOdd takes a natural number and returns whether it is odd, and isEven takes a natural number and returns whether it is even. We'll also apply the following restrictions:
As usual, we start from the basic skeleton:
The base case, 0 for natural numbers:
function isOdd(n) { if (n === 0) { return false; } else { isEven(?); return ?; } }
function isEven(n) { if (n === 0) { return true; } else { isOdd(?); return ?; } }
We move closer to the base case:
All that's left is to work out how to use the values returned by isEven and isOdd. Suppose n = 1. In isOdd, isEven returns true because 1 - 1 = 0, so we can return that same value; in isEven, isOdd returns false because 1 - 1 = 0, so once again we can simply return that value. This gives us 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, feel free to check them in your editor. Also try rewriting them with ternaries, and why not corecursively: all practice helps you get the hang of it. Be careful not to make things harder than they need to be.
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)
isOdd and isEven can also be written with simple recursion. Keeping the same restrictions, rewrite these two functions using simple recursion only.
Also simply called a stack overflow. Function calls aren't free. The processor needs a workspace to store the function's arguments and local variables. This space is kept until the function has returned a value. When a function calls another function, a new workspace is created for the one being called. But the old one stays, because the first function hasn't been able to return a value yet. When we call the loop function, we create an infinite number of workspaces. And even though loop has no arguments and no local variables, it still has to call itself, which means it needs a little room to make that call. An infinite number of little bits adds up to a lot. So much, in fact, that no computer in the world can stack all the workspaces needed to run loop. To avoid too many stack overflow problems, some languages limit how deep recursive calls can go. LeekScript is one of them. If you've read the tutorial on the official site, you may have noticed that it mentioned a limit of 200 calls. That value is no longer current, but the principle is that on the 201st call to loop, LeekScript would stop your script and report a crash with a stack overflow error. Today, LeekScript, which is compiled rather than interpreted, relies on the maximum size of the call stack. Not all functions need a workspace of the same size: on a given computer, a very light function should be able to repeat more times than a heavy one. A limit based on the size of the program's workspace, rather than on an arbitrary depth that could needlessly restrict some code, seems more useful for the people who use the language.
This concept isn't exclusive to recursion, but it came about because of the stack overflow problem. We've seen that a function's workspace doesn't go away until a value has been returned. Looking at the recursive definition of sumN, it's easy to see why: when we make the inner call to sumN, there's still an addition left to do before we can return a result. If we did the addition before the call, however, there would be no extra work left to do. Some languages (LeekScript is not one of them at the time of writing) perform an optimization called tail call elimination: when the calling function merely returns the result of the function it calls, its workspace is destroyed (or reused) and replaced with the workspace of the called function. Take the loop function. When called, the only thing it does is call itself again. (It doesn't return anything, but it doesn't do any more work afterward either.) This means that if its workspace were eliminated at each inner call, instead of a program that uses an infinitely large workspace, we would have a program whose workspace stays tiny, even though it never stops.
Once again, starting from our function skeleton:
function tailSumN(n) { tailSumN(?); return ?; }
This time, 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 end up with the same result as before.
The simplest change is to return the result directly:
function tailSumN(n) { return tailSumN(?); }
We also need to decide where to put the addition. We can't use the result of tailSumN, so it has to happen before the call: in a variable before the call, or directly in the call's arguments:
function tailSumN(n) { return tailSumN(? + ?); }
We could use n as an operand of our addition, but we also have to think about the stopping condition. Either way, we need two new values: either a base case and one part of the addition, or two parts of the addition. We'll keep n for our stopping condition. This means we'll have a value to compare it with, and that value will have to move toward n. So it will be the part that gets added to the sum (x), and the other value will be the sum so far (acc).
function tailSumN(n, x, acc) { if (? === n) { return ?; } else { return tailSumN(n, ? , x + acc); } }
We can easily deduce that x will be compared to n. Likewise, since x is the part that changes at each step of the addition, and we know that 0 and that x moves toward n, we simply add 1 to get closer to n.
function tailSumN(n, x, acc) { if (x == n) { return ?; } else { return tailSumN(n, x + 1, acc + x); } }
We still have to decide what to return when the stopping condition is met. n is only there to control our sum, so we won't use it. x alone makes no sense, since the sum of the previous steps is stored in acc. That leaves two options: either acc alone, or acc + x. To choose between them, we can compare what each option gives, starting with:
We can quickly see that acc + x gives the expected result.
function tailSumN(n, x, acc) { if (x == n) { return acc + x; } else { return tailSumN(n, x + 1, acc + x); } }
You could return acc alone at the end by stopping the recursion one step later (condition x > n), but the choice made here keeps the two branches of the function more alike. Both perform an addition, but when the stopping condition is met, we don't call tailSumN again.
To use this function, you need to know how tailSumN works: it needs an n, the base case and an accumulator. But all we want is the sum from 0 to n. So we need to define an intermediate function that takes 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); } }
Users can now call sumN without having to think about it. Go ahead and try it in your Leek Wars editor, or watch it run 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 the record, a function like go is called a helper function, or just a helper.
Sometimes you can use the original argument(s) (here n) to reach the stopping condition. So try rewriting tailSumN without the intermediate x. Keep it simple, and draw on what you already know.
Take the functions from the previous exercises and rewrite them using tail recursion.
A list is defined as either an empty list (usually called Nil), or an element followed by the rest of the list (as a pair). In LS1, we'll represent Nil with an empty array: [], and the pair with a two-element array: [a, List a]. So a list containing the elements 1, 2, 3, 4 will be written [1, [2, [3, [4, []]]]]. We'll also define a few functions that make this data type easier to work with:
function nil() { return []; } // () -> List a // Creates an empty list. function cons(x, xs) { return [x, xs]; } // (a, List a) -> List a // Adds an element to a list (that is, creates a longer list). function head(xs) { return xs[0]; } // List a -> a // Gets the head; crashes if the list is empty (actually returns null). function tail(xs) { return xs[1]; } // List a -> List a // Gets the tail; same remark. function empty(xs) { return xs == nil(); } // List a -> Bool
Since the goal of this article is to practice recursion, the code for a fromArray function is given right away:
function fromArray(xs) { return arrayFoldRight(xs, cons, nil()); }
It can be rewritten recursively: feel free to do it, and compare the results of your implementation with the one above.
To work with the elements of a list, we have to break it down so we can handle the head element first, and the rest of the elements later. As a first exercise, you'll implement a recursive function that displays the elements of the list it receives. A first version will display them from the outside in (pre-order): 1, 2, 3, 4 -> 1 2 3 4, then a second version will display them from the inside out (post-order): 1, 2, 3, 4 -> 4 3 2 1. Nil is not displayed. You can work with the arrays directly, but it's better to use the functions defined above for that purpose. You don't need any variables: the var keyword and the assignment operator = shouldn't appear in your code.
Remember: start with the stopping condition. This data type is very simple and has only two possible cases, which makes it very easy to decide when to stop the recursion.
Function skeletons:
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 walk through a list and handle its elements in either order, you'll implement a toArray function that takes a list and returns an array with the elements in the same order, so that [1, 2, 3, 4] == toArray(fromArray([1, 2, 3, 4])). Once again, prefer the list functions to working with the arrays directly (except for 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 work, but the simplest one uses no variables and no assignments.
Now that you can display your lists in a compact, readable way with debug(toArray(xs)), it will be easier to examine what your functions return.
While implementing toArray, you may at some point have ended up with the array backwards. The next exercise does the same thing, but with a list as the result. You'll implement a reverse function that takes a list and returns a new list with the elements in the opposite order. (This function already exists for arrays, but nobody uses it, so feel free to reuse the name.) Again, try to use only the functions provided for lists 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 out of the box 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 ourselves. So that's what you're going to do. At the very least, you should implement equ (==) and lesserThan (), lesserEqu (=).
All this is fun, but you probably want to do more with lists than scratch the surface: computing their length, getting the element at a given index, transforming their contents, and so on. So here is a list (heh) of functions you should implement to better understand this data structure and how to work with it:
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()); }
Lists are nice (not so much in LS1), but because of arrays they're of limited use in Leek Wars. We'll now look at a slightly more complex data structure. If we define a list as List a = Nil | Cons a (List a), a binary tree is defined in almost the same way: Tree a = Nil | Node a (Tree a) (Tree a). It's easy to see that a list is a tree where one of the branches always contains Nil. We can also regard lists and binary trees as special cases of more general data structures, but we'll get to that later.
First, let's define the functions for working with binary trees:
function nil() { return []; } // () -> Tree elem // Creates an empty tree. function node(x, ls, rs) { return [x, ls, rs]; } // (elem, Tree elem, Tree elem) -> Tree elem // Combines two trees and an element into a new tree. function head(xs) { return xs[0]; } // Tree elem -> elem // Gets the head; crashes if the tree is empty (actually returns null). function left(xs) { return xs[1]; } // Tree elem -> Tree elem // Gets the left subtree; same remark as for head function right(xs) { return xs[2]; } // Tree elem -> Tree elem // Gets the right subtree; same remark as for head function empty(xs) { return xs == nil(); } // Tree elem -> Bool
Or elegant brute force.
If you haven't done the fibonacci exercise yet, start there.
Now try values such as 120. LeekScript doesn't automatically switch to big numbers, so don't worry if the results are wrong. However, if you implemented both versions correctly, you'll have noticed that the recursive version couldn't give you a result, while the tail-recursive one keeps going without any trouble, and we don't even have tail call elimination. This is because for every n > 1, fibonacci calls itself twice, which gives a function with a time complexity of O(2^n). (Not exactly, but what matters here is that it's exponential.) In comparison, the tail-recursive version of fibonacci runs in O(n): no work is ever repeated while computing fibonacci(n). However, the recursive definition of fibonacci is much simpler to write and to understand than the tail-recursive one. So we'd like to have the simplicity of one and the performance of the other. To get there, we must make sure we don't recompute anything needlessly: we need to keep the intermediate results. Defining a function that checks whether a result has already been computed and cached and returns it, or else computes it, stores it and returns it, is called memoization. Here is a basic example of a 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 a one-argument function and returns that same function, 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.
Interesting things that you probably won't need.
Impossible de charger les données du jeu.
Vérifiez votre connexion et réessayez.