Recursive function overflow

Question

0.00/5 (No votes)

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 7-Jun-11 5:47am

MJ_

Add a Solution

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

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

Ciumac Sergiu · Accepted Answer · 2011-06-07T05:53:00

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

Posted 7-Jun-11 5:53am

Ciumac Sergiu

Updated 7-Jun-11 5:57am

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

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.

Sergey Alexandrovich Kryukov 7-Jun-11 15:10pm

So, after some thinking, I voted 5.
--SA