15,902,939 members
See more:
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

## 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
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.
--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.)