Thread: How to change recursive loop to non recursive loop

  1. #1
    Registered User
    Join Date
    Jan 2002
    Posts
    68

    Lightbulb How to change recursive loop to non recursive loop

    How to change recursive loop to non recursive loop
    I want to find area of contiguous 5 (5-connected area) in two dimension array like this

    00000000000000000
    00000055555500000
    00000055055000000
    00000000005550000
    00000000000000000


    Contiguous area of number 5 = 13
    I write FindAreaof5 function below and m_tempData(x,y) is data in this array (0 or 5)
    I call FindAreaof5 function by this loop

    code
    .................................................. .............
    for (y=0; y< height; y++){
    for (x=0; x< width; x++){
    if (m_tempData(x,y) == 5){
    InterestArea = FindAreaof5(x,y);
    }
    }
    .................................................. .............

    ////Below this is FindAreaof5 function//////

    code
    .................................................. .............
    long FindAreaof5(int x, int y)
    {
    long count ;
    if (m_tempData(x,y)==0) return 0;
    m_tempData(x,y) = 0;

    count = 1 + FindAreaof5(x, y-1) + FindAreaof5(x+1, y-1)
    + FindAreaof5(x+1, y) + FindAreaof5(x+1, y+1)
    + FindAreaof5(x, y+1) +FindAreaof5(x-1, y+1)
    + FindAreaof5(x-1, y) + FindAreaof5(x-1, y-1);
    return count;
    .................................................. .............

    In the above example I can find FindAreaof5 = 13
    If FindAreaof5 has small value ,it can find FindAreaof5.
    But if FindAreaof5 has large value (more than 12000) , it show message box and tell me there is Stack Overflow error.
    I want to know how to solve this problem. Someone suggest me to change recursive loop to non recursive or use blob coloring but I do not know how to do that. If you know how to solve my problem, please tell me. Thank you very much.

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    Recursion is very similar to a loop, instead of calling the function again, simply reiterate.

    >it show message box and tell me there is Stack Overflow error
    Code:
    count = 1 + FindAreaof5(x, y-1) + FindAreaof5(x+1, y-1) 
    + FindAreaof5(x+1, y) + FindAreaof5(x+1, y+1) 
    + FindAreaof5(x, y+1) +FindAreaof5(x-1, y+1) 
    + FindAreaof5(x-1, y) + FindAreaof5(x-1, y-1);
    Hmm, I wonder why...Each time a function calls itself, completely separate copies of it's variables are popped onto the stack, meaning that something like the above code will fill available stack space pretty quickly. This is the type of situation where an iterative solution is far better than a recursive one.

    -Prelude
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. adding a function to a program
    By trippedwire in forum C++ Programming
    Replies: 9
    Last Post: 09-30-2004, 12:35 PM
  2. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  3. help with calculating change from a dollar
    By z.tron in forum C++ Programming
    Replies: 3
    Last Post: 09-13-2002, 03:58 PM
  4. while loop vs recursive
    By Unregistered in forum C Programming
    Replies: 2
    Last Post: 04-07-2002, 07:33 AM
  5. Replies: 2
    Last Post: 09-04-2001, 02:12 PM