# difference between recursive and iterative

Show 80 post(s) from this thread on one page
Page 1 of 3 123 Last
• 07-04-2004
Micko
difference between recursive and iterative
I conceptually understand what is the difference between recursive and iterative implementation of some problem. Iterative uses loops, and recursive uses recursive function calls. But I found terms recursive formula and iterative formula.
For example formula for Newton_Raphson method for solving equation f(x)=0 is

x(n+1)=x(n)+f(x(n))/f'(x(n))

Is this recursive or iterative formula. What is the difference?
I read somewhere that recursive formulaes are best to implement by recursion in C and iterative formulaes are best to implement iterative using loops.
How can I recognize iterative from recursive formulae.
Thanks
• 07-04-2004
sand_man
but why would you need to think about it? just do what ever works for your program when the time comes.
• 07-04-2004
Micko
I'm really very curious about this. It's really interesting question. I assumed there are a lot of experienced programmers that could answer this question.
• 07-04-2004
Salem
Recursion is nothing more than a disguised loop. Anything you can express recursively you can also express iteratively.

Two factorials
Code:

```#include <stdio.h> int f1 ( int n ) {     int i, res = 1;     for ( i = 1 ; i <= n ; i++ ) res *= i;     return res; } int f2 ( int n ) {     if ( n == 1 ) return 1;     else return n * f2(n-1); } int main ( void ) {     printf( "%d %d\n", f1(8), f2(8) );     return 0; }```
This isn't to say that some recursive functions can be easily written as a loop.
The towers of Hanoi problem is very neatly written in just a few lines recursively, but takes a bit more effort to write it out in a loop.

Quicksort for example is often expressed in recursive terms, but the most efficient implementations are usually iterative.

Only the most perverse coder would have a recursive strlen() function for example :)
• 07-04-2004
Emmanuel Delaha
Quote:

Originally Posted by Micko
<...> How can I recognize iterative from recursive formulae.
Thanks

How is this a question about the C language ?

It's more a mathematics and/or algorithm question.
• 07-04-2004
Thantos
Emmanuel we answer algorithm questions in these forums. If they are using C then they post it in the C forum, if they are using C++ they post it in the C++ forum, for a game in the game forum, etc. Hell half of the questions I see generaly break down to a algorithm problem.
• 07-04-2004
Micko
Thanks for replying. Like I said I understand the difference between recursive and iterative implementation. However I'm not able to understand recursive and iterative formulaes. Just look at example above:
it is iterative because I can iteratively repeat same procedure to get solution that satisfies certain criterium. On the other hand it is recursive, because I use result from previous step.
If someone can tell me if this is recursive or iterative formula.
And Emmanuel, yes this is algorithm question, but I don't think that should stop me for asking. I'm sure there are a lot of more experinced programmers that faced the same question. After all, I hope this forum is not only for correcting syntaxs and semantics errors!

Is it possible to say this:

A recursive formule is that one in which you use results from previous steps with algebraic operations involving only a constants
example:

Code:

```y(0)=1; y(1)=1; y(n)=y(n-1)+y(n-2);```
An iterative forumla is that one in which you use results from previous steps + additional computation
example:

Code:

```x(0)=0.5 f(x)=x^2+3*x+2; f'(x)=2*x+3; x(n+1)=x(n)-f(x(n))/f'(x(n));```
Here, beside value x(n) which is calculated in previous step, one must calculate f(x(n)) and f'(x(n)).

Does this make any sense?

(Just to remember my main question was: Is Newton Raphson formulae recursive or iterative? :))
• 07-04-2004
Thantos
Well there is a rule for all recursive formulas. You have to be given the starting values.

In general a recursive formula requires that you know the previous value to calculate the next value. Example would be the fibnacci sequence.
f(n) = f(n-1) + f(n-2) where f(0) = 1 and f(1) = 1
• 07-04-2004
Micko
So,
Fibonacci sequence is recursive formula that's ok, but what about
that Newton-Raphson formulae and others similar numerical methods?
For example solving equation x^2+2*x-4=0 using Newton method you must start from somewhere: example x=1, and after 2-3 steps you get x=1.236...
I still cannot figure out what is difference if there is any.
• 07-04-2004
Thantos
Well does the Newton-Raphson formula meet the two critera
1) Do you need to know n-1 to find n
2) Are you giving the starting values

If it meets both then yes its recursive. Just becareful because just as any recursive algorithm can be rewritten to be iterative so can formulas.
• 07-04-2004
Micko
Code:

```Well does the Newton-Raphson formula meet the two critera 1) Do you need to know n-1 to find n 2) Are you giving the starting values If it meets both then yes its recursive. Just becareful because just as any recursive algorithm can be rewritten to be iterative so can formulas.```
1) yes, as you can see I must use x(n) to compute x(n+1)
2) yes, I'm giving the start value, but there is a catch:
I'm sloving equation it has exact value, I predict that value assuming for example x=1 and after 2-3 iteration (steps) (it depends on what precision I want example 3 exact decimals) I get x=1.236...
this means that my assumed values is becaming more and more accurate. This is, you must admit trickier question.
In example with fibonacci sequence you get array:
1 1 2 3 5...
but in example with Newton-Raphson
you get also an array, but solution is just last element
• 07-04-2004
Thantos
1) You the quote tag instead of the code tag when quoting :)
• 07-04-2004
Micko
In school we called Newton formulae iterative.
But, I think I need to take an aspirin, to have rest then take beer and watch Portugal-Greece.
• 07-04-2004
Micko
Quote:

Originally Posted by Thantos

That means this formulae is recursive. But the question how to recognize iterative stays open.

Are there any other opinions?
• 07-04-2004
Perspective
i guess it all depends on your definition of iterative. consider the following.

f( n ) = f( n-1 ) + blah blah (for all n = 0,1,2,...)
this is recursive by definition. It is also iterative because you find successive values based on previous ones. so, to find value f( 3 ) you need f( 2 ), to find f( 2 ) you need f( 1 ), etc.... Each iteration produces a sequential result.

f( n ) = f( n/2 ) + log( blah blah ) (for all n = 2^x, x = 0,1,2,3....)
this is also recursive. Note that it is not iterative; f( n+1 ) has nothing to do with f( n ).
This could be considered iterative (iterating by powers of 2 in this case) though i think by what you've explained this is what would souly be called recursive and not iterative.

like Salem and Thantos said, in terms of implementation, any recursive proceedure can be implemented iteratively. in terms of theory, both examples ive given are recursive, only the first is iterative. (like i mentioned above though, really depends on your definition of iterative)
Show 80 post(s) from this thread on one page
Page 1 of 3 123 Last