myProgrammingLab Palindrome Challenge Using Recursion-CodePudding

I'm taking an Intro to Programming class and a good chunk of the material is drilled into our heads through myProgrammingLab. I'm having a little trouble with the concept of Recursion... It's sort of been hit or miss for me. This particular problem has me stumped. When I submit my code, it offers me

CTest1.cpp: In function 'bool isPalindrome(int*, int)': CTest1.cpp:9: error: invalid conversion from 'int' to 'int*' CTest1.cpp:9: error: initializing argument 1 of 'bool isPalindrome(int*, int)'" as advice, which I can assure you is not very helpful. Lol

I think my main problem is when I get to the actual recursion. I'm aware that something's off, but.. If you could just point me in the right direction, I would very much appreciate it.

A 'array palindrome' is an array which, when its elements are reversed, remains the same (i.e., the elements of the array are same when scanned forward or backward)

Write a recursive, bool-valued function, isPalindrome, that accepts an integer -valued array , and the number of elements and returns whether the array is a palindrome.

An array is a palindrome if: the array is empty (0 elements ) or contains only one element (which therefore is the same when reversed), or the first and last elements of the array are the same, and the rest of the array (i.e., the second through next-to-last elements ) form a palindrome.

My code so far:

bool isPalindrome(int arr[], int n)
{
    if (n == 0 || n == 1)
    {
        return true;
    }
    else if (arr[n-1] == isPalindrome(arr[((n-1) - n)  1 ], n))
    {
        return true;
    } 
    else 
    {
        return false;
    }
}

CodePudding user response：

isPalindrome does not accept an int as a first argument. It accepts only an array, by doing this: arr[((n-1) - n) 1] you are feeeding it an int instead if an array of ints. This ((n-1) - n) 1 will evaluate to a “position” in the array, eg: arr[0] being the first element, your case an int.

CodePudding user response：

Recursion mostly has three main components:

a stopping condition (when you reach an array size small enough to be a guaranteed palindrome (0 or 1)),
a computation step (e.g. to compare the first and last item of the array and determine whether it makes sense to continue) and
a data subset selection for the nested recursion call (e.g. an array of size n - 2, excluding the first and last characters, which we already compared and found “palindrome-worthy”).

The three components in code:

bool isPalindrome(int arr[], size_t n) {
  return n < 2 || (
         arr[0] == arr[n - 1] &&
         isPalindrome(arr   1, n - 2));
}

Of course you may want to test the function a bit (and do not forget to run it under valgrind as well):

#include <iostream>

int main() {
  std::cout << isPalindrome((int[0]){}, 0) << std::endl;
  std::cout << isPalindrome((int[1]){1}, 1) << std::endl;
  std::cout << isPalindrome((int[2]){1, 1}, 2) << std::endl;
  std::cout << isPalindrome((int[2]){2, 1}, 2) << std::endl;
  std::cout << isPalindrome((int[2]){1, 2}, 2) << std::endl;
  std::cout << isPalindrome((int[3]){1, 2, 1}, 3) << std::endl;
  std::cout << isPalindrome((int[3]){2, 2, 2}, 3) << std::endl;
  std::cout << isPalindrome((int[3]){2, 2, 1}, 3) << std::endl;
  std::cout << isPalindrome((int[4]){1, 2, 1, 2}, 4) << std::endl;
  std::cout << isPalindrome((int[4]){1, 2, 2, 1}, 4) << std::endl;
  std::cout << isPalindrome((int[4]){1, 2, 3, 2}, 4) << std::endl;
  std::cout << isPalindrome((int[4]){2, 3, 2, 1}, 4) << std::endl;
  std::cout << isPalindrome((int[4]){1, 3, 3, 1}, 4) << std::endl;
}

As a side note, this^^^ deadly struggle with arrays suggests that a different data type would be a much better choice. For example, std::string or std::vector can be initialized way easier, should be passed by reference and, as a bonus, STL containers carry size information with them. Additionally, you can use std::string_view for substrings and std::span for “subvectors” in your recursion, without copying the container over and over on each recursion level.

Here’s an example with std::string_view and three different implementations (one with recursion and two without recursion):

#include <iostream>
#include <string_view>

bool isPalindrome1(const std::string_view s) {
  return s.size() < 2 || (
         s[0] == s[s.size() - 1] &&
         isPalindrome1(s.substr(1, s.size() - 2)));
}

bool isPalindrome2(const std::string_view s) {
  const size_t end = s.size() / 2;
  for (size_t i = 0; i < end;   i)
    if (s[i] != s[s.size() - i - 1])
      return false;
  return true;
}

bool isPalindrome3(const std::string_view s) {
  auto b = s.begin();
  const auto end = b   s.size() / 2;
  auto e = s.rbegin();
  for (; b < end;   b,   e)
    if (*b != *e) return false;
  return true;
}

int main() {
  for (auto isPalindrome : {isPalindrome1,
                            isPalindrome2,
                            isPalindrome3}) {
    std::cout << isPalindrome("") << std::endl;
    std::cout << isPalindrome("a") << std::endl;
    std::cout << isPalindrome("ab") << std::endl;
    std::cout << isPalindrome("aa") << std::endl;
    std::cout << isPalindrome("abc") << std::endl;
    std::cout << isPalindrome("aba") << std::endl;
    std::cout << isPalindrome("baab") << std::endl;
    std::cout << isPalindrome("baba") << std::endl;
  }
}