Click here to Skip to main content
14,332,426 members
Rate this:
Please Sign up or sign in to vote.
Hey, I built a working recursive function that finds the Longest Common Sequence between two strings.
http://en.wikipedia.org/wiki/Longest_common_subsequence_problem[^]
It works perfectly fine and it is fast cause I use a memiozation table so that I'm not calling something that I've previously called already. My problem lies that when I have strings over 150 characters, I get a call stack overflow. I was wondering if anyone knows of a good suggestion to fixing this or of a better way of finding the longest common subsequence.
Posted

1 solution

Rate this:
Please Sign up or sign in to vote.

Solution 1

Hi,
stack overflow happens when your computer's stack gets too many function calls, thus strings over 150 chars generate such error. There are several workarounds that you can use in order to solve this problem:
1) optimize your code to get fewer function calls
2) use Stack object in order to simulate recursive calls, by memorizing variable states
3) the best one - think of an algorithm that is not recursive. Its a common interview question, to find a solution without the use of recursion. There is an entire article devoted to the problem of Longest Common Sequence here[^] at codeproject. But before looking at it, I suggest you to try finding the non-recursive solution by your own.
Regards
   
v2
Comments
Manfred Rudolf Bihy 7-Jun-11 12:17pm
   
I agree with most of what you said thus my 5.
I don't think that strings would do anything to the stack though. Since a string is immutable it is always passed by reference. Even using out modifier wont change anything about that since only the reference to a new string will be passed back it the passed in string was modified.

Cheers!
   
Manfred, you're absolutely right!
In practice, this exception is a result of infinite recursion, much less of too long recursion.
--SA
Ciumac Sergiu 7-Jun-11 13:09pm
   
Thanks, a small remark here: I've meant that the idea behind a long string is not related to memory consumption, but rather to the big number of sequential method calls that one needs to perform while calculating the longest sub-string (recursively it is an expensive operation). I'm mostly sure that in the written algorithm the number of method invocations is O(n*n) dependent upon the length of the string, thus once you select 2 big strings for analysis you get your stack overflowed. Its not that the stack is fulfilled because of the memory that a string occupies, but because of the # of method calls it requires to solve the problem.
Regards
   
Oh, that's a different story. Depending on algorithm, it could be right.
Will you add this note to your answer, of just a reference to your comment?
--SA
MJ_ 7-Jun-11 13:12pm
   
Alright. So I'll have a while loop that also has a stack. On the stack I'll push the currant configuration of the function until the stack is empty. Sounds good. (Unless in 3. you meant think of a method that doesn't involve implementing a recursive function by using a while loop and stack. Then I'll have to rethink everything.)
Ciumac Sergiu 7-Jun-11 13:19pm
   
"So I'll have a while loop that also has a stack" - exactly, this is the classical way of simulating the recursion. Its not so fast in terms of speed of processing, but it's very reliable if the solution is scaled for big inputs.
   
So, after some thinking, I voted 5.
--SA

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100