Stack Over Flow Exception Error (Palindrome) C#

Question

Having trouble figuring out this overflow exception error, I believe it has to do with the bool statement but unsure how to get around it. I upload a list of palindromes and the list is read and assigned to string variables.

Is there anyway around this stackoverflow error?

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++) //use for foreach loop can be faster and save a little more memory.
            {
                string ll = l[i];
                if (T(ll)) 
                {
                    Console.WriteLine(ll);
                    c++;
                }
            }

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

        private static bool T(string s)
        {
            if (string.IsNullOrWhiteSpace(s)) return false; //Stops at white spaces, why is this returning a value from the parameter set up?
            return s.Length == 1 || (s[0] == s[s.Length - 1] && T(s.Substring(1, s.Length - 2))); 
        }


    }
}

The error happens during the palindrome comparison: private static bool T(string s). A recursive logic that compares the first and last letters and then uses the logic again to test the letters in between. Ex: Blob, B vs b (true), then uses the code again and tests l vs o (false).

Should I create an exception? Or is there a way around this through the logic?

This code does not crash for sample input I tested. Find out one specific input that causes it to crash and update your answer. Note, you fail to detect valid palendromes with an even length, e.g. you find `ABCBA` but not `ABCCBA`. — Eric J., Mar 09 '23 at 04:46
Not answering your question, but you have a comment: _"save a little more memory"_. I don't know how long your text file is, but rather than `File.ReadAllLines`, consider reading the data in line by line and looping over that — Flydog57, Mar 09 '23 at 04:51
To avoid a stack overflow, don't put so many frames on the stack. Consider the potential depth of recursive function calls when making them. In this case `T()` is recursively called up to half the length of the input strings, for long strings that's very many times. So the simplest option is just don't do this recursively. — moreON, Mar 09 '23 at 04:57
Indeed, a non-recursive implementation is trivial and is faster. Unless you must do this recursively e.g. for an assignment, I would do it iteratively. FYI, every recursive algorithm can be expressed iteratively. https://stackoverflow.com/questions/931762/can-every-recursion-be-converted-into-iteration — Eric J., Mar 09 '23 at 05:02

score 0 · Answer 1 · answered Mar 09 '23 at 06:19

The default stack size for a 64-bit process is 4mb (32-bit process is 1mb).

Each recursive call allocates a new string on the heap and places a reference (essentially a pointer) to that heap memory on the stack along with information about how to return from the function call.

If the input string is long enough, you will run out of stack space before completing the recursive check for palendromeness.

How long does a string need to be to cause this exception?

Replace this line of yours:

string[] l = File.ReadAllLines("UKACD17.TXT");

with this:

string[] l = new string[] 
{ 
    new string(Enumerable.Repeat<char>('A', 50000).ToArray())
};

Running this in 64-bit LinqPad, I get a StackOverflowException. Changing 50000 to 5000, the program does not crash. Tweak that value to see how long a string you can process with the available stack.

You can alternatively convert the recursive algorithm to an interative one like this:

static bool T(string ll)
{
    var len = ll.Length/2;
    for (int i = 0; i <= len; i++)
        if (ll[i] != ll[ll.Length - i - 1])
            return false;
    
    return true;
}

The iterative algorithm will run much faster because it doesn't make heap allocations or function calls.

Stack Over Flow Exception Error (Palindrome) C#

1 Answers1