如何实现仅接收整数n的递归最小除数求解函数？

嘿，我懂你想要的是一个只接收整数n作为参数的递归函数，不用额外的辅助参数对吧？没问题，我们可以通过嵌套递归函数的方式来实现，既满足单参数的要求，又保留递归逻辑，还能优化效率。

修改后的完整代码 #

using System;

public class Program {
    public static void Main() {
        int n = Convert.ToInt32(Console.ReadLine());
        Console.WriteLine(SmallestDivisor(n));
    }

    public static int SmallestDivisor(int n) {
        // 处理基础情况：n=2直接返回2
        if (n == 2) return 2;
        // 如果是偶数，最小除数必然是2
        if (n % 2 == 0) return 2;
        
        // 内部嵌套的递归函数，负责从奇数开始检查除数
        int FindDivisor(int d) {
            // 优化：如果d的平方大于n，说明n是质数，直接返回n
            if ((long)d * d > n) return n;
            if (n % d == 0) return d;
            // 只检查奇数，每次加2减少递归次数
            return FindDivisor(d + 2);
        }
        
        // 初始调用内部递归，从3开始检查
        return FindDivisor(3);
    }
}

思路详解 #

• 基础情况处理：先直接处理偶数和n=2的简单场景，避免不必要的递归调用。
• 嵌套递归函数：在主函数内部定义一个带辅助参数的递归函数FindDivisor，这个函数只在内部使用，外部调用者看不到这个参数，完美满足你“仅接收n作为参数”的要求。
• 效率优化：
  • 因为已经排除了偶数，所以每次递归只检查奇数（d+2），减少了一半的递归次数。
  • 加入了(long)d*d >n的判断：如果当前检查的除数的平方已经大于n，说明n是质数，直接返回n本身，避免无意义的递归。

对比原代码的优势 #

原代码的辅助参数版本虽然能工作，但对于大质数会进行大量无意义的偶数检查，而且没有终止条件的优化，递归次数会非常多。修改后的版本不仅满足单参数要求，还大幅提升了效率，同时降低了栈溢出的风险。

内容的提问来源于stack exchange，提问作者FunnyBuzer