1

The program needs to check if the array is palindrome using recursion, but I get stack overflow exception in unmanaged. Been stuck on it for over a day, please help

public static void Main(string[] args)
{
    char[] arr = { 'd', 'a', 'd' };
    int ind = 0;

    Rowpalindrome(arr, ind);
}

static bool Rowpalindrome(char[] arr, int index)
{
    if (index == arr.Length % 2)
        return true;

    int i = index;

    if (arr[i] != arr[(arr.Length - index - 1)])
        return false;
    else
        return Rowpalindrome(arr, index++);
}
Dmitry Bychenko
  • 180,369
  • 20
  • 160
  • 215
john smith
  • 11
  • 2

1 Answers1

7

You have error in the increment; it should be ++indexinstead of index++:

return Rowpalindrome(arr, ++index);

you should increment and pass modified value of index (++index), not increment and pass initial value (index++). Even better implementation is to put it simple:

return Rowpalindrome(arr, index + 1);

Edit: You have some logical errors as well (thanks to Fildor who's pointed it out): the condition should be

if (arr.Length <= 1 || index > arr.Length % 2 + 1)
    return true;

The final recoursive code can be 

static bool Rowpalindrome(char[] arr, int index) {
  if (arr.Length <= 1 || index > arr.Length % 2 + 1)
    return true;

  // Let's get rid of "i" (which is index) and exploit short circuit of &&:
  // .Net tests arr[index] != arr[(arr.Length - index - 1)]
  // and only if it's true call for Rowpalindrome(arr, index + 1)
  return arr[index] != arr[(arr.Length - index - 1)] && Rowpalindrome(arr, index + 1);
}

Test cases: (Let's use Linq to query for each test)

using System.Linq;

...

var tests = new char[][] {
  new char[] { },
  new char[] { 'a' },
  new char[] { 'a', 'a' },
  new char[] { 'a', 'b' },
  new char[] { 'a', 'b', 'a' },
  new char[] { 'a', 'b', 'c' },
  new char[] { 'a', 'b', 'b', 'a' },
  new char[] { 'a', 'b', 'c', 'a' },
  new char[] { 'a', 'b', 'b', 'c' },
};

var result = tests
  .Select(test => $"{"[" +string.Join(", ", test) + "]", -15} : {(Rowpalindrome(test, 0) ? "Palindrome" : "Not")}");

Console.Write(string.Join(Environment.NewLine, result));

Outcome:

[]              : Palindrome
[a]             : Palindrome
[a, a]          : Palindrome
[a, b]          : Not
[a, b, a]       : Palindrome
[a, b, c]       : Not
[a, b, b, a]    : Palindrome
[a, b, c, a]    : Not
[a, b, b, c]    : Not

Edit 2: In case of multidimensional array (see comments below) you can extract column of interest into an array and run the routine, e.g. for 2D array:

char[,] c = new char[,] {
  { 'a', 'b', 'c'},
  { 'x', 'y', 'z'},
  { 'x', 'p', 'q'},
  { 'a', 'm', 'n'},
};

int colIndex = 0; // should be {'a', 'x', 'x', 'a'} column

// c.GetLength(0) - number of lines (length of the 1st dimension) - 4
char[] a = new char[c.GetLength(0)];

for (int i = 0; i < a.Length; ++i)
  a[i] = c[i, colIndex];

bool result = Rowpalindrome(a, 0);
Dmitry Bychenko
  • 180,369
  • 20
  • 160
  • 215
  • 1
    This `if (index == arr.Length % 2)` also looks incorrect to me. That would make any even-length array a rowpalindrome, wouldn't it? (Not adding it as separate answer, because it is not causing the SOE) – Fildor Oct 30 '18 at 08:33
  • 1
    @Fildor: you are quite right, thank you! There is a *logical* error in the code. – Dmitry Bychenko Oct 30 '18 at 08:43
  • Thank you so much! Can you please help me in another question? I need to do the same only that I'm getting a multidimensional array and a colum and I need to check if the collum is a palindrome – john smith Oct 30 '18 at 09:08
  • 1
    @johnsmith That would be a new question, please. – Fildor Oct 30 '18 at 09:12
  • @john smith: you can try reading the column into an array and then call the *routine*. In case of 2D array: when given `char[,] c = ... int columnIndex = ...` you can do `char[] a = char[c.GetLength(0)]; for (int r = 0; r < a.Length; ++r) a[r] = c[r, columnIndex]; bool isPalindrome = Rowpalindrome(a, 0);` – Dmitry Bychenko Oct 30 '18 at 09:13
  • thank you so much! you saved me, i still have one more question but ill post in a new thread thank you! – john smith Oct 30 '18 at 10:16