> LeekScript 教程
前置知识：
----
一般来说，递归是指一个对象引用自身的能力。在现实世界中，最明显的例子就是分形，还有把两面镜子面对面摆放的时候。这个概念也出现在这样的句子里：“我梦见我梦见我在做梦。”，或者 “我想我正在写我梦见我想我正在写……” 等等。在编程中，它主要表现为调用自身的函数：
function loop() { loop(); }
上面这个函数是最简单的递归函数了。调用它时，它什么也不做，只是调用自己。这和使用无限循环（例如 while(true);）是一回事。接下来所有的递归函数，我们都会以这个函数为基本骨架。
递归类似于拆解。它主要出现在''分治''（分而治之）类算法中。为了解决问题，我们先把它拆分成更容易解决的子问题，重复这个过程，直到遇到一个可以直接解决的问题；然后再组合之前的解，逐层解决上一级的问题。
我们想定义一个函数：参数是整数 n，返回 0 到 n 的和（即 0 + 1 + ... + n）。 沿用我们的基本骨架，可以先从下面这个函数开始：
function sumN(n) { sumN(?); return ?; }
目前我们掌握的信息如下：
n 是已知的；sumN；sumN 必须返回一个数字；loop 一样，sumN 不会停下来。我们得想办法让它停止。写递归时，先从终止条件入手总是个好主意。 对于递归，我们希望在遇到可以直接解决的问题时，就不再继续创建子问题。在这个例子里，0 到 0 的和是我们知道怎么求的。所以 0 就是我们的基本情况（base case），可以直接返回对应的和。
function sumN(n) { if (n === 0) { return 0; } else { sumN(?); return ?; } }
现在需要想办法到达基本情况。我们可以让 n 减去它自己，但这样就没法求 0 到 n 之间所有整数的和了，手上只剩下 0 和 n。 所以我们要创建一个子问题，让它求一个 n 更接近基本情况的和。
function sumN(n) { if (n === 0) { return 0; } else { sumN(n - 1); return ?; } }
剩下的就只是真正把和算出来了，这也是一开始的要求。在这里，0 到 n 的和，也就是 0 到 n - 1 的和再加上 n。
function sumN(n) { if (n === 0) { return 0; } else { return n + sumN(n - 1); } }
用三元运算符来写：
function sumN(n) { return n === 0 ? 0 : n + sumN(n - 1); }
不妨在你的 Leek Wars 编辑器里试试这段代码。也许你会发现递归的主要问题。 你也可以在这个网站上（以基础的方式）可视化执行过程，或者用 Hazurl 写的这个库来调试递归函数。
/!\ 本节有待重写，下面展示的主要是尾递归，不适用于有多个分支的情况。/!\ 共递归类似于构建。递归是从主问题出发，设法到达基本情况；共递归则相反，我们直接从基本情况出发，一步步推进到主问题的解。
我们在讲镜子和句子的时候，其实已经接触过相互递归了。在编程中，放到函数上，就是两个或更多函数互相调用。下面是最简单的相互递归：
function mutualLoop() { mutualHelper(); }
function mutualHelper() { mutualLoop(); }
它并不比简单递归复杂多少，但用在函数上也很少更有用；当所用语言可以定义递归数据结构时，这种递归形式才能真正显示出它的价值。不过，除非 LeekScript 2 具备了这种能力（大概已经可以做到，虽然不太规范），或者读者提出要求，否则我们不会展开这个话题。
这里我们要定义两个函数：isOdd 接收一个自然数，返回这个数是否为奇数；isEven 接收一个自然数，返回这个数是否为偶数。我们还要加上以下限制：
和往常一样，我们先套用基本骨架：
基本情况，对自然数来说就是 0：
function isOdd(n) { if (n === 0) { return false; } else { isEven(?); return ?; } }
function isEven(n) { if (n === 0) { return true; } else { isOdd(?); return ?; } }
向基本情况靠近：
剩下的就是确定如何使用 isEven 和 isOdd 的返回值。假设 n = 1：对于 isOdd，isEven 会返回 true，因为 1 - 1 = 0，所以我们可以直接返回这个值；对于 isEven，isOdd 会返回 false，因为 1 - 1 = 0，同样可以直接返回这个值。于是得到下面两个函数：
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); } }
和往常一样，不妨在编辑器里验证一下。也试着用三元运算符改写它们，甚至用共递归的方式来写，多练习总是好的。注意别把事情弄得无谓地复杂。
速速搞定。
用递归方式定义 factorielle（阶乘）函数。
factorial 0 = 1 factorial n = n * (n - 1) * ... * 1
用递归方式定义 fibonacci 函数。
fibonacci 0 = 1 fibonacci 1 = 1 fibonacci n = fibonacci (n - 1) + fibonacci (n - 2)
isOdd 和 isEven 也可以只用简单递归来写。在保持同样限制的前提下，用递归方式重写这两个函数。
也叫 Stack Overflow（栈溢出）。 函数调用并不是免费的。处理器需要一块工作空间来存放函数的参数和局部变量。只要函数还没有返回值，这块空间就会一直保留。当一个函数调用另一个函数时，会为后者生成一块新的工作空间，但旧的那块仍然保留，因为第一个函数还没能返回值。调用 loop 函数时，我们会生成无穷多块工作空间。即使 loop 既没有参数也没有局部变量，它仍然需要调用自己，也就是说它需要一点空间来完成这次调用。而无穷多个“一点点”，加起来就真的是非常多了。多到世界上没有任何一台计算机能把执行 loop 所需的全部工作空间都压入栈中。为了避免调用栈溢出带来''太多''问题，有些语言会限制递归调用的最大深度，LeekScript 就是如此。如果你读过官网上的教程，可能注意到其中提到过 200 次调用的上限。这个数值已经过时了，但原理上，这意味着在第 201 次调用 loop 时，LeekScript 解释器会中止你的脚本，并报告崩溃，错误为''stack overflow''（栈溢出）。在撰写本文时，作者估计 LeekScript 解释器依据的是调用栈的最大大小。并不是所有函数都需要同样大小的工作空间。在同一台计算机上，一个非常轻量的函数应该能比一个重量级函数重复更多次。对语言的使用者来说，按程序工作空间的大小来设限，似乎比按一个任意的深度来设限更好，后者可能会无谓地限制某些代码。
这个概念并非递归独有，但它正是因为调用栈溢出问题而出现的。我们已经看到，只要还没有返回值，函数的工作空间就不会消失。观察 sumN 的递归定义，就很容易理解原因：在内部调用 sumN 之后，我们还得做一次加法才能返回结果。然而，如果我们在调用之前就做加法，调用之后就不需要再做额外的工作了。有些语言（在撰写本节时，LeekScript 不在其列）会进行一种叫作''尾调用消除''的优化：当调用方函数只是直接返回被调用函数的结果时，就销毁（或复用）调用方的工作空间，用被调用函数的工作空间取而代之。以 loop 函数为例：调用它时，它唯一做的事情就是再次调用自己。（它没有返回值，但之后也不再做任何工作。）这意味着，如果每次子调用都消除它的工作空间，我们就不会得到一个占用无限大工作空间的程序，而是一个工作空间始终极小的程序，即使它永远不会停止。
再一次套用我们的函数骨架：
function tailSumN(n) { tailSumN(?); return ?; }
和之前不同，这次我们手上的有用信息更少了：
我们的处境和之前几乎一模一样，如果重复之前的步骤，就会得到和之前一样的结果。
最简单的改动是直接返回结果：
function tailSumN(n) { return tailSumN(?); }
我们还需要决定把加法放在哪里。我们不能使用 tailSumN 的结果，所以必须在调用之前做加法：要么先存进一个变量，要么直接写在调用的参数里：
function tailSumN(n) { return tailSumN(? + ?); }
我们可以把 n 当作加法的一个操作数，但还得考虑终止条件。无论哪种做法，我们都需要两个新的值：要么是一个基本情况加上加法的一部分，要么是加法的两个部分。我们把 n 留给终止条件。这意味着我们会有一个值与它比较，而且这个值必须逐渐趋近 n。所以它就是被加到和里的那部分（x），另一个值则是目前为止的和（acc）。
function tailSumN(n, x, acc) { if (? === n) { return ?; } else { return tailSumN(n, ? , x + acc); } }
很容易推断出，x 要和 n 比较。同样，x 是加法每一步中变化的部分，而且已知 0 ，x 趋近于 n，所以只要每次加 1 就能向 n 靠近。
function tailSumN(n, x, acc) { if (x == n) { return ?; } else { return tailSumN(n, x + 1, acc + x); } }
剩下的就是决定终止条件满足时该返回什么。n 只用来控制求和，所以不会用它。单独的 x 没有意义，因为前面各步的和都存在 acc 里。我们有两种可能：要么只返回 acc，要么返回 acc + x。为了在两者之间做选择，可以先代入以下情况，比较两种做法的结果：
很快就能看出，期望的结果由 acc + x 给出。
function tailSumN(n, x, acc) { if (x == n) { return acc + x; } else { return tailSumN(n, x + 1, acc + x); } }
如果初始调用时用 x = 1，最后也可以只返回 acc，但这里的选择让函数的两个分支更加相似。两个分支都做一次加法，只是终止条件满足时，不再调用 tailSumN。
使用这个函数需要用户了解 tailSumN 的工作方式：它需要一个 n、基本情况和一个累加器。而我们只是想得到 0 到 n 的和。所以需要定义一个中间函数，负责用正确的参数调用 tailSumN。
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); } }
现在用户可以直接调用 sumN，不用再多想了。去吧，不妨在你的 Leek Wars 编辑器里试试，或者在这个网站上观察执行过程。 使用三元运算符和闭包来写：
function sumN(n) { var go = function(x, acc) { return x === n ? x + acc : go(x + 1, acc + x); }; return go(0, 0); }
补充一下，go 这样的函数叫作辅助函数（英文为 helper function，或简称 helper）。
有时可以用原始参数（这里是 n）来到达终止条件。所以请你试着不借助中间变量 x 重写 tailSumN。写得简单些，从你已经掌握的知识中找灵感。
把前面练习中的函数找出来，用尾递归重写它们。
列表的定义是：要么是一个空列表（通常叫作 Nil），要么是一个元素加上列表的剩余部分（以序对的形式）。在 LS1 中，我们用空数组 [] 表示 Nil，用含两个元素的数组 [a, List a] 表示序对。这样，包含元素 1, 2, 3, 4 的列表就写作 [1, [2, [3, [4, []]]]]。 我们还会定义几个用来操作这种数据类型的实用函数：
function nil() { return []; } // () -> List a // 创建一个空列表。 function cons(x, xs) { return [x, xs]; } // (a, List a) -> List a // 向列表中添加一个元素（也就是创建一个更长的列表）。 function head(xs) { return xs[0]; } // List a -> List a // 取出头部元素，列表为空时崩溃（实际上会返回 null）。 function tail(xs) { return xs[1]; } // List a -> List a // 取出尾部，同上。 function empty(xs) { return xs == nil(); } // List a -> Bool
由于本文的目的是练习递归，fromArray 函数的代码直接给出：
function fromArray(xs) { return arrayFoldRight(xs, cons, nil()); }
它也可以用递归方式重新实现，不妨动手试试，然后把你的实现和上面这个的结果做个比较。
要操作列表中的元素，我们需要把列表拆开，先处理头部元素，再处理其余的元素。第一个练习，你要实现一个递归函数，打印参数列表中的元素。第一个版本按从外到内的顺序（先序，pre order）打印：1, 2, 3, 4 -> 1 2 3 4；第二个版本按从内到外的顺序（后序，post order）打印：1, 2, 3, 4 -> 4 3 2 1。Nil 不打印。 你可以直接操作数组，但最好使用上面定义的专用函数。变量是用不上的：你的代码里不应该出现 var 关键字和赋值运算符 =。
记住，先从终止条件入手。这种数据类型非常简单，只有两种可能的情况，所以决定何时停止递归也非常简单。
函数骨架：
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
现在你已经会遍历列表，并按某种顺序处理其中的元素了。接下来你要实现一个 toArray 函数：参数是一个列表，返回一个元素顺序相同的数组。也就是说：[1, 2, 3, 4] == toArray(fromArray([1, 2, 3, 4]))。同样，尽量使用列表操作函数，不要直接操作数组（当然，结果数组除外）。
function toArray(xs) { /* code */ } // List a -> Array a
debug([1, 2, 3, 4] == toArray(fromArray([1, 2, 3, 4]))); > [LeekySquash] true
有好几种正确的实现，但最简单的一种不需要变量，也不需要赋值。
现在你可以用 debug(toArray(xs)) 把列表以紧凑易读的方式打印出来，检查函数结果也就更方便了。
在实现 toArray 的过程中，你可能某个时候得到过顺序颠倒的数组。下面这个练习做的是同样的事，只不过结果是一个列表。你要实现一个 reverse 函数：参数是一个列表，返回一个元素顺序反过来的新列表。（数组已经有同名函数了，但没人用它，所以尽管拿这个名字来用。）同样，尽量只使用为此准备的函数，不要去碰数组。
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
相等运算符 == 对我们的列表能直接生效，因为它们是由数组构成的；但如果我们真的创建了一种新的数据类型，就得自己实现这个运算符。所以这正是你接下来要做的。至少应该实现 equ (==) 和 lesserThan (), lesserEqu (=) 也实现了。
好了，这些都挺有意思，但你大概想更深入地使用列表，比如计算长度、获取指定索引处的元素、转换内容等等。下面就列出（嘿嘿）一些你应该实现的函数，帮助你更好地理解这种数据结构以及如何操作它：
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()); }
列表挺不错的（在 LS1 里就没那么好了），但由于有数组，它在 Leek Wars 中的用处有限。现在我们来认识一种稍微复杂一点的数据结构。如果把列表定义为 List a = Nil | Cons a (List a)，那么二叉树的定义几乎一样：Tree a = Nil | Node a (Tree a) (Tree a)。很容易看出，列表就是一棵其中一个分支总是 Nil 的树。我们还可以认为，列表和二叉树都是更一般的数据结构的特例，不过这个以后再讲。
我们先来定义操作二叉树的函数：
function nil() { return []; } // () -> Tree elem // 创建一棵空树。 function node(x, ls, rs) { return [x, ls, rs]; } // (elem, Tree elem, Tree elem) -> Tree elem // 把两棵树和一个元素组合成一棵新树。 function head(xs) { return xs[0]; } // Tree elem -> elem // 取出头部元素，树为空时崩溃（实际上会返回 null）。 function left(xs) { return xs[1]; } // Tree elem -> Tree elem // 取出左子树，说明同 head function right(xs) { return xs[2]; } // Tree elem -> Tree elem // 取出右子树，说明同 head function empty(xs) { return xs == nil(); } // Tree elem -> Bool
又名：优雅的暴力。
如果你还没做 fibonacci 那道练习，先从它开始。
现在试试 120 这样的值。LeekScript 不会自动把数字转换成大整数（Bignum），所以结果不对也不用担心。不过，如果你两个版本都实现对了，就会注意到递归版本没能给你返回结果，而尾递归版本却能毫无问题地算下去，尽管我们根本没有尾调用消除。 这是因为对于每个 n > 1，fibonacci 都会被再调用两次，于是这个函数的时间复杂度是 O(2^n)。（并不精确，但这里我们关心的是它的指数级特性。）相比之下，尾递归版本的 fibonacci 以 O(n) 运行：在求解 fibonacci(n) 的整个过程中，我们没有重复任何工作。然而，fibonacci 的递归定义比尾递归定义容易实现得多，也容易理解得多。所以我们希望同时享受前者的简便和后者的性能。为此，必须确保不做无谓的重复计算，也就是需要保存中间结果。定义这样一个函数：检查某个结果是否已经计算并缓存过，如果是就直接返回它，否则就计算、保存再返回。这种方法叫作''记忆化''。下面是一个记忆化 fibonacci 的基础示例：
global fibmem = [];
function fibonacci(n) { var ret = fibmem[n]; if (ret !== null) { return ret; } else { if (n memoize 是这样一个函数，它接收一个单参数函数作为参数，返回这个函数的记忆化版本。那么我们可以这样定义 fibonacci：
global fibonacci = memoize(function(n) { return n fibonacci 定义时间复杂度为 O(n)，但空间复杂度为 0(n)，而尾递归定义的空间复杂度是 0(1)。
一些有趣但你大概用不上的东西。
Impossible de charger les données du jeu.
Vérifiez votre connexion et réessayez.