Thread: difference between recursive and iterative

  1. #1
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    715

    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

  2. #2
    ---
    Join Date
    May 2004
    Posts
    1,379
    i cant answer that question.
    but why would you need to think about it? just do what ever works for your program when the time comes.

  3. #3
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    715
    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.
    Last edited by Micko; 07-04-2004 at 11:08 AM.

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    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
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  5. #5
    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.
    Emmanuel Delahaye

    "C is a sharp tool"

  6. #6
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    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.

  7. #7
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    715
    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? )
    Last edited by Micko; 07-04-2004 at 11:23 AM.

  8. #8
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    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

  9. #9
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    715
    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.
    Last edited by Micko; 07-04-2004 at 11:47 AM.

  10. #10
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    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.

  11. #11
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    715
    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

  12. #12
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    1) You the quote tag instead of the code tag when quoting
    2) You have now answered your own question

  13. #13
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    715
    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.
    Only I've got is a bad headache!

  14. #14
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    715
    Quote Originally Posted by Thantos
    You have now answered your own question
    That means this formulae is recursive. But the question how to recognize iterative stays open.

    Are there any other opinions?

  15. #15
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    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)

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Using both a Recursive and Iterative Functions
    By belkins in forum C Programming
    Replies: 12
    Last Post: 11-02-2008, 12:31 PM
  2. recursive function
    By technosavvy in forum C Programming
    Replies: 1
    Last Post: 02-29-2008, 05:42 AM
  3. splitting linked list recursive vs. iterative
    By Micko in forum C Programming
    Replies: 7
    Last Post: 03-17-2005, 05:51 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. Iterative Tree Traversal using a stack
    By BigDaddyDrew in forum C++ Programming
    Replies: 7
    Last Post: 03-10-2003, 05:44 PM