Module: 子程序。递归


Problem

5/12

递归和迭代

Theory Click to read/hide

递归和迭代
要理解递归，你需要理解递归...
 
迭代 在编程中-循环数据处理过程的一步。 
当前步骤（迭代）的迭代算法通常使用在先前步骤计算的相同操作或动作的结果。  此类计算的一个例子是递归关系的计算。 
递归值的一个简单示例是阶乘：\(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\)) 是基本情况（递归终止条件），第二行是到下一步的过渡。  
  <正文>
应该理解，函数调用涉及一些额外的开销，因此非递归阶乘计算会稍微快一些。 

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

Problem

定义一个函数 K(n)，返回给定自然数的位数 n为

\(\begin{equation*} K(n) = \begin{cases} 1 &\text{if n < 10}\\ K(n / 10) + 1 &\text{if n >= 10} \end{cases} \end{equation*}\).

编写一个递归函数，使用上面的比率计算自然数 n 中的位数。

time 1000 ms
memory 32 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C#
递归阶乘函数 迭代算法
<前> 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);
1 
using System;
2 
class Program
3 
{
4 
    static int countDigits(int n)
5 
    {
6
7
8
9
10 
        return 1 + countDigits(n / 10);
11 
    }
12 
    static void Main()
13 
    {
14 
        int n = Convert.ToInt32(Console.ReadLine());
15 
        Console.WriteLine(countDigits(n));
16 
    }
17 
}

     

Program check result

To check the solution of the problem, you need to register or log in!