PDA

View Full Version : Need suggestions



GaPe
10-31-2002, 11:33 AM
Hi!

I have to find a programming problem that can be solved with iterative and recursion way (sorry for bad English :confused: ). So if you have an idea please post it.

Thanks.

Shiro
10-31-2002, 12:02 PM
Most, if not all, recursive functions can be made iterative by removing the recursion. For example the faculty function, this is usually given as a recursive definition:

n! = n * (n-1)!

When expanded it is:

n! = n * (n-1) * ... * 2 * 1

From this it can be seen that you could remove the recursion by introducing a variable i so that:

n! = P (i=1 to n) i

Where P is the product quantor.


So I'd suggest you take a recursive solution to a problem and make it iterative. Using Google to search for "examples of recursion" leads you to a lot of applications which make use of recursion. Like sorting, the towers of Hanoi, etc.

Davros
10-31-2002, 12:05 PM
k-approximation. A lovely little algorithm which is used for finding alternative spellings in spell checkers.

Here, I've done 99% of your home work for you:

http://cboard.cprogramming.com/showthread.php?threadid=27202

See the last post.

You would probably want to pull out the AnsiStrings & use char* instead. This would actually be much quicker & memory efficient, as currently it is actually creating a new string on the stack each time it recurses.