为什么这个方法需要递归

本文关键字：递归 方法 为什么 | 更新日期: 2023-09-27 18:24:15

一时兴起，我决定回去寻求认证，从98-361软件开发基础开始。（我做这件事更多的是为了自己，而不是其他任何事情。我想填补我知识上的空白。）

在本书的早期课程中，他们在"熟练评估"部分介绍了这个有趣的场景：

您正在为您的应用您需要编写一个方法，该方法接受一个整数和计算其中的有效位数。您需要创建递归程序来解决这个问题。你怎么会写这样的程序

我发现自己对这种情况感到困惑。如果我正确理解"有效数字"，那么计算整数有效数字的函数就不需要递归。而且，任何坚持认为它是递归的建筑师都应该检查一下自己的头脑。

还是我不明白？我是不是完全错过了什么？据我所知，有效数字是一个数字的数字，从左开始，向右前进，不包括任何前导零。

在什么条件下，这需要递归？（对我来说，这个练习的全部目的是学习新东西。有人扔给我一块骨头。）

编辑：我不想要这个问题的答案。我可以自己解决。在我看来，只要在字符串中的字符上进行简单的foreach循环，这个"问题"就可以更容易地解决。

最终编辑

考虑到下面令人敬畏的海报的明智建议，这就是我为解决这个问题而想出的简单解决方案。（尽管我可能心存疑虑。）

using System;
class Program
{
    static void Main(string[] args)
    {
        var values = new[] { 5, 15, 150, 250, 2500, 25051, 255500005, -10, -1005 };
        foreach (var value in values)
        {
            Console.WriteLine("Signficiant digits for {0} is {1}.", value, SignificantDigits(value));
        }
    }
    public static int SignificantDigits(int n)
    {
        if (n == 0)
        {
            return 0;
        }
        return 1 + SignificantDigits((int)(n / 10));
    }
}

为什么这个方法需要递归

这样的算法不需要递归。但这里的目的不是编写真实世界的代码，而是确保您理解递归。

既然你说你不追求代码，我在这里会很小心，但我需要提供一些东西来比较解决方案的复杂性，所以我将使用伪代码。递归解决方案可能类似于：

def sigDigits (n):
    # Handle negative numbers.
    if n < 0:
        return sigDigits (-n)
    # 0..9 is one significant digit.
    if n < 10:
        return 1
    # Otherwise it's one plus the count in n/10 (truncated).
    return 1 + sigDigits (n / 10)

你是对的，它和迭代一样可行。

def sigDigits (n):
    # Handle negative numbers.
    if n < 0:
        n = -n
    # All numbers have at least one significant digit.
    digits = 1
    # Then we add one and divide by ten (truncated), until we get low enough.
    while n > 9:
        n = n / 10
        digits = digits + 1
    return digits

有些人（通常有数学倾向，包括我自己）认为递归算法在合适的地方更优雅（比如"解决方案搜索空间"减少得很快，以免破坏堆栈）。

我质疑在特定情况下的适用性，因为迭代解决方案并不太复杂，但提问者必须提供一些问题，而这个问题相对容易解决。

而且，根据您的编辑：

可以通过在字符串中的字符上进行简单的foreach循环来更容易地解决

你没有字符串，你有一个整数。我不怀疑你可以把变成一个字符串，然后计算字符数，但这似乎是一种迂回的方法。

它不需要是递归的。简单地说，问题是要求您编写一个递归实现，大概是为了测试您对递归函数如何工作的理解。

这似乎是一个非常强制的例子。这个问题可以用一个更简单的迭代算法来解决。

许多教学资源确实很难提供何时使用递归的有用示例。从技术上讲，你永远不需要来使用它，但对于一大类（主要是算法）问题，它确实可以简化事情。

例如，考虑对二叉树的任何操作。因为二叉树的物理结构是递归的，所以对其进行操作的算法也是自然递归的。您也可以编写命令式算法来对二叉树进行操作，但递归算法更容易编写和理解。

相关文章：