欢迎来到我们的系列文章「Cairo学习专题」第六讲。上一讲中我们学习了隐式参数，今天我们要聊 Cairo 中很重要的一章：递归。
像往常一样，如果你是中途加入的，建议从头开始看我们的文章。
PS：教程中的语法代码都是在 Cairo v0.9.0 版本下使用的
数组是神秘的
在开始使用 Cairo 时，我听到的一个令人震惊的事情是我不能写循环。没有 for 循环，没有 while 循环等等，只有递归。主要原因是 Cairo 的内存是不可改变的，也就是说，一旦你写了一个内存单元的值，这个单元在将来就不会再改变。
这是很令人沮丧的，但值得庆幸的是，在 Cairo 1.0 中会看到这方面的更新。
什么是递归？
在计算机科学中，递归是一种使用函数或算法的编程技术，它可以一次或多次调用自己，直到满足一个指定的条件。
更简单地说，如果一个函数反复调用自己，该函数就是一个递归函数。注意，该函数必须有一个停止递归的基础条件，否则程序可能会出现堆栈溢出。
递归是相当复杂的，我花了一些时间才完全理解，所以如果你在第一次阅读时没有理解也不要自责。我们将通过一些 Starklings 的练习来更好地解释递归。
recursion01.cairo
在这个练习中，我们要写一个斐波那契数的递归实现，返回第 n 个斐波那契数。要解决这个练习，我们首先要了解什么是斐波纳契数。
斐波那契数列是一个数列，其中每个数字 ( 斐波那契数 ) 都是前面两个数字之和。该系列的前 13 个数字是：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144
从上面的定义中，我们可以看出，要得到第 n 个斐波那契数，我们需要把第 n-1 个的数字和第 n-2 个的数字相加。(因为每个数字都是前面两个数字之和）。
用数学的形式表达：
nth number = (nth - 1) + (nth - 2)
要求第五个斐波那契数，就是：
Fib(5) = Fib(4) + Fib(3)
由前面可知，第三第四个分别是 2，1。所以第五个就是：
Fib(5) = 2 + 1 = 3
我们可以很容易地推导出这一点，那是因为我们只求了第五，但想象一下要求得到第一百个斐波那契数字，我们不能手动做这件事，我们需要写一个程序来做这件事。
如果我们使用 Javascript、Python、Solidity 等，我们可以很容易地使用 for 循环来完成这个任务，但由于 Cairo 还不支持 for 循环，我们要使用递归，具体步骤如下：
首先我们需要注意，由于我们正在编写一个计算机程序，我们的第一个斐波那契数字的索引是0，而不是 1。
我们要设置基本条件以避免堆栈溢出。由于我们已经知道第一个和第二个斐波那契数总是 0 和 1，所以我们要检查我们的 n，如果是 0 就自动返回 0，如果是 1 就返回 1：
if n == 0:return (0)endif n == 1:
return (1)end
由于第 n 个斐波那契项是第 n-1 个和第 n-2 个的数字之和，我们需要用递归来获得这些数字（调用斐波那契函数，将 n-1 和 n-2 项作为新的 n 传递给它）：
let (x) = fibonacci(n - 1)let (y) = fibonacci(n - 2)
返回这两个数的和：
return (x + y)
完整代码如下：
func fibonacci(n : felt) -> (result : felt):
alloc_locals if n == 0:
return (0)
end if n == 1:
return (1)
end let (local x) = fibonacci(n - 1)
let (local y) = fibonacci(n - 2)
return (x + y)end
这里我们引入了一些新的东西，如 alloc_locals 和 local 关键字，这是撤销引用，我们将在本系列的下一讲深入研究。
现在检查一下我们的测试是否通过：
没问题。
array01.cairo
递归在数组中有着巨大的应用，与循环类似。在这个练习中，我们要通过 contains 函数进行循环，如果 haystack 包含 needle，则返回 1，否则返回 0。
为了解决这个练习，我们将遵循斐波那契练习的步骤。
建立基本条件
首先需要检查给定的数组长度（haystack_len）是否为 0，如果是，我们将自动返回 0，因为这意味着数组是空的。
if haystack_len == 0:
return (0)end
接下来我们检查数组的第一个元素是不是 needle，是的话返回 1
if haystack[0] == needle:
return (1)end
用递归循环 contains 函数
let (contained) = contains(needle, haystack + 1, haystack_len - 1)return (contained)
我们这里用递归循环 contains 函数，每次都将被检查的数组索引增加 1，并将数组长度减少 1。
这背后的逻辑是，每次我们通过 contains 函数进行递归，把数组的输入长度不断减少，直到我们到达数组的最后一个元素。这里有一个场景可以帮助你更好地理解这个问题：
如果我们有一个数组，x 和 needle=3。
x = [0, 1, 2, 3, 4, 5]
检查基本条件：
如果数组长度为 0，我们会返回 0，但事实并非如此，所以我们转而检查 x[0]= needle，但事实并非如此，因为 x[0]=0，但 needle=3。
接下来开始递归：
调用 contains 函数，这次传递的是 needle，将数组索引向上推 1，变成 x+1 而不是 x，然后将数组长度也减少 1，因为我们刚刚从数组中剔除了第一个元素。
因此，当第一次调用 contains 函数时，看起来会是这样的：
contains(3, [1, 2, 3, 4, 5], 5)
继续下去直到数组长度为 0。完整代码：
func contains(needle : felt, haystack : felt*, haystack_len : felt) -> (result : felt):
if haystack_len == 0:
return (0)
end if haystack[0] == needle:
return (1)
end let (contained) = contains(needle, haystack + 1, haystack_len - 1)
return (contained)end
看看能否通过测试：
成功！
最后
开始这个系列以来我们已经取得了重大的进展，很高兴你能走到这一步！
为了缩短本文的篇幅，我们只尝试了 Starklings 中递归部分的 7 个练习中的 2 个。希望你尝试剩下的 5 个练习，这将有助于提高你对递归的理解。
像往常一样，如果你觉得这篇文章有收获，不妨与他人分享。
本文由 wzabing 创作，采用 知识共享署名4.0 国际许可协议进行许可。
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名。