Lines 43
##### Keywords
algorithm (8) C++ (2) LCS (2)
##### Permissions
Owner: Michael Case
Viewable by Everyone
Editable by Michael Case
Siafoo is here to make coding less frustrating and to save you time.

# recursive solution for LCS problem 0

 In Brief This recursive routine costs a lot and you can see clearly that the cost will be high in terms of repeated comparisons and memory consumption.
 Language C++
# 's
` 1#include <iostream> 2#include <string> 3#include <cstdlib> 4 5int lcs( const std::string& s1, const std::string& s2, std::string& result ) { 6	int retval(0); 7	if ( s2.size() > 1 && s1.size() > 1 ) { 8		if ( s1[0] == s2[0] ) { 9			std::string ret1;10			retval = 1 + lcs(s1.substr(1, s1.size()-1), s2.substr(1,s2.size()-1),ret1);11			result += s1[0] + ret1;12		} else {13			++i;14			std::string ret1, ret2;15			retval = std::max(lcs(s1.substr(1, s1.size()-1), s2,ret1), lcs(s1, s2.substr(1,s2.size()-1),ret2));16			//std::cout << "ret1 and ret2: " << ret1 << " " << ret2 << std::endl;17			if (ret1.size() > ret2.size()) result += ret1;18			else result += ret2;19		}20	} else if ( s1.size() && s2.size() && s1[0] == s2[0] ) {21		result += s1[0];22		retval = 1;23	}24	return retval;25}2627int main (int argc, char * const argv[]) {28	std::cout << "The purpose is to find the longest and NOT all of the "29	"actual subsequences.  This algorithm is a brute force algorithm to "30	"demonstrate finding the longest common subsequence." << std::endl31	<< std::endl32	<< "First we proceed by going through X compared to Y and then "33	"going through comparing Y to X.  In either case we get 'a' not 'the' "34	"longest subsequence." << std::endl << std::endl;35	std::string x="ABCDBAGZCDCA";36	std::string y="BCADCGZ";37	std::string result;38	std::cout << lcs(x,y,result) << std::endl;39	std::cout << result << std::endl;40	result.clear();41	std::cout << lcs(y,x,result) << std::endl;42	std::cout << result << std::endl;43	44    return 0;45}`

This recursive routine costs a lot and you can see clearly that the cost will be high in terms of repeated comparisons and memory consumption.