(Python) 子例程。递归

递归

过程或函数可能包含对其中另一个过程的调用。其中，子程序可以调用自身。在这种情况下，计算机不关心。他也一如既往，从上到下始终如一地执行他遇到的命令。

如果你还记得数学，那你就会遇到 数学归纳原理。具体如下：
对于每个自然 n 如果
    1. 对 n = 1 和
有效     2. 从对任意自然数 n = k 的陈述的有效性来看，它对  n = k + 1 为真。

在编程中，这种技术称为递归。
   

例子

<前> def Rec(a): 如果 (a>0): Rec(a-1) 打印（一）
示意性地，递归的工作可以用流程图表示



Rec() 过程以参数 3 执行。然后，在参数 3 的过程中，调用参数 2 的过程，依此类推，直到调用参数 0 的过程。当调用参数 0 的过程时，递归调用将不再发生，参数为 0 的过程将打印数字 0 并退出。然后控制权返回给参数为 1 的过程，它也通过打印数字 1 来完成它的工作，依此类推。在带有参数 3 的过程之前。 

所有被调用的过程都存储在内存中，直到它们完成它们的工作。并发过程的数量称为递归深度。
 

作为循环替代的递归

我们已经看到，递归是重复执行子程序中包含的指令。反过来，这类似于循环的工作。有些编程语言完全没有循环结构。例如，Prolog。 
让我们尝试模拟循环 for 的工作。 
for 循环包含一个计步器变量。在递归子程序中，这样的变量可以作为参数传递。 <前> # Procedure LoopImitation() 有两个参数 # 第一个参数 –计步器，第二个参数——总步数 def LoopImitation(i, n): print("Hello N", i) # 对 i 的任何值重复的语句 如果我n: # 直到循环计数器等于值n， LoopImitation(i + 1, n) # 调用过程的新实例， # 带参数 i+1（转到下一个值 i）

递归和迭代

迭代 在编程中-循环数据处理过程的一步。 
当前步骤（迭代）的迭代算法通常使用在先前步骤计算的相同操作或动作的结果。  此类计算的一个例子是递归关系的计算。 
递归值的一个简单示例是阶乘：\(N!=1 \cdot 2 \cdot 3 \cdot \ ... \ \cdot N\)。
每一步（迭代）的值的计算是 \(N=N \cdot i\) 。 在计算\(N\)的值时，我们取已经存储的值 \(N\) >.

一个数的阶乘也可以用递归公式来描述：
\(\begin{equation*} n!= \begin{cases} 1 &\text{n <= 1,}\\ (n-1)!\cdot n &\text{n > 1.} \end{cases} \end{equation*}\)

你可能会注意到这个描述只不过是一个递归函数。
这里第一行 (\(n <= 1\)) 是基本情况（递归终止条件），第二行是到下一步的过渡。   <正文>
应该理解，函数调用涉及一些额外的开销，因此非递归阶乘计算会稍微快一些。 

结论： 如果您可以使用简单的迭代算法编写程序，无需递归，那么您就需要编写无递归的程序。但是，仍然存在一大类仅通过递归实现计算过程的问题。
另一方面，递归算法通常更容易理解。
 

递归阶乘函数	迭代算法
def 阶乘（n）： 如果 n > 1: 返回 n * 阶乘 (n - 1) 别的：  返回 1	x=1 对于我在范围内（1，n + 1）： x = x * 我;
任务 在部落语言“Tumba-Yumba”的字母表中；四个字母：“K”、“L”、“M”和“N”。需要在屏幕上显示所有由 n 个字母组成的单词，这些单词可以由这个字母表的字母组成 这个问题是一个普通的蛮力问题，可以简化为一个更小的问题。 我们将依次用字母替换单词。 单词的第一个位置可以是字母表中的 4 个字母之一 (K, L, M, N)。 首先，将字母“K”放在首位。然后，为了得到第一个字母为'K'的所有变体，你需要枚举剩下的n-1 positions and .etc. （见图） 因此，我们想出了一个递归的解决方案：在一个循环中，遍历所有可能的第一个字母（依次将字母表中的每个字母放在首位）并为每种情况构建所有可能的“尾巴”；长度n-1.   字符的递归迭代 当剩余部分为空（n = 0）时，您需要停止递归并输出完成的单词，即所有字母都已被选中。  递归过程如下所示：  <前> def TumbaWords（单词，字母表，n）： 如果 n < 1: 打印（单词） 返回 对于字母表中的 c： TumbaWords（单词+c，字母表，n - 1） Training problem 迭代第 1 行