# Cairo 之旅 VI：掌握递归

By [Starknet 中文](https://paragraph.com/@starknet-zh) · 2022-10-29

---

> 作者：[Darington Nnam](https://twitter.com/0xdarlington) 原文：[Journey through Cairo VI — Mastering Recursion](https://medium.com/@darlingtonnnam/journey-through-cairo-vi-mastering-recursion-8f03e4242b56) 翻译：[Louis Wang](https://twitter.com/lviswang) 校对：[「StarkNet 中文社区」](https://twitter.com/StarkNet_ZH)

欢迎来到我们的系列文章「Cairo之旅」第六讲。上一讲中我们学习了隐式参数，今天我们要聊 Cairo 中很重要的一章：递归。

像往常一样，如果你是中途加入的，建议从头开始看我们的文章。

_P.S：教程中的语法代码都是在 Cairo v0.9.0 版本下使用的_

数组是神秘的
------

在开始使用 Cairo 时，我听到的一个令人震惊的事情是我不能写循环。没有 for 循环，没有 while 循环等等，只有递归。主要原因是 Cairo 的内存是不可改变的，也就是说，一旦你写了一个内存单元的值，这个单元在将来就不会再改变。

这是很令人沮丧的，但值得庆幸的是，在 Cairo 1.0 中会看到这方面的更新。

什么是递归？
------

在计算机科学中，递归是一种使用函数或算法的编程技术，它可以一次或多次调用自己，直到满足一个指定的条件。

更简单地说，如果一个函数反复调用自己，该函数就是一个递归函数。注意，该函数必须有一个停止递归的基础条件，否则程序可能会出现堆栈溢出。

递归是相当复杂的，我花了一些时间才完全理解，所以如果你在第一次阅读时没有理解也不要自责。我们将通过一些 Starklings 的练习来更好地解释递归。

### recursion01.cairo

![](https://storage.googleapis.com/papyrus_images/2fe1d7b996f33ee1aa4c586b1e6e0a34094f0ed7e0e3c2c1b96d7b86904972a6.png)

在这个练习中，我们要写一个斐波那契数的递归实现，返回第 n 个斐波那契数。要解决这个练习，我们首先要了解什么是斐波纳契数。

斐波那契数列是一个数列，其中每个数字 ( 斐波那契数 ) 都是前面两个数字之和。该系列的前 13 个数字是：

从上面的定义中，我们可以看出，要得到第 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)
    end
    if 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 关键字，这是撤销引用，我们将在本系列的下一讲深入研究。

现在检查一下我们的测试是否通过：

![](https://storage.googleapis.com/papyrus_images/083e4c42762920c396096340a3e941adef18783285e164cdea7f2b20447ade8c.png)

没问题。

### 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
    

看看能否通过测试：

![](https://storage.googleapis.com/papyrus_images/734dd455fa275b827cdb4eb3a0fb6c1af11883ce68e89b5ac4d3b5215dbdd368.png)

成功！

最后
--

开始这个系列以来我们已经取得了重大的进展，很高兴你能走到这一步！

为了缩短本文的篇幅，我们只尝试了 Starklings 中递归部分的 7 个练习中的 2 个。希望你尝试剩下的 5 个练习，这将有助于提高你对递归的理解。

像往常一样，如果你觉得这篇文章有收获，不妨与他人分享。

---

*Originally published on [Starknet 中文](https://paragraph.com/@starknet-zh/cairo-vi)*