European Experts Exchange (EEE.org) :: Free Experts PHP MySql Oracle Microsoft Web SQL Delphi


Languages :: Pascal :: recusive vs iterrative loops
By: patsysimon	Date: 20/04/2003 00:00:00	Points: 50	Status: Answered Quality : Excellent
I've done the fibonnaci series using a recursive structure and I need to know how to do it using aloop. Could you explain the disadvantages and advantages of each. program recursive; var Fib, A : integer; Function Fibonnaci(N: integer): integer; begin if (N = 1) or (N = 2) then Fibonnaci := 1 else Fibonnaci :=Fibonnaci(N-2) + Fibonnaci(N-1); End; Begin readln(A); Fib := Fibonnaci (A); write('The ',A,'th Fibonnaci number is: '); writeln(fib); readln; END.
By: mlmcc	Date: 20/04/2003 10:09:00		Type : Comment
The disadvantage of using recursion is the number of times you call fib. example Fib(5) Calls Fib(4) Fib(3) Fin(2) Fib(1) Fib(2) Fib(3) Fib(2) Fib(1) Notice Fib(2) is called 3 times, Fib(1) and Fib(3) called twice Advantage - you can calculate Fib(N) relatively directly. Loop example Calculates each Fib(x) once up to Fin(N) Public Function Fibanoci(N as integer) as Integer Dim Fib(25) as Integer Fib(1) = 1 Fib(2) = 2 for i = 3 to N Fib(i) = Fib(i-1) + Fib(i-2) next i end Function Advantage - Faster, fewer calls (less stack space used) In actuality, though Fibinoci numbers are defined recursively, it really isn't a recursive algortihm. Consider powers. x^n = if n=0 then 1 else x * x^(n-1) mlmcc

By: VGR	Date: 20/04/2003 16:19:00		Type : Answer
agree with mlmcc *Sometimes, an algorithm can be "de-recursified",but not always. IMHO, advantages/disdvantages of the recursion are : -more concise code -self-sustained code (everything is either parameter or local) -more elegant code (because of the two above) -uses the stack, so encounters an OS limit once in a while (Turbo-Pascal used to return a runtime error for this ; I guess this can now be trapped as an Exception in Delphi) -proves superior thinking (IMHO :D ) Transforming it to an iterative algorithm : -clumsier -longer -more memory greedy -less stack greedy I really think the "cost" of an iteration's handling of arrays and counter data largely compensates the "cost" of recursive function calls, but this is algorithm-dependent IMHO also, a recursive algorithm may* be faster than its iterative brother. At least, it's faster (more natural) to write :D

By: patsysimon	Date: 25/04/2003 03:39:00		Type : Comment
Here the question maybe you can give me a clearer picture.'discuss the following proposition :'Recursion is a good approach to solving certain kinds of problems in computing, and a bad approach for solving other kinds.' Provide an example for each case.(past paper question that seem to recur every year.)

By: VGR	Date: 25/04/2003 06:07:00		Type : Comment
not exactly. And not for "problems in computing" "computing" solves the problems of physics, maths, engineering, astronomy, accountancy, etc "computing" is a tool, not a goal in itself. It has its own problems, but they don't solve by programming :D I would say that "naturally recursive" problems deserve naturally a recursive approach (like the factorial), even if they may be more efficiently computed by "derecursifying" the algorithm (again, the factorial) And that "other problems" can't usually be efficiently/cleanly be trated as a recursive algorithm. An other example of naturally recursive algorithms are : -getting all sub-dirs and files of a given parent directory -finding all children of all children etc of a given person in a genealogy tree -parsing a logical expression (parentheses, OR, AND, NOT, XOR)

By: patsysimon	Date: 25/04/2003 08:28:00		Type : Comment
could someone else help me VGR is confusing the hell out of me.Can't we use recursion or iterative loops to solve mathematical probems such as Factorial, Fibonnacci series, power functions etc..etc? Computing is it? Thus recursion or iterative loops can be used to (compute) solves the problems of maths.

By: VGR	Date: 25/04/2003 09:00:00		Type : Comment
For the first part that confuses you,let's say we don't express ourselves at the same level. My view is more philosophical and yours is more pragmatic. For the second part, I told you all I thought was correct. -intrinsic recursive problems do exist, they have natural recursive algorithms, and *sometimes* may be de-recursified (but it's always ugly :D ) -other problems are usually not "recursifiables", or at the price of contorsions Houdini would not have rejected as his.

Do register to be able to answer

Add This Article To:
Del.icio.us	Digg	Google	Spurl
Blink	Wong	Simpy	Y! MyWeb

Contact

page generated in 42.958020 milliseconds

Why Google AdSense ads ?

New Improved Search!