Click here to Skip to main content
15,902,939 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
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

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
 
Share this answer
 
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!
Sergey Alexandrovich Kryukov 7-Jun-11 15:08pm    
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
Sergey Alexandrovich Kryukov 7-Jun-11 15:10pm    
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.)

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



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900