Archived

This topic is now archived and is closed to further replies.

nws_mrman

recursive algorithm vs. iterative algoritm

Recommended Posts

Guest Anonymous Poster
stop cheating Nick
france are going to win the world cup

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
iterative code is more efficient and more "human readeble", recurcive code is more elegant but it consumes more memory and cpu power.

Share this post


Link to post
Share on other sites
Not sure what your''re asking.

Anyway, a recursive function is a function which calls itself. Ierative is, for example, using a while loop.

quote:

iterative code is more efficient and more "human readeble", recurcive code is more elegant but it consumes more memory and cpu power.



Not as simple as that...

True, recursive functions are bad for the stack. If you limit the number of function parameters though, you should be able to recurse 1000''s of time. Of course... checking if you are running out of stackspace is mandatory.

When it comes to performance it really depends on the problem you are trying to solve. Sometimes a recursive algorithm is faster than the iterative one. Further more, some problems are a pain in the ass to solve iteratively, but a breeze to solve recursivly.

Share this post


Link to post
Share on other sites
A lot of problems are recursive in nature anyway, so the iterative algorithm just ends up emulating recursion.

Once there was a time when all people believed in God and the church ruled. This time is called the Dark Ages.

Share this post


Link to post
Share on other sites
quote:
Original post by Arild Fines
A lot of problems are recursive in nature anyway, so the iterative algorithm just ends up emulating recursion.



But all recursive programs can be solved iteratively as well.

I thought recursion was very difficult when I first started programming. It is a topic that is way harder than pointers, in my opinion. I don''t think it is too bad anymore, and in fact, I feel a sense of satisfaction when I think of a recursive solution on my own.

To the original poster: recursion is very useful when you want to remember the state of a certain situation. Take the map coloring problem, which can take a 2D map and fill in all the "countries" so that no country has the same color as an adjacent country. The recursive solution to this problem is very intuitive (although it is essentially brute force and I am sure there is a more efficient way).

Share this post


Link to post
Share on other sites
Thanks for the help.
The reason i asked what the difference between an iterative algorithm and a recursive algorithm was because for one of the tasks in my school work the question was:

"Rewrite the following recursive algorithm as an iterative algorithm..."

FUNCTION Recurse(N:Integer):Integer;
IF N = 1 THEN
Output 1,1
Recurse = 1
ELSE
Output N and N*(N+1)/2
Recurse = N*(N+1)/2+Recurse(N-1)
END IF
END Recurse


So i have come up with my answer:

WHILE N > 1
Output N and N*(N+1)/2
number = number + (N*(N+1)/2)
N = N - 1
END WHILE
IF N = 1
Output 1,1
number = number + 1
END IF


I have tested it and it outputs the same numbers as the recurse example but i dont know if what i have written is an iterative algorithm. I dont want the correct answer if my answer is wrong, but can anyone just help by telling me if i have answered the question right.
Thanks

Share this post


Link to post
Share on other sites