递归函数 - 试图理解

Question

我对这段代码有疑问。这不是工作或家庭作业。我只是想了解递归函数。代码一开始是可以工作的，但是当它发现一个超过 22000 个字符的单词时，它导致抛出错误 - 一个 Whosebugexception。

这是代码

using System;

namespace Palindrome
{
    using System.IO;

    public class Program
    {
        public static void Main()
        {
            int c = 0;

            string[] l = File.ReadAllLines("UKACD17.TXT");
            for (int i = 0; i < l.Length; i++)
            {
                string ll = l[i];
                if (T(ll))
                {
                    Console.WriteLine(ll);
                    c++;
                }
            }

            Console.WriteLine("Found {0} palindromes.", c);
            Console.ReadLine();
        }

        private static bool T(string s)
        {
            if (string.IsNullOrWhiteSpace(s)) return false;
            return s.Length == 1 || (s[0] == s[s.Length - 1] && T(s.Substring(1, s.Length - 2)));
        }
    }}

Answer 1

该方法在逻辑上看起来是正确的，但由于执行您的代码的计算机的实际限制，它不会起作用。

无论何时调用一个方法，它都会将调用方法的状态推入堆栈 - 基本上是一个包含数据的内存块，一旦被调用方法执行完毕，这些数据将允许在调用方法中继续执行。

此内存块的大小非常重要，因此如果您尝试递归调用该方法 11000 次（对于 22000 个字符的初始输入），则需要推送 11000 个堆栈帧 - 这显然是一种比允许的更深的递归方式（它也可能在 11000 之前很久就放弃了）。

限制已设置，我想，否则你会用完有限的内存，而这些内存本可以用于其他更有用的东西。

您可以将其变成一个循环，而不是递归地调用该方法：

private static boolean T(string s) {
  if (string.IsNullOrWhiteSpace(s)) return false;
  int i = 0;
  int j = s.length - 1;
  while (i < j) {
    if (s[i] != s[j]) return false;
    i++; j--;
  }
  return true;
}

这使用两个指针指向您向彼此移动的字符串 - 在每一步中，如果它们指向不同的字符，则它不可能是回文，因此您可以 return false；否则，将它们移向彼此并重复。

调用起来要便宜得多，因为不需要压入堆栈帧 - 您所做的只是比较字符和 incrementing/decrementing 几个整数。

递归函数 - 试图理解

Recursive Function -trying to understand

c#

recursion

function