# Longest palindromic subsequence using recursion

Here given code implementation process.

``````/*
C program for
Longest palindromic subsequence using recursion
*/
#include <stdio.h>
#include <string.h>

// Returns the max value of given two numbers
int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
int findLPS(char *text, int start, int ends)
{
if (start == ends)
{
// When single character remains
return 1;
}
if (text[start] == text[ends] && start + 1 == ends)
{
// When two consecutive elements are same character
return 2;
}
if (text[start] == text[ends])
{
// Increase start value and reduce end value
// and find the recursively  lps
return findLPS(text, start + 1, ends - 1) + 2;
}
return maxValue(findLPS(text, start, ends - 1), findLPS(text, start + 1, ends));
}
int main(int argc, char
const *argv[])
{
char *text1 = "pewmoozdp";
char *text2 = "xbfdsafx";
// Test A
int n = strlen(text1);
// "poop" is resultant palindrome
// Length 4
int ans = findLPS(text1, 0, n - 1);
printf("\n Given  : %s ", text1);
printf("\n Result : %d", ans);
// Test B
n = strlen(text2);
// [xfsfx,xfdfx,xfafx] is resultant palindrome
// Length 5
ans = findLPS(text2, 0, n - 1);
printf("\n Given  : %s ", text2);
printf("\n Result : %d", ans);
return 0;
}``````

#### Output

`````` Given  : pewmoozdp
Result : 4
Given  : xbfdsafx
Result : 5``````
``````/*
Java program for
Longest palindromic subsequence using recursion
*/
public class LPS
{
// Returns the max value of given two numbers
public int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
public int findLPS(String text, int start, int ends)
{
if (start == ends)
{
// When single character remains
return 1;
}
if (text.charAt(start) == text.charAt(ends) && start + 1 == ends)
{
// When two consecutive elements are same character
return 2;
}
if (text.charAt(start) == text.charAt(ends))
{
// Increase start value and reduce end value
// and find the recursively lps
return findLPS(text, start + 1, ends - 1) + 2;
}
return maxValue(findLPS(text, start, ends - 1),
findLPS(text, start + 1, ends));
}
public static void main(String[] args)
{
String text1 = "pewmoozdp";
String text2 = "xbfdsafx";
// Test A
int n = text1.length();
// "poop" is resultant palindrome
// Length 4
int ans = task.findLPS(text1, 0, n - 1);
System.out.print("\n Given : " + text1 );
System.out.print("\n Result : " + ans);
// Test B
n = text2.length();
// [xfsfx,xfdfx,xfafx] is resultant palindrome
// Length 5
ans = task.findLPS(text2, 0, n - 1);
System.out.print("\n Given : " + text2 );
System.out.print("\n Result : " + ans );

}
}``````

#### Output

`````` Given : pewmoozdp
Result : 4
Given : xbfdsafx
Result : 5``````
``````// Include header file
#include <iostream>
#include <string>

using namespace std;
/*
C++ program for
Longest palindromic subsequence using recursion
*/
class LPS
{
public:
// Returns the max value of given two numbers
int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
int findLPS(string text, int start, int ends)
{
if (start == ends)
{
// When single character remains
return 1;
}
if (text[start] == text[ends] && start + 1 == ends)
{
// When two consecutive elements are same character
return 2;
}
if (text[start] == text[ends])
{
// Increase start value and reduce end value
// and find the recursively lps
return this->findLPS(text, start + 1, ends - 1) + 2;
}
return this->maxValue(this->findLPS(text, start, ends - 1), this->findLPS(text, start + 1, ends));
}
};
int main()
{
string text1 = "pewmoozdp";
string text2 = "xbfdsafx";
// Test A
int n = text1.length();
// "poop" is resultant palindrome
// Length 4
int ans = task->findLPS(text1, 0, n - 1);
cout << "\n Given : " << text1;
cout << "\n Result : " << ans;
// Test B
n = text2.length();
// [xfsfx,xfdfx,xfafx] is resultant palindrome
// Length 5
ans = task->findLPS(text2, 0, n - 1);
cout << "\n Given : " << text2;
cout << "\n Result : " << ans;
return 0;
}``````

#### Output

`````` Given : pewmoozdp
Result : 4
Given : xbfdsafx
Result : 5``````
``````// Include namespace system
using System;
/*
Csharp program for
Longest palindromic subsequence using recursion
*/
public class LPS
{
// Returns the max value of given two numbers
public int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
public int findLPS(String text, int start, int ends)
{
if (start == ends)
{
// When single character remains
return 1;
}
if (text[start] == text[ends] && start + 1 == ends)
{
// When two consecutive elements are same character
return 2;
}
if (text[start] == text[ends])
{
// Increase start value and reduce end value
// and find the recursively lps
return this.findLPS(text, start + 1, ends - 1) + 2;
}
return this.maxValue(this.findLPS(text, start, ends - 1), this.findLPS(text, start + 1, ends));
}
public static void Main(String[] args)
{
String text1 = "pewmoozdp";
String text2 = "xbfdsafx";
// Test A
int n = text1.Length;
// "poop" is resultant palindrome
// Length 4
int ans = task.findLPS(text1, 0, n - 1);
Console.Write("\n Given : " + text1);
Console.Write("\n Result : " + ans);
// Test B
n = text2.Length;
// [xfsfx,xfdfx,xfafx] is resultant palindrome
// Length 5
ans = task.findLPS(text2, 0, n - 1);
Console.Write("\n Given : " + text2);
Console.Write("\n Result : " + ans);
}
}``````

#### Output

`````` Given : pewmoozdp
Result : 4
Given : xbfdsafx
Result : 5``````
``````package main
import "fmt"
/*
Go program for
Longest palindromic subsequence using recursion
*/

// Returns the max value of given two numbers
func maxValue(a, b int) int {
if a > b {
return a
}
return b
}
func findLPS(text string, start int, ends int) int {
if start == ends {
// When single character remains
return 1
}
if text[start] == text[ends] && start + 1 == ends {
// When two consecutive elements are same character
return 2
}
if text[start] == text[ends] {
// Increase start value and reduce end value
// and find the recursively lps
return findLPS(text, start + 1, ends - 1) + 2
}
return maxValue(findLPS(text, start, ends - 1), findLPS(text, start + 1, ends))
}
func main() {

var text1 string = "pewmoozdp"
var text2 string = "xbfdsafx"
// Test A
var n int = len(text1)
// "poop" is resultant palindrome
// Length 4
var ans int = findLPS(text1, 0, n - 1)
fmt.Print("\n Given : ", text1)
fmt.Print("\n Result : ", ans)
// Test B
n = len(text2)
// [xfsfx,xfdfx,xfafx] is resultant palindrome
// Length 5
ans = findLPS(text2, 0, n - 1)
fmt.Print("\n Given : ", text2)
fmt.Print("\n Result : ", ans)
}``````

#### Output

`````` Given : pewmoozdp
Result : 4
Given : xbfdsafx
Result : 5``````
``````<?php
/*
Php program for
Longest palindromic subsequence using recursion
*/
class LPS
{
// Returns the max value of given two numbers
public	function maxValue(\$a, \$b)
{
if (\$a > \$b)
{
return \$a;
}
return \$b;
}
public	function findLPS(\$text, \$start, \$ends)
{
if (\$start == \$ends)
{
// When single character remains
return 1;
}
if (\$text[\$start] == \$text[\$ends] && \$start + 1 == \$ends)
{
// When two consecutive elements are same character
return 2;
}
if (\$text[\$start] == \$text[\$ends])
{
// Increase start value and reduce end value
// and find the recursively lps
return \$this->findLPS(\$text, \$start + 1, \$ends - 1) + 2;
}
return \$this->maxValue(\$this->findLPS(\$text, \$start, \$ends - 1),
\$this->findLPS(\$text, \$start + 1, \$ends));
}
}

function main()
{
\$text1 = "pewmoozdp";
\$text2 = "xbfdsafx";
// Test A
\$n = strlen(\$text1);
// "poop" is resultant palindrome
// Length 4
\$ans = \$task->findLPS(\$text1, 0, \$n - 1);
echo("\n Given : ".\$text1);
echo("\n Result : ".\$ans);
// Test B
\$n = strlen(\$text2);
// [xfsfx,xfdfx,xfafx] is resultant palindrome
// Length 5
\$ans = \$task->findLPS(\$text2, 0, \$n - 1);
echo("\n Given : ".\$text2);
echo("\n Result : ".\$ans);
}
main();``````

#### Output

`````` Given : pewmoozdp
Result : 4
Given : xbfdsafx
Result : 5``````
``````/*
Node JS program for
Longest palindromic subsequence using recursion
*/
class LPS
{
// Returns the max value of given two numbers
maxValue(a, b)
{
if (a > b)
{
return a;
}
return b;
}
findLPS(text, start, ends)
{
if (start == ends)
{
// When single character remains
return 1;
}
if (text.charAt(start) == text.charAt(ends) && start + 1 == ends)
{
// When two consecutive elements are same character
return 2;
}
if (text.charAt(start) == text.charAt(ends))
{
// Increase start value and reduce end value
// and find the recursively lps
return this.findLPS(text, start + 1, ends - 1) + 2;
}
return this.maxValue(this.findLPS(text, start, ends - 1),
this.findLPS(text, start + 1, ends));
}
}

function main()
{
var text1 = "pewmoozdp";
var text2 = "xbfdsafx";
// Test A
var n = text1.length;
// "poop" is resultant palindrome
// Length 4
var ans = task.findLPS(text1, 0, n - 1);
process.stdout.write("\n Given : " + text1);
process.stdout.write("\n Result : " + ans);
// Test B
n = text2.length;
// [xfsfx,xfdfx,xfafx] is resultant palindrome
// Length 5
ans = task.findLPS(text2, 0, n - 1);
process.stdout.write("\n Given : " + text2);
process.stdout.write("\n Result : " + ans);
}
main();``````

#### Output

`````` Given : pewmoozdp
Result : 4
Given : xbfdsafx
Result : 5``````
``````#    Python 3 program for
#    Longest palindromic subsequence using recursion
class LPS :
#  Returns the max value of given two numbers
def maxValue(self, a, b) :
if (a > b) :
return a
return b

def findLPS(self, text, start, ends) :
if (start == ends) :
#  When single character remains
return 1

if (text[start] == text[ends] and start + 1 == ends) :
#  When two consecutive elements are same character
return 2

if (text[start] == text[ends]) :
#  Increase start value and reduce end value
#  and find the recursively lps
return self.findLPS(text, start + 1, ends - 1) + 2

return self.maxValue(self.findLPS(text, start, ends - 1),
self.findLPS(text, start + 1, ends))

def main() :
text1 = "pewmoozdp"
text2 = "xbfdsafx"
#  Test A
n = len(text1)
#  "poop" is resultant palindrome
#  Length 4
ans = task.findLPS(text1, 0, n - 1)
print("\n Given : ", text1, end = "")
print("\n Result : ", ans, end = "")
#  Test B
n = len(text2)
#  [xfsfx,xfdfx,xfafx] is resultant palindrome
#  Length 5
ans = task.findLPS(text2, 0, n - 1)
print("\n Given : ", text2, end = "")
print("\n Result : ", ans, end = "")

if __name__ == "__main__": main()``````

#### Output

`````` Given :  pewmoozdp
Result :  4
Given :  xbfdsafx
Result :  5``````
``````#    Ruby program for
#    Longest palindromic subsequence using recursion
class LPS
#  Returns the max value of given two numbers
def maxValue(a, b)
if (a > b)
return a
end

return b
end

def findLPS(text, start, ends)
if (start == ends)
#  When single character remains
return 1
end

if (text[start] == text[ends] && start + 1 == ends)
#  When two consecutive elements are same character
return 2
end

if (text[start] == text[ends])
#  Increase start value and reduce end value
#  and find the recursively lps
return self.findLPS(text, start + 1, ends - 1) + 2
end

return self.maxValue(self.findLPS(text, start, ends - 1),
self.findLPS(text, start + 1, ends))
end

end

def main()
text1 = "pewmoozdp"
text2 = "xbfdsafx"
#  Test A
n = text1.length
#  "poop" is resultant palindrome
#  Length 4
ans = task.findLPS(text1, 0, n - 1)
print("\n Given : ", text1)
print("\n Result : ", ans)
#  Test B
n = text2.length
#  [xfsfx,xfdfx,xfafx] is resultant palindrome
#  Length 5
ans = task.findLPS(text2, 0, n - 1)
print("\n Given : ", text2)
print("\n Result : ", ans)
end

main()``````

#### Output

`````` Given : pewmoozdp
Result : 4
Given : xbfdsafx
Result : 5``````
``````/*
Scala program for
Longest palindromic subsequence using recursion
*/
class LPS()
{
// Returns the max value of given two numbers
def maxValue(a: Int, b: Int): Int = {
if (a > b)
{
return a;
}
return b;
}
def findLPS(text: String, start: Int, ends: Int): Int = {
if (start == ends)
{
// When single character remains
return 1;
}
if (text.charAt(start) == text.charAt(ends) && start + 1 == ends)
{
// When two consecutive elements are same character
return 2;
}
if (text.charAt(start) == text.charAt(ends))
{
// Increase start value and reduce end value
// and find the recursively lps
return findLPS(text, start + 1, ends - 1) + 2;
}
return maxValue(findLPS(text, start, ends - 1),
findLPS(text, start + 1, ends));
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: LPS = new LPS();
var text1: String = "pewmoozdp";
var text2: String = "xbfdsafx";
// Test A
var n: Int = text1.length();
// "poop" is resultant palindrome
// Length 4
var ans: Int = task.findLPS(text1, 0, n - 1);
print("\n Given : " + text1);
print("\n Result : " + ans);
// Test B
n = text2.length();
// [xfsfx,xfdfx,xfafx] is resultant palindrome
// Length 5
ans = task.findLPS(text2, 0, n - 1);
print("\n Given : " + text2);
print("\n Result : " + ans);
}
}``````

#### Output

`````` Given : pewmoozdp
Result : 4
Given : xbfdsafx
Result : 5``````
``````import Foundation;
/*
Swift 4 program for
Longest palindromic subsequence using recursion
*/
class LPS
{
// Returns the max value of given two numbers
func maxValue(_ a: Int, _ b: Int) -> Int
{
if (a > b)
{
return a;
}
return b;
}
func findLPS(_ text: [Character], _ start: Int, _ ends: Int) -> Int
{
if (start == ends)
{
// When single character remains
return 1;
}
if (text[start] == text[ends] && start + 1 == ends)
{
// When two consecutive elements are same character
return 2;
}
if (text[start] == text[ends])
{
// Increase start value and reduce end value
// and find the recursively lps
return self.findLPS(text, start + 1, ends - 1) + 2;
}
return self.maxValue(self.findLPS(text, start, ends - 1),
self.findLPS(text, start + 1, ends));
}
}
func main()
{
let text1: String = "pewmoozdp";
let text2: String = "xbfdsafx";
// Test A
var n: Int = text1.count;
// "poop" is resultant palindrome
// Length 4
var ans: Int = task.findLPS(Array(text1), 0, n - 1);
print("\n Given : ", text1, terminator: "");
print("\n Result : ", ans, terminator: "");
// Test B
n = text2.count;
// [xfsfx,xfdfx,xfafx] is resultant palindrome
// Length 5
ans = task.findLPS(Array(text2), 0, n - 1);
print("\n Given : ", text2, terminator: "");
print("\n Result : ", ans, terminator: "");
}
main();``````

#### Output

`````` Given :  pewmoozdp
Result :  4
Given :  xbfdsafx
Result :  5``````
``````/*
Kotlin program for
Longest palindromic subsequence using recursion
*/
class LPS
{
// Returns the max value of given two numbers
fun maxValue(a: Int, b: Int): Int
{
if (a > b)
{
return a;
}
return b;
}
fun findLPS(text: String, start: Int, ends: Int): Int
{
if (start == ends)
{
// When single character remains
return 1;
}
if (text.get(start) == text.get(ends) && start + 1 == ends)
{
// When two consecutive elements are same character
return 2;
}
if (text.get(start) == text.get(ends))
{
// Increase start value and reduce end value
// and find the recursively lps
return this.findLPS(text, start + 1, ends - 1) + 2;
}
return this.maxValue(this.findLPS(text, start, ends - 1), this.findLPS(text, start + 1, ends));
}
}
fun main(args: Array < String > ): Unit
{
val text1: String = "pewmoozdp";
val text2: String = "xbfdsafx";
// Test A
var n: Int = text1.length;
// "poop" is resultant palindrome
// Length 4
var ans: Int = task.findLPS(text1, 0, n - 1);
print("\n Given : " + text1);
print("\n Result : " + ans);
// Test B
n = text2.length;
// [xfsfx,xfdfx,xfafx] is resultant palindrome
// Length 5
ans = task.findLPS(text2, 0, n - 1);
print("\n Given : " + text2);
print("\n Result : " + ans);
}``````

#### Output

`````` Given : pewmoozdp
Result : 4
Given : xbfdsafx
Result : 5``````

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.