Register to reply 
Recursive vs iterative approach 
Share this thread: 
#1
Nov212, 01:15 PM

P: 283

Maybe this question better belongs to programming section but I feel it has mathematics related doubt.
I want an intuition on how iterative and recursive approaches are different. Just look at the simple arithmetic progression. n^{th} term is given as a + n.d. This can be derived using both iterative and recursive methods. I am looking for the basic idea behind both the approaches. Also can all recursive solution be converted to iterative solution? In Fibonacci sequence can n^{th} term be found iteratively? So if all iteraitve and recursive solutions be interconvertible whats the basic difference between both, i mean the basic crux or logic behind both? Ah, I still feel I couldn't convey my question! 


#2
Nov212, 02:46 PM

P: 784

I can try to answer.
Basically a recursive algorithm calculates a number then uses the number it just calculated to calculate the next number, and so on. An iterative algorithm is a algorithm which 'calls' itself at some point in it's progression. The fibonacci sequence is a really good example of this. You can write functions (I'm assuming you know some basic programming  stop me if I'm off) that calculate terms in the Fibonacci sequence, store those terms as variables, and use that variable to compute the next term; this is a recursive approach. You can also write a function which seems to be doing the same thing but instead of storing a number as a variable the function calls itself. Meaning at some line in a int Function() you would have a call to int Function(), a.k.a a call to itself. This creates a nested function within a function that can be evaluated to produce terms in the Fibonacci sequence. This is an iterative approach. I have to run or else I would show the code in both these cases. If no one else has answered your question better later I can edit in some stuff. 


#3
Nov212, 04:28 PM

HW Helper
P: 7,047

wiki_recursion_cs.htm A recursive approach can be converted into an iterative approach by using an array to replace the functionality of the stack. In some cases, there may be an naturally iterative approach that can be used instead of a recursive approach. An iterative approach can be converted into a recursive approach by passing all the loop related variables as parameters to a self called function, but this is usually inefficient. 


#4
Nov212, 04:36 PM

P: 5,462

Recursive vs iterative approach
My trusty maths dictionary (this is the maths forum, not the programming one) says that they mean the same thing.



#5
Nov212, 04:43 PM

P: 784

Ah! I apologize, I mixed up the terms. Idiotic on my part, sorry OP.
My C++ book literally starts the chapter on recursion with "A recursive function in C++ is a function that calls itself." Should have checked before I posted. Sorry :) 


#6
Nov212, 04:47 PM

HW Helper
P: 7,047

http://en.wikipedia.org/wiki/Iteration http://en.wikipedia.org/wiki/Recursion For computer science (programming), the terms have different meanings as explained above: iteration means looping, recursion means a function that calls itself. Example of converting a recursive approach to an interative approach. iterative_recursion.htm fibonacci_iterative.htm 


#7
Nov212, 08:46 PM

Homework
Sci Advisor
HW Helper
Thanks
P: 9,656

In software, the difference is essentially that they work from opposite ends. In iteration, you start with an almost trivial case and solve it; then using that you can solve the next case. In recursion, you start from the endpoint and reason that you could solve that if you knew the answer to the next simpler case  so you go off and solve that then return to complete the job.
The advantage of recursion is elegance. Take the towers of Hanoi problem. It's easy to see that a solution is: To move the top N discs from tower A to tower B  move the top N1 from tower A to tower C  move the top disc from A to B  move the top N1 from C to B Once you've observed that is a solution, it's quite easy to restructure it as iteration, but either way it takes 2^N steps. Fibonacci, OTOH, demonstrates a serious disadvantage of recursion. The number of steps required is again exponential (equal roughly to the value that will be computed). But the iterative solution only takes N steps. Another disadvantage of recursion is stack size, which can be hard to anticipate. In theoretical computing and some related fields, recursive definitions arise. E.g. in the definition of a statement in a given computer language. Not sure how you'd replace those with a form of iteration. In consequence, the compiler likely analyses the program recursively, but I couldn't swear to that. In mathematical induction, I don't see a distinction. You have the inductive step and the base case, but whether you think of the proof as running backwards to or forwards from the base case is a matter of taste. There is a trap using recursion in mathematical definitions. If you attempt to use the definition to assess whether an object satisfies it, you could find yourself in infinite regress. You need some way of ensuring that the recursive analysis terminates for any given object  otherwise the definition is broken. 


#8
Nov412, 01:13 AM

P: 685

I recommend looking at the factorial function. It can both be implemented iteratively and recursively.
As already mentioned iteration involves using for loops. The recursive approach uses a function that calls itself. This sounds a little strange but let's have a look at how 3! is calculated: 1. iteration: Simply calculate 1*2*3
2. recursion: The recursive function is defined as:
f(3) = 3*f(31) = 3*f(2) What is f(2)? f(2) = 2*f(21) = 2*f(1) What is f(1)? f(1) = 1, according to definition Let's write everything in succession: f(3) = 3*f(2) = 3*(2*f(1)) = 3*(2*(1)) 


#9
Nov512, 04:15 AM

P: 5,462

These comments are true if you actually (intend to) carry out all the steps.
It is often possible, however, to develop a formula for the nth term without this effort. 


#10
Nov512, 06:46 AM

Engineering
Sci Advisor
HW Helper
Thanks
P: 6,959

f(10) = f(9) + f(8) ... (*) So you start by calculating f(9) f(9) = f(8) + f(7), etc But after you have done that, you already know the value of f(8) to finish calculating Eq. (*), so you don't need to calculate f(8) again. This is a very powerful idea in situations where you can't easily analyze the complete algorithm in advance to figure out what you need to calculate. An example would be a chess program looking at possible future moves, There are often many different ways of getting to the same position on the board, but the "history" of how you got there is irrelevant to how good the position is. (OK, that's a slight simplification of the real rules of chess, to simplfy the example!) 


#11
Nov512, 05:43 PM

HW Helper
P: 7,047

   Perhaps a better example for using recursion would be navigation of a tree like structure, such as the files and folders in a partition. Assume the goal is to process all files in the current directory first, then to recursively process all subdirectories in the current directory. There are two main loops, one to process files, the other to process subdirectories. Iteration would be awkward since the recursion returns back into the middle of the second loop. The code would look something like this:



#12
Nov612, 02:33 AM

P: 45

You can use recurrence relations for recursion.



#13
Nov612, 03:14 AM

P: 283

Why is recursion sometimes easier that iteration. Programs like nqueens and knights tour are easy using recursion but I struggle making them using iteration.
So what advantage does recursion offer in such cases. Why its easier to think recursive in some cases? 


#14
Nov612, 06:03 AM

Mentor
P: 15,067

With C++ you can also use templates to get an O(1) runtime solution:



#15
Nov612, 04:57 PM

HW Helper
P: 7,047




#16
Nov712, 01:20 PM

Mentor
P: 15,067

Here's one more recursive implementation of the Fibonacci algorithm. Note this is not tail recursive.



#17
Nov712, 01:40 PM

HW Helper
P: 7,047

I think the directory / nodal tree scan example from my earlier post is a better case for using recursion than fibonacci. Fibonacci can be easily implemented iteratively, but the two loop (1st loop for files / leaves, 2nd loop for subdirectories / subnodes) directory / tree scan, is awkward to implement iteratively, depending on the language (in C, it requires a goto to jump into the middle of the 2nd loop when the end of the current directory / branch is reached, in addition to restoring pointers / variables to the next "higher" directory / node). 


#18
Nov712, 10:50 PM

P: 283




Register to reply 
Related Discussions  
Iterative method  Precalculus Mathematics Homework  3  
Which approach is nicer? UK MEI approach? American approach?  Academic Guidance  0  
Iterative map in mathematica  Math & Science Software  5  
Iterative Methods  Calculus & Beyond Homework  6  
Iterative routines  General Math  13 