Cairo 之旅 VI：掌握递归 - Diamond

作者：Darington Nnam 原文：Journey through Cairo VI — Mastering Recursion 翻译：Louis Wang 校对：「StarkNet 中文社区」

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

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

P.S：教程中的语法代码都是在 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)
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 关键字，这是撤销引用，我们将在本系列的下一讲深入研究。

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

没问题。

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 个练习，这将有助于提高你对递归的理解。

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