简单的递归？

Question

我是编程新手，很难理解递归。有一个问题我一直在解决但无法解决。我真的不明白它们是如何解决的。

“定义一个过程 plus，它接受两个非负整数并返回它们的和。您可以使用的唯一过程（除了对 plus 的递归调用之外）是：zero?、sub1 和 add1。

我知道这是一个内置过程方案中的函数，所以我知道它们是可以解决的，我只是不明白递归是如此棘手

！ =] 谢谢

我正在 Petite Chez Scheme 工作（使用 SWL 编辑器）

Answer 1

递归是软件开发中一个非常重要的概念。我不知道（petit chez）方案，所以我将从一般角度来处理这个问题。

递归函数的概念是一遍又一遍地重复相同的任务，直到达到某个限制边界。就第一个问题而言，您有两个数字，您需要将它们加在一起。但是，您只能将数字加 1 或将数字减 1。您的字面值也为零。

所以。将数字视为两个桶。他们每人都有 10 块石头。您想将这两个桶“添加”在一起。您一次只能移动一块石头（即您不能抓起一把石头或将一个桶倒入另一个桶中）。

假设您想将所有东西从左边的桶移到右边的桶中，一次一块石头。你需要做什么？

首先，您必须从左边的桶中取出 1 块石头，即您使用 sub1 从桶中取出一颗石头。然后，您将同一块石头添加到右侧的桶中，即您add1 到右侧的桶中。

现在您可以循环执行此操作，但您不知道任何给定解决方案中会有多少石头。你真正想做的是说“从左边的桶中取出一颗石头，将其放入右边的桶中，然后重复，直到左边的桶中没有石头为止。”左桶中没有石头的情况称为“基本情况”，此时您会说“好吧，我现在完成了”，

这种情况的伪代码示例是（使用您的 plus、add1、sub1）。和零）：

plus(leftBucket, rightBucket)
{
  if(leftBucket == zero) // check if the left bucket is empty yet
  {
    // the left bucket is empty, we've moved all the stones
    return rightBucket; // the right bucket must be full
  }
  else 
  {
    // we still have stones in the left bucket, remove 1, 
    // put it in the right bucket, repeat.
    return plus(sub1(leftBucket), add1(rightBucket)); 
  }
}

如果您仍然需要更多帮助，请告诉我，我可以运行其他示例，但这看起来对您来说可能是一个家庭作业问题，并且递归对于理解非常重要，所以我不想只给您全部答案。

Answer 2

递归只是一个调用自身的函数。最常见、最容易理解的递归示例是遍历看起来像树的数据结构。

您将如何访问树的每个分支？您将从树干开始并调用访问（分支），将树干作为第一个分支传递。 Visit() 为每个分支的每个分支调用自身，依此类推。

public void visit(Branch branch)
{
    // do something with this branch here

    // visit the branches of this branch
    foreach(var subbranch in branch.branches)
    {
        visit(subbranch)
    }
}

Answer 3

递归与归纳密切相关 - 首先解决（或证明）基本情况，然后假设您的解决方案对于某些值n是正确的，并用它来解决（或证明）n + 1。

所以这里的第一步是看第一个问题。将两个数字相加的良好基本情况是什么？

---

好吧，我们有了基本情况：当其中一个数字为零时。

为了简单起见，我们假设第二个数字为零，只是为了让事情变得更容易一些。

所以我们知道(+ n 0)等于n。因此，现在对于我们的递归步骤，我们想要进行任意调用 (+ xy)，并将其转换为更接近我们理想的 (+ n 0）。这样我们就会取得一些进展并最终解决我们的问题。

那么我们要怎么做呢？

---

(+ xy) 当然等价于 (+ (add1 x) (sub1 y)) - 这让我们更接近 (zero? y）。

这给了我们最终的解决方案：（

(define (+ x y)
  (if (zero? y)
    (x)
    (+ (add1 x) (sub1 y))
))

当然，您可以交换参数的顺序，它仍然是等效的）。

类似的机制可以用来解决另外两个问题。