Question

求数的递归

Answer 1

递归，又译为递回，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。例如，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现的。也可以理解为自我复制的过程。在数学和计算机科学中，当一类对象或方法可以由两个属性定义时，它们表现出递归行为:

简单的基线条件---不使用递归产生答案的终止情况
一组规则将所有其他情形缩减到基线条件
例如，以下是某人祖先的递归定义:

某人的父母是他的祖先（基线条件）
某人祖先的祖先也是他的祖先（递归步骤）
斐波那契数列是递归的经典例子:

Fib(0) = 1 基线条件1；

Fib(1) = 1 基线条件2；

对所有整数n,n > 1时：Fib(n) = (Fib(n-1) + Fib(n-2))。

许多数学公理基于递归规则。例如，皮亚诺公理对自然数的形式定义可以描述为:0是自然数，每个自然数都有一个后继数，它也是自然数。通过这种基线条件和递归规则，可以生成所有自然数的集合。

递归定义的数学对象包括函数、集合，尤其是分形。

递归还有多种开玩笑的“定义”。递归是当程序的一个步骤涉及调用程序本身的过程。经历递归的过程被称为“递归”。

要理解递归，必须认识到程序和程序运行之间的区别。程序是基于一组规则的一组步骤。程序的运行实际上包括遵循规则和执行步骤。一个类比:一个程序就像一个书面的食谱；运行一个程序就像实际准备饭菜一样。

递归与过程规范中对其他程序执行的引用相关，但不相同。例如，食谱可能指烹饪蔬菜，而需要依次加水等步骤是另一个程序。然而，递归过程是指(至少)其中一个步骤需要一个相同过程的新实例，就像酸面团配方需要上次制作相同配方时剩下的一些面团。这立即产生了一个无限循环的可能性；如果为了程序能够完成，在某些情况下跳过有问题的步骤，这样递归只能在定义中被正确使用，比如一个酸面团配方，它还告诉您如何获取一些生面团，以防您以前从未做过生面团。即使定义正确，递归过程对人类来说也不容易执行，因为它需要区分过程的新调用和旧调用(部分执行)；这需要对程序的各种同步实例的进展程度进行一些管理。因此，递归定义在日常情况下非常罕见。一个例子可以是下面的寻找迷宫之路的过程，继续前进，直到到达出口或分支点(死角被认为是带有0个分支的分支点)。如果到达的点是出口，终止。否则，递归地使用该过程，依次尝试每个分支；如果每次试验都只到达死胡同而失败，返回到导致这个分支点的路径并报告失败。这是否真正定义了终止过程取决于迷宫的性质:它不允许循环。在任何情况下，执行该过程都需要仔细记录所有当前探索的分支点，以及哪些分支已经被彻底尝试过。