求数的递归

递归，又译为递回，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。例如，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现的。也可以理解为自我复制的过程。在数学和计算机科学中，当一类对象或方法可以由两个属性定义时，它们表现出递归行为:简单的基线条件---不使用递归产生答案的终止情况一组规则将所有其他情形缩减到基线条件例如，以下是某人祖先的递归定义:某人的父母是他的祖先（基线条件）某人祖先的祖先也是他的祖先（递归步骤）斐波那契数列是递归的经典例子:Fib(0) = 1 基线条件1；Fib(1) = 1 基线条件2；对所有整数n,n > 1时：Fib(n) = (Fib(n-1) + Fib(n-2))。许多数学公理基于递归规则。例如，皮亚诺公理对自然数的形式定义可以描述为:0是自然数，每个自然数都有一个后继数，它也是自然数。通过这种基线条件和递归规则，可以生成所有自然数的集合。递归定义的数学对象包括函数、集合，尤其是分形。递归还有多种开玩笑的“定义”。递归是当程序的一个步骤涉及调用程序本身的过程。经历递归的过程被称为“递归”。要理解递归，必须认识到程序和程序运行之间的区别。程序是基于一组规则的一组步骤。程序的运行实际上包括遵循规则和执行步骤。一个类比:一个程序就像一个书面的食谱；运行一个程序就像实际准备饭菜一样。递归与过程规范中对其他程序执行的引用相关，但不相同。例如，食谱可能指烹饪蔬菜，而需要依次加水等步骤是另一个程序。然而，递归过程是指(至少)其中一个步骤需要一个相同过程的新实例，就像酸面团配方需要上次制作相同配方时剩下的一些面团。这立即产生了一个无限循环的可能性；如果为了程序能够完成，在某些情况下跳过有问题的步骤，这样递归只能在定义中被正确使用，比如一个酸面团配方，它还告诉您如何获取一些生面团，以防您以前从未做过生面团。即使定义正确，递归过程对人类来说也不容易执行，因为它需要区分过程的新调用和旧调用(部分执行)；这需要对程序的各种同步实例的进展程度进行一些管理。因此，递归定义在日常情况下非常罕见。一个例子可以是下面的寻找迷宫之路的过程，继续前进，直到到达出口或分支点(死角被认为是带有0个分支的分支点)。如果到达的点是出口，终止。否则，递归地使用该过程，依次尝试每个分支；如果每次试验都只到达死胡同而失败，返回到导致这个分支点的路径并报告失败。这是否真正定义了终止过程取决于迷宫的性质:它不允许循环。在任何情况下，执行该过程都需要仔细记录所有当前探索的分支点，以及哪些分支已经被彻底尝试过。