Thread: difference between recursive and iterative

  1. #31
    Registered User
    Join Date
    Aug 2003
    Posts
    470
    You might find this interesting to read Micko.
    http://mitpress.mit.edu/sicp/full-te...ml#%_sec_1.2.1

  2. #32
    Registered User
    Join Date
    Jun 2004
    Posts
    722
    The fibonacci series is a bad example of recursion because the number can be calculated with a single way loop. On the other hand if you want to make operations on a graph, like doing a depth search, recurssion is imperative, unless you want a PhD in non-recursive functions.
    I'm saying this because calling a function requires pushing arguments and the return point adress to the stack, which could in some cases spend to much memory, or even overflow the stack, causing the program to crash.
    This could happen with the floodfill algorithm to fill regions of pixels.
    Code:
    void floodfill(int x, int y){
        if(/*point is on contour, or has countour color*/)
            return;
        floodfill(x+1, y);
        floodfill(x-1, y);
        floodfill(x, y+1);
        floodfill(x, y-1);
    }
    imagine if you have a big picture..., but in this case a non-recursive implementation is very hard to implement.
    About fibonacci:
    Code:
    int fibrec(int n){
        if(n<2) return 1;
        return fibrec(n-1)+fibrec(n-2);
    }
    
    int fibnrec(int n){
        int n0=0, n1=1, i=0;
    
        while(i++<n){/*sum cicle*/
            if(n0>n1)
                n1=n0+n1;
            else
                n0=n1+n0;
        }
        return n0>n1?n0:n1;
    }
    The second implementation is non-recursive, therefore much lighter to the computer, and in this case very optimized, because the function runs a single loop, instead of calling itself twice.

    So please consider in the future whether to use recursion or loops, now that you now what these are.

  3. #33
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Actually going from recursive to non recursive is a completly machnical process. The C++ class I will be taking in the fall actually goes into it. Only thing that makes it difficult is the number of recursion points.

  4. #34
    Registered User
    Join Date
    Jun 2004
    Posts
    722
    Quote Originally Posted by Thantos
    Only thing that makes it difficult is the number of recursion points.
    Exactly!

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