c# - 为什么这个方法需要递归？

Question

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

在本书最开始的类(class)中，他们在熟练评估部分展示了这个有趣的场景:

You are developing a library of utility functions for your application. You need to write a method that takes an integer and counts the number of significant digits in it. You need to create a recursive program to solve this problem. How would you write such a program?

我发现自己对这种情况感到困惑。如果我正确理解“有效数字”，那么计算整数有效数字的函数就没有必要递归了。而且，任何坚持递归的架构师都应该检查一下他的头脑。

还是我没听懂？我在这里完全错过了什么吗？据我了解，有效数字是数字的数字，从左到右，不包括任何前导零。

在什么情况下需要递归？ (对我来说，这个练习的全部意义在于学习新事物。有人扔给我一根骨头。)

编辑:我不想回答问题。我可以自己解决这个问题。在我看来，通过对字符串中的字符进行简单的 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));
    }
}

Answer 1

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

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

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

有些人(通常是数学爱好者，包括我自己)认为递归算法在适合的地方更优雅(例如“解决方案搜索空间”减少得非常快，以免耗尽你的堆栈).

我质疑在这个特殊案例中的适用性，因为迭代解决方案不是太复杂，但发问者必须提供一些问题，而这个问题相对容易解决.

并且，根据您的编辑:

... could be solved far more easily with a simple foreach loop over the characters in a string

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