用于检查字符串是否为回文的递归函数-yiteyi-C++库

给定一个字符串，编写一个递归函数，检查给定字符串是否为回文，否则为非回文。

null

例如：

Input : malayalamOutput : YesReverse of malayalam is alsomalayalam.Input : maxOutput : NoReverse of max is not max.

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

我们讨论了一个迭代函数在这里 . 递归函数的概念很简单：

1) If there is only one character in string   return true.2) Else compare first and last characters   and recur for remaining substring.

以下是上述理念的实施情况：

C++

                         // A recursive C++ program to                       
                         // check whether a given number                       
                         // is palindrome or not                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // A recursive function that                       
                         // check a str[s..e] is                       
                         // palindrome or not.                       
                         bool                                     isPalRec(                                     char                                     str[],                       
                                                 int                                     s,                                     int                                     e)                       
                         {                       
                                   
                                                 // If there is only one character                       
                                                 if                                     (s == e)                       
                                                 return                                     true                                     ;                       
           
                                                 // If first and last                       
                                                 // characters do not match                       
                                                 if                                     (str[s] != str[e])                       
                                                 return                                     false                                     ;                       
           
                                                 // If there are more than                       
                                                 // two characters, check if                       
                                                 // middle substring is also                       
                                                 // palindrome or not.                       
                                                 if                                     (s < e + 1)                       
                                                 return                                     isPalRec(str, s + 1, e - 1);                       
           
                                                 return                                     true                                     ;                       
                         }                       
           
                         bool                                     isPalindrome(                                     char                                     str[])                       
                         {                       
                                                 int                                     n =                                     strlen                                     (str);                       
                                   
                                                 // An empty string is                       
                                                 // considered as palindrome                       
                                                 if                                     (n == 0)                       
                                                 return                                     true                                     ;                       
                                   
                                                 return                                     isPalRec(str, 0, n - 1);                       
                         }                       
           
                         // Driver Code                       
                         int                                     main()                       
                         {                       
                                                 char                                     str[] =                                     "geeg"                                     ;                       
           
                                                 if                                     (isPalindrome(str))                       
                                                 cout <<                                     "Yes"                                     ;                       
                                                 else                       
                                                 cout <<                                     "No"                                     ;                       
           
                                                 return                                     0;                       
                         }                       
           
                         // This code is contributed by shivanisinghss2110                       

C

                         // A recursive C program to                       
                         // check whether a given number                       
                         // is palindrome or not                       
                         #include <stdio.h>                       
                         #include <string.h>                       
                         #include <stdbool.h>                       
           
                         // A recursive function that                       
                         // check a str[s..e] is                       
                         // palindrome or not.                       
                         bool                                     isPalRec(                                     char                                     str[],                       
                                                 int                                     s,                                     int                                     e)                       
                         {                       
                                                 // If there is only one character                       
                                                 if                                     (s == e)                       
                                                 return                                     true                                     ;                       
           
                                                 // If first and last                       
                                                 // characters do not match                       
                                                 if                                     (str[s] != str[e])                       
                                                 return                                     false                                     ;                       
           
                                                 // If there are more than                       
                                                 // two characters, check if                       
                                                 // middle substring is also                       
                                                 // palindrome or not.                       
                                                 if                                     (s < e + 1)                       
                                                 return                                     isPalRec(str, s + 1, e - 1);                       
           
                                                 return                                     true                                     ;                       
                         }                       
           
                         bool                                     isPalindrome(                                     char                                     str[])                       
                         {                       
                         int                                     n =                                     strlen                                     (str);                       
           
                         // An empty string is                       
                         // considered as palindrome                       
                         if                                     (n == 0)                       
                                                 return                                     true                                     ;                       
           
                         return                                     isPalRec(str, 0, n - 1);                       
                         }                       
           
                         // Driver Code                       
                         int                                     main()                       
                         {                       
                                                 char                                     str[] =                                     "geeg"                                     ;                       
           
                                                 if                                     (isPalindrome(str))                       
                                                 printf                                     (                                     "Yes"                                     );                       
                                                 else                       
                                                 printf                                     (                                     "No"                                     );                       
           
                                                 return                                     0;                       
                         }                       

JAVA

                         // A recursive JAVA program to                       
                         // check whether a given String                       
                         // is palindrome or not                       
                         import                                     java.io.*;                       
           
                         class                                     GFG                       
                         {                       
                                                 // A recursive function that                       
                                                 // check a str(s..e) is                       
                                                 // palindrome or not.                       
                                                 static                                     boolean                                     isPalRec(String str,                       
                                                 int                                     s,                                     int                                     e)                       
                                                 {                       
                                                 // If there is only one character                       
                                                 if                                     (s == e)                       
                                                 return                                     true                                     ;                       
           
                                                 // If first and last                       
                                                 // characters do not match                       
                                                 if                                     ((str.charAt(s)) != (str.charAt(e)))                       
                                                 return                                     false                                     ;                       
           
                                                 // If there are more than                       
                                                 // two characters, check if                       
                                                 // middle substring is also                       
                                                 // palindrome or not.                       
                                                 if                                     (s < e +                                     1                                     )                       
                                                 return                                     isPalRec(str, s +                                     1                                     , e -                                     1                                     );                       
           
                                                 return                                     true                                     ;                       
                                                 }                       
           
                                                 static                                     boolean                                     isPalindrome(String str)                       
                                                 {                       
                                                 int                                     n = str.length();                       
           
                                                 // An empty string is                       
                                                 // considered as palindrome                       
                                                 if                                     (n ==                                     0                                     )                       
                                                 return                                     true                                     ;                       
           
                                                 return                                     isPalRec(str,                                     0                                     , n -                                     1                                     );                       
                                                 }                       
           
                                                 // Driver Code                       
                                                 public                                     static                                     void                                     main(String args[])                       
                                                 {                       
                                                 String str =                                     "geeg"                                     ;                       
           
                                                 if                                     (isPalindrome(str))                       
                                                 System.out.println(                                     "Yes"                                     );                       
                                                 else                       
                                                 System.out.println(                                     "No"                                     );                       
                                                 }                       
                         }                       
           
                         // This code is contributed                       
                         // by Nikita Tiwari                       

python

                         # A recursive Python program                       
                         # to check whether a given                       
                         # number is palindrome or not                       
           
                         # A recursive function that                       
                         # check a str[s..e] is                       
                         # palindrome or not.                       
                         def                                     isPalRec(st, s, e) :                       
                                   
                                                 # If there is only one character                       
                                                 if                                     (s                                     =                                     =                                     e):                       
                                                 return                                     True                       
           
                                                 # If first and last                       
                                                 # characters do not match                       
                                                 if                                     (st[s] !                                     =                                     st[e]) :                       
                                                 return                                     False                       
           
                                                 # If there are more than                       
                                                 # two characters, check if                       
                                                 # middle substring is also                       
                                                 # palindrome or not.                       
                                                 if                                     (s < e                                     +                                     1                                     ) :                       
                                                 return                                     isPalRec(st, s                                     +                                     1                                     , e                                     -                                     1                                     );                       
           
                                                 return                                     True                       
           
                         def                                     isPalindrome(st) :                       
                                                 n                                     =                                     len                                     (st)                       
                                   
                                                 # An empty string is                       
                                                 # considered as palindrome                       
                                                 if                                     (n                                     =                                     =                                     0                                     ) :                       
                                                 return                                     True                       
                                   
                                                 return                                     isPalRec(st,                                     0                                     , n                                     -                                     1                                     );                       
           
           
                         # Driver Code                       
                         st                                     =                                     "geeg"                       
                         if                                     (isPalindrome(st)) :                       
                                                 print                                     "Yes"                       
                         else                                     :                       
                                                 print                                     "No"                       
                                   
                         # This code is contributed                       
                         # by Nikita Tiwari.                       

C#

                         // A recursive C# program to                       
                         // check whether a given number                       
                         // is palindrome or not                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
           
                                                 // A recursive function that                       
                                                 // check a str(s..e)                       
                                                 // is palindrome or not.                       
                                                 static                                     bool                                     isPalRec(String str,                       
                                                 int                                     s,                       
                                                 int                                     e)                       
                                                 {                       
                                   
                                                 // If there is only one character                       
                                                 if                                     (s == e)                       
                                                 return                                     true                                     ;                       
           
                                                 // If first and last character                       
                                                 // do not match                       
                                                 if                                     ((str[s]) != (str[e]))                       
                                                 return                                     false                                     ;                       
           
                                                 // If there are more than two                       
                                                 // characters, check if middle                       
                                                 // substring is also                       
                                                 // palindrome or not.                       
                                                 if                                     (s < e + 1)                       
                                                 return                                     isPalRec(str, s + 1,                       
                                                 e - 1);                       
                                                 return                                     true                                     ;                       
                                                 }                       
           
                                                 static                                     bool                                     isPalindrome(String str)                       
                                                 {                       
                                                 int                                     n = str.Length;                       
           
                                                 // An empty string is considered                       
                                                 // as palindrome                       
                                                 if                                     (n == 0)                       
                                                 return                                     true                                     ;                       
           
                                                 return                                     isPalRec(str, 0, n - 1);                       
                                                 }                       
           
                                                 // Driver Code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 String str =                                     "geeg"                                     ;                       
           
                                                 if                                     (isPalindrome(str))                       
                                                 Console.Write(                                     "Yes"                                     );                       
                                                 else                       
                                                 Console.Write(                                     "No"                                     );                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Nitin Mittal.                       

PHP

                         <?php                       
                         // A recursive php program to                       
                         // check whether a given number                       
                         // is palindrome or not                       
           
           
                         // A recursive function that                       
                         // check a str[s..e] is                       
                         // palindrome or not.                       
                         function                                     isPalRec(                                     $str                                     ,                                     $s                                     ,                                     $e                                     )                       
                         {                       
                                                 // If there is only one character                       
                                                 if                                     (                                     $s                                     ==                                     $e                                     )                       
                                                 return                                     true;                       
           
                                                 // If first and last                       
                                                 // characters do not match                       
                                                 if                                     (                                     $str                                     [                                     $s                                     ] !=                                     $str                                     [                                     $e                                     ])                       
                                                 return                                     false;                       
           
                                                 // If there are more than two                       
                                                 // characters, check if middle                       
                                                 // substring is also palindrome or not.                       
                                                 if                                     (                                     $s                                     <                                     $e                                     + 1)                       
                                                 return                                     isPalRec(                                     $str                                     ,                                     $s                                     + 1,                                     $e                                     - 1);                       
           
                                                 return                                     true;                       
                         }                       
           
                         function                                     isPalindrome(                                     $str                                     )                       
                         {                       
                         $n                                     =                                     strlen                                     (                                     $str                                     );                       
           
                         // An empty string is                       
                         // considered as palindrome                       
                         if                                     (                                     $n                                     == 0)                       
                                                 return                                     true;                       
           
                         return                                     isPalRec(                                     $str                                     , 0,                                     $n                                     - 1);                       
                         }                       
           
                         // Driver Code                       
                         {                       
                                                 $str                                     =                                     "geeg"                                     ;                       
           
                                                 if                                     (isPalindrome(                                     $str                                     ))                       
                                                 echo                                     (                                     "Yes"                                     );                       
                                                 else                       
                                                 echo                                     (                                     "No"                                     );                       
           
                                                 return                                     0;                       
                         }                       
           
                         // This code is contributed                       
                         // by nitin mittal.                       
                         ?>                       

Javascript

                         <script>                       
                                                 // A recursive javascript program to                       
                                                 // check whether a given String                       
                                                 // is palindrome or not                       
                                                 // A recursive function that                       
                                                 // check a str(s..e) is                       
                                                 // palindrome or not.                       
                                                 function                                     isPalRec( str , s , e) {                       
                                                 // If there is only one character                       
                                                 if                                     (s == e)                       
                                                 return                                     true                                     ;                       
           
                                                 // If first and last                       
                                                 // characters do not match                       
                                                 if                                     ((str.charAt(s)) != (str.charAt(e)))                       
                                                 return                                     false                                     ;                       
           
                                                 // If there are more than                       
                                                 // two characters, check if                       
                                                 // middle substring is also                       
                                                 // palindrome or not.                       
                                                 if                                     (s < e + 1)                       
                                                 return                                     isPalRec(str, s + 1, e - 1);                       
           
                                                 return                                     true                                     ;                       
                                                 }                       
           
                                                 function                                     isPalindrome( str) {                       
                                                 var                                     n = str.length;                       
           
                                                 // An empty string is                       
                                                 // considered as palindrome                       
                                                 if                                     (n == 0)                       
                                                 return                                     true                                     ;                       
           
                                                 return                                     isPalRec(str, 0, n - 1);                       
                                                 }                       
           
                                                 // Driver Code                       
                                   
                                                 var                                     str =                                     "geeg"                                     ;                       
           
                                                 if                                     (isPalindrome(str))                       
                                                 document.write(                                     "Yes"                                     );                       
                                                 else                       
                                                 document.write(                                     "No"                                     );                       
           
                         // This code contributed by gauravrajput1                       
                         </script>                       

输出

Yes

另一种方法：

基本上在遍历时检查第i个和第n-i-1个索引是否相等。

如果不存在equal return false，如果它们相等，则继续递归调用。

C++

                         #include <iostream>                       
                         using                                     namespace                                     std;                       
           
                         bool                                     isPalindrome(string s,                                     int                                     i){                       
                                   
                                                 if                                     (i > s.size()/2){                       
                                                 return                                     true                                     ;                       
                                                 }                       
                                   
                                                 return                                     s[i] == s[s.size()-i-1] && isPalindrome(s, i+1) ;                       
                                   
                         }                       
                                   
                                   
                         int                                     main()                       
                         {                       
                                                 string str =                                     "geeg"                                     ;                       
                                                 if                                     (isPalindrome(str, 0))                       
                                                 cout <<                                     "Yes"                                     ;                       
                                                 else                       
                                                 cout <<                                     "No"                                     ;                       
           
                                                 return                                     0;                       
           
                         }                       

输出

Yes

时间复杂性： O（n）

辅助空间： O（n）

本文由 萨希尔·拉吉普特 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章