Program to check if an array is palindrome or not using Recursion
Given an array. The task is to determine whether an array is a palindrome or not using recursion.
Examples:
Input: arr[] = {3, 6, 0, 6, 3}
Output: PalindromeInput: arr[] = {1, 2, 3, 4, 5}
Output: Not Palindrome
Approach:
- Base case: If array has only one element i.e. begin == end then return 1, also if begin>end which means the array is palindrome then also return 1.
- If the first and the last elements are equal then recursively call the function again but increment begin by 1 and decrement end by 1.
- If the first and last element is not equal then return 0.
Below is the implementation of the above approach:
C++
// C++ implementation of above approach #include <iostream> using namespace std; // Recursive function that returns 1 if // palindrome, 0 if not palindrome int palindrome( int arr[], int begin, int end) { // base case if (begin >= end) { return 1; } if (arr[begin] == arr[end]) { return palindrome(arr, begin + 1, end - 1); } else { return 0; } } // Driver code int main() { int a[] = { 3, 6, 0, 6, 3 }; int n = sizeof (a) / sizeof (a[0]); if (palindrome(a, 0, n - 1) == 1) cout << "Palindrome" ; else cout << "Not Palindrome" ; return 0; } |
Java
// Java implementation of above approach import java.io.*; class GFG { // Recursive function that returns 1 if // palindrome, 0 if not palindrome static int palindrome( int arr[], int begin, int end) { // base case if (begin >= end) { return 1 ; } if (arr[begin] == arr[end]) { return palindrome(arr, begin + 1 , end - 1 ); } else { return 0 ; } } // Driver code public static void main (String[] args) { int a[] = { 3 , 6 , 0 , 6 , 3 }; int n = a.length; if (palindrome(a, 0 , n - 1 ) == 1 ) System.out.print( "Palindrome" ); else System.out.println( "Not Palindrome" ); } } |
Python 3
# Python 3 implementation of above approach # Recursive function that returns 1 if # palindrome, 0 if not palindrome def palindrome(arr, begin, end): # base case if (begin > = end) : return 1 if (arr[begin] = = arr[end]) : return palindrome(arr, begin + 1 , end - 1 ) else : return 0 # Driver code if __name__ = = "__main__" : a = [ 3 , 6 , 0 , 6 , 3 ] n = len (a) if (palindrome(a, 0 , n - 1 ) = = 1 ): print ( "Palindrome" ) else : print ( "Not Palindrome" ) # This code is contributed # by ChitraNayal |
C#
// C# implementation of above approach using System; class GFG { // Recursive function that returns 1 // if palindrome, 0 if not palindrome static int palindrome( int []arr, int begin, int end) { // base case if (begin >= end) { return 1; } if (arr[begin] == arr[end]) { return palindrome(arr, begin + 1, end - 1); } else { return 0; } } // Driver code public static void Main () { int []a = { 3, 6, 0, 6, 3 }; int n = a.Length; if (palindrome(a, 0, n - 1) == 1) Console.WriteLine( "Palindrome" ); else Console.WriteLine( "Not Palindrome" ); } } // This code is contributed by inder_verma |
PHP
<?php // PHP implementation of above approach // Recursive function that returns 1 // if palindrome, 0 if not palindrome function palindrome( $arr , $begin , $end ) { // base case if ( $begin >= $end ) { return 1; } if ( $arr [ $begin ] == $arr [ $end ]) { return palindrome( $arr , $begin + 1, $end - 1); } else { return 0; } } // Driver code $a = array ( 3, 6, 0, 6, 3 ); $n = count ( $a ); if (palindrome( $a , 0, $n - 1) == 1) echo "Palindrome" ; else echo "Not Palindrome" ; // This code is contributed // by inder_verma ?> |
Javascript
<script> // Javascript implementation of above approach // Recursive function that returns 1 if // palindrome, 0 if not palindrome function palindrome(arr, begin, end) { // base case if (begin >= end) { return 1; } if (arr[begin] == arr[end]) { return palindrome(arr, begin + 1, end - 1); } else { return 0; } } // Driver code let a = [ 3, 6, 0, 6, 3 ]; let n = a.length; if (palindrome(a, 0, n - 1) == 1) document.write( "Palindrome" ); else document.write( "Not Palindrome" ); // This code is contributed by divyeshrabadiya07. </script> |
Output:
Palindrome
Time complexity: O(N), where N is the size of the given array.
Auxiliary space: O(N), recursive stack space of size N will be required.