子程序。递归

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

如果你记得数学，那么在那里你可以满足数学归纳法的原理。如下所示： 某些陈述对于每个自然 n 如果
    1) 它对 n = 1有效；
    2) 从对任意自然 n = k 的陈述的有效性来看，它对  n = k+1 为真。

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

递归 是一种根据给定的简单基本情况根据集合本身定义一组对象的方法。

递归 是直接或通过其他过程和函数调用自身的过程（函数）。
递归过程的例子：

void Rec(int a)
{
 如果 (a>0) { Rec(a-1);
 控制台.WriteLine(a);
}

从原理上讲，递归的工作可以用流程图表示。

我们发现递归是重复执行子程序中包含的命令。反过来，这类似于循环的工作。有些编程语言根本不存在循环结构，例如 Prolog。 
让我们尝试模拟循环 for 的工作。 
for 循环包含一个计步器变量。在递归子程序中，这样的变量可以作为参数传递。 <前> // 过程 LoopImitation() 有两个参数 // 第一个参数 –计步器，第二个参数——总步数 <代码>static void LoopImitation(int i, int n) { Console.WriteLine("你好 N" + i); // 对于任何值 i 要重复的语句 if (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\)) 是基本情况（递归终止条件），第二行是到下一步的过渡。  
  <正文>
应该理解，函数调用涉及一些额外的开销，因此非递归阶乘计算会稍微快一些。 

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

递归阶乘函数	迭代算法
<前> static int Factorial(int n){ 如果 (n > 1) 返回 n * 阶乘（n - 1）； 否则返回 1； }	<前> int x = 1; for (int i = 2; i <= n; i++) x = x * 我; Console.WriteLine("%d", x);
将数字从一个数字系统递归转换为另一个数字系统   在程序的某些情况下，您可以在不带参数的情况下使用单词 return  - 也就是说，实际上，程序仍然不会返回任何内容。 这在递归时很有用，当  ;return  用于在参数值被递归的基本情况下结束下降。例如，将数字从十进制转换为二进制的过程可能如下所示： static void printTwo(int n) {    如果（n == 0）返回；   printTwo(n / 2);  如果 (n % 2 == 0) Console.Write(0);  否则 Console.Write(1); Training problem 递归翻译：八进制数系统中的数字
任务 在部落语言“Tumba-Yumba”的字母表中；四个字母：“K”、“L”、“M”和“N”。您需要显示所有由 n 个字母组成的单词，这些单词可以从这个字母表的字母组成。 这个问题是一个普通的蛮力问题，可以简化为一个更小的问题。 我们将依次用字母替换单词。 单词的第一个位置可以是字母表中的 4 个字母之一（K、L、M、N）。 让我们把字母K放在第一位。然后，为了得到第一个字母为K的所有变体，您需要枚举剩余n - 1位置的所有可能的字母组合 等等。 （见图） 这样，问题就简化为解决四个长度为n - 1的问题。   递归遍历 n 个字符 w[0]='K'; // 遍历最后的 L-1 个字符 w[0]='L'; // 遍历最后的 L-1 个字符 w[0]='M'; // 遍历最后的 L-1 个字符 w[0]='N'; // 遍历最后的 L-1 个字符 w - 存储工作词的字符串。 因此，我们得到了递归。我们可以将问题的解决方案安排在递归过程的形式。 递归何时结束还有待确定？当设置完所有字符时，即设置的字符个数为n。在这种情况下，您需要在屏幕上显示结果词并退出程序。 C# 程序将如下所示。 <分区> // w - 可变参数（字符串结果） // TumbaWords 程序将字母表作为字符串传递， // 单词word和已经设置的字符数（开头–0） static void TumbaWords（字符串 A，引用字符串 w，int N） { if (N == w.Length) // w.Length - 字符串中的字符数 {   // 如果所有字符都已经设置为单词，       // 然后需要输出一个字符串并结束程序 控制台.WriteLine(w); 返回; } for ( int i = 0; i < w.Length; i ++ ) // 如果上面的条件为假（即不是所有的字符都是间隔的， {     // 如果上面的条件为假（即不是所有的字符都是间隔的，    // 然后在循环中我们遍历字母表中的所有字符并   //交替将字符放在第一个空闲空间 w += A[i]; TumbaWords(A, ref w, N+1); w = w.Remove(w.Length - 1); // 然后删除最后添加的字符，   // 用相同的前缀创建一个新词 } } 静态无效主要（） { int n = Convert.ToInt32(Console.ReadLine()); 字串=“”； TumbaWords(“KLMN”，参考字，0); } 注意 w 是一个可变参数（结果字符串）！ Training problem 遍历行