Converting recursive algorithm to an iterative version

Discussion in 'C++' started by Ania, Dec 7, 2011.

  1. Ania

    Ania Guest

    Hi,

    Here is my problem:
    I implemented recurive algorithm in c++ for a problem given below:

    I have a list of items (only positive integers are allowed) and fixed
    number of bins of identical capacity. I need to pack items (if
    possible) so that elements in each bin sum up to given capacity.

    I try to convert my recursive algorithm to an one. However, my
    implementation with explicit stack doesn't work as I expected. I can't
    pinpoint the place where I have made a mistake.

    //items are sorted in decreasing order

    Recursive:
    bool backtrack(vector<int>& items, vector<Bin>& bins, unsigned
    index,unsigned bin_capacity)
    {
    if (bin_capacity - items.front() < 0) return false;

    if (index < items.size())
    {
    //try to put an item into all opened bins
    for(unsigned i = 0; i < bins.size(); ++i)
    {
    if (bins.sum() + items[index] + items.back() <=
    bin_capacity || bin_capacity - bins.sum() == items[index])
    {
    bins.add(items[index]);
    return backtrack(items, bins, index + 1,
    bin_capacity);

    }
    }
    //put an item without exceeding maximum number of bins
    if (bins.size() < BINS)
    {
    Bin new_bin = Bin();
    bins.push_back(new_bin);
    bins.back().add(items[index]);

    return backtrack(items, bins, index + 1, bin_capacity);

    }
    }
    else
    {
    //check if solution has been found
    if (bins.size() == BINS )
    {
    for (unsigned i = 0; i <bins.size(); ++i)
    {
    packed_items.push_back(bins);
    }

    return true;
    }
    }
    return false;

    }

    Iterative( not working properly)
    bool backtrack(vector<int>& items, vector<Bin>& bins, unsigned index,
    unsigned bin_capacity)
    {
    stack<Node> stack;
    Node node, child_node;
    Bin new_bin;
    //init the stack
    node.bins.add(new_bin);
    node.bins.back().add(items[item_index]);
    stack.push(node);
    item_index++;

    while(!stack.empty())
    {
    node = stack.top();
    stack.pop();

    if (item_index < items.size())
    {
    if (node.bins.size() < BINS)
    {
    child_node = node;
    Bin empty;
    child_node.bins.add(empty);
    child_node.bins.back().add(items[item_index]);
    stack.push(child_node);
    }

    int last_index = node.bins.size() - 1;
    for (unsigned i = 0; i <= last_index; i++)
    {
    if (node.bins[last_index - i]->get_sum()
    +items[item_index]+ items.back( <=bin_capacity || bin_capacity -
    node.bins[last_index - i]->get_sum() ==items[item_index])
    {
    child_node = node;
    child_node.bins[last_index - i]-
    >push_back(items[item_index]);


    stack.push(child_node);
    }
    }
    item_index++;
    }
    else
    {
    if (node.bins() == BINS)
    {
    //copy solution
    bins = node.bins;
    return true;
    }
    }
    }
    return false;

    }

    Any help would be highly appreciated.
    Ania, Dec 7, 2011
    #1
    1. Advertising

  2. On 12/7/2011 6:48 PM, Ania wrote:
    > Here is my problem:
    > I implemented recurive algorithm in c++ for a problem given below:
    >
    > I have a list of items (only positive integers are allowed) and fixed
    > number of bins of identical capacity. I need to pack items (if
    > possible) so that elements in each bin sum up to given capacity.
    >
    > I try to convert my recursive algorithm to an one. However, my
    > implementation with explicit stack doesn't work as I expected.


    What does that mean? What did you expect? What does it do? Do you
    think we should be guessing or dusting off our crystal ball?

    > I can't
    > pinpoint the place where I have made a mistake.


    Have you tried using a "debugger" and step through your code? Do you
    have a test case? Do you know what values of your objects need to be on
    every step of your algorithm? If you do, just fire off that debugger
    (whichever you got, all pretty much work when you know what you're
    doing) and execute your test program step by step, and verify that the
    values of the objects as they need to be. If they aren't make changes
    to the code.

    If you don't have a test case, get yourself one. If you don't know what
    values of your objects should be at every point in your program... did
    you actually write your program yourself? If you did, you should. Do
    you know how to use a debugger? If you don't, it looks like it's time
    to learn.

    Bite the bullet and fix your own program. Otherwise, find a different
    field to develop your skills.

    V
    --
    I do not respond to top-posted replies, please don't ask
    Victor Bazarov, Dec 8, 2011
    #2
    1. Advertising

  3. On Dec 7, 11:48 pm, Ania <> wrote:
    > Hi,
    >
    > Here is my problem:
    > I implemented recurive algorithm in c++ for a problem given below:
    >
    > I have a list of items (only positive integers are allowed) and fixed
    > number of bins of identical capacity. I need to pack items (if
    > possible) so that elements in each bin sum up to given capacity.
    >
    > I try to convert my recursive algorithm to an one. However, my
    > implementation with explicit stack doesn't work as I expected. I can't
    > pinpoint the place where I have made a mistake.
    >
    > //items are sorted in decreasing order
    >
    > Recursive:
    > bool backtrack(vector<int>& items, vector<Bin>& bins, unsigned
    > index,unsigned bin_capacity)
    > {
    >     if (bin_capacity - items.front() < 0) return false;
    >
    >     if (index < items.size())
    >     {
    >         //try to put an item into all opened bins
    >         for(unsigned i = 0; i < bins.size(); ++i)
    >         {
    >             if (bins.sum() + items[index] + items.back() <=
    > bin_capacity || bin_capacity - bins.sum() == items[index])
    >             {
    >                 bins.add(items[index]);
    >                 return backtrack(items, bins, index + 1,
    > bin_capacity);
    >
    >             }
    >         }
    >         //put an item without exceeding maximum number of bins
    >         if (bins.size() < BINS)
    >         {
    >             Bin new_bin = Bin();
    >             bins.push_back(new_bin);
    >             bins.back().add(items[index]);
    >
    >             return backtrack(items, bins, index + 1, bin_capacity);
    >
    >         }
    >     }
    >     else
    >     {
    >         //check if solution has been found
    >         if  (bins.size() == BINS )
    >         {
    >             for (unsigned i = 0; i <bins.size(); ++i)
    >             {
    >                 packed_items.push_back(bins);
    >             }
    >
    >             return true;
    >         }
    >     }
    >     return false;
    >
    > }
    >
    > Iterative( not working properly)
    > bool backtrack(vector<int>& items, vector<Bin>& bins, unsigned index,
    > unsigned bin_capacity)
    > {
    >       stack<Node> stack;
    >       Node node, child_node;
    >       Bin new_bin;
    >       //init the stack
    >       node.bins.add(new_bin);
    >       node.bins.back().add(items[item_index]);
    >       stack.push(node);
    >       item_index++;
    >
    >       while(!stack.empty())
    >       {
    >         node = stack.top();
    >         stack.pop();
    >
    >         if (item_index < items.size())
    >         {
    >             if (node.bins.size() < BINS)
    >             {
    >                child_node = node;
    >                Bin empty;
    >                child_node.bins.add(empty);
    >                child_node.bins.back().add(items[item_index]);
    >                stack.push(child_node);
    >             }
    >
    >             int last_index = node.bins.size() - 1;
    >             for (unsigned i = 0; i <= last_index; i++)
    >             {
    >                 if (node.bins[last_index - i]->get_sum()
    > +items[item_index]+ items.back( <=bin_capacity || bin_capacity -
    > node.bins[last_index - i]->get_sum() ==items[item_index])
    >                {
    >                    child_node = node;
    >                    child_node.bins[last_index - i]-
    >
    > >push_back(items[item_index]);

    >
    >                    stack.push(child_node);
    >                 }
    >             }
    >             item_index++;
    >             }
    >         else
    >         {
    >            if (node.bins() == BINS)
    >            {
    >                //copy solution
    >                bins = node.bins;
    >                return true;
    >            }
    >        }
    >    }
    >     return false;
    >
    > }
    >
    > Any help would be highly appreciated.


    build in some sort of trace facility. By seeing what gets called with
    what parameters should enable you to compare the recursive with the
    iterative and fix one or the other.

    Why are you doing this?
    Nick Keighley, Dec 8, 2011
    #3
  4. Ania

    Ania Guest

    @Nick Keighley I'm trying to implement an iterative version just
    because of stack overflows for large datasets in recursive approach,

    Thanks for your suggestions, I'll try to use debugger.
    Ania, Dec 8, 2011
    #4
  5. Ania

    Larry Evans Guest

    On 12/07/11 17:48, Ania wrote:
    [snip]
    > I try to convert my recursive algorithm to an one. However, my
    > implementation with explicit stack doesn't work as I expected. I can't
    > pinpoint the place where I have made a mistake.

    [snip]

    In the iterative code, there's:

    > int last_index = node.bins.size() - 1;
    > for (unsigned i = 0; i <= last_index; i++)
    > {
    > if (node.bins[last_index - i]->get_sum()
    > +items[item_index]+ items.back( <=bin_capacity || bin_capacity -
    > node.bins[last_index - i]->get_sum() ==items[item_index])

    This looks suspicious to me:

    ( <=bin_capacity

    Are you sure you've posted code that compiles?

    -regards,
    Larry
    Larry Evans, Dec 8, 2011
    #5
  6. Ania

    Ania Guest

    On 8 Gru, 18:58, Larry Evans <> wrote:
    > On 12/07/11 17:48, Ania wrote:
    > [snip]> I try to convert my recursive algorithm to an one. However, my
    > > implementation with explicit stack doesn't work as I expected. I can't
    > > pinpoint the place where I have made a mistake.

    >
    > [snip]
    >
    > In the iterative code, there's:
    >
    > >             int last_index = node.bins.size() - 1;
    > >             for (unsigned i = 0; i <= last_index; i++)
    > >             {
    > >                 if (node.bins[last_index - i]->get_sum()
    > > +items[item_index]+ items.back( <=bin_capacity || bin_capacity -
    > > node.bins[last_index - i]->get_sum() ==items[item_index])

    >
    > This looks suspicious to me:
    >
    >   ( <=bin_capacity
    >
    > Are you sure you've posted code that compiles?
    >
    > -regards,
    > Larry


    Finally, I found a place where I made a mistake. I messed with
    pointers(shallow copies) and that was the main problem. Now it works
    great.

    Thanks for inspiring me.

    I'm sorry but the code posted was not ready to compile, it was high
    level pseudocode.
    Here is code ready to compile (I don't use pointers here, just to make
    it simpler).

    class Bin
    {
    public:
    Bin() { _sum = 0;}
    int get_sum(){ return _sum; }
    int size() {return bin.size(); }
    bool isFull() { return _sum == bin.size(); }
    void add(int item)
    {
    bin.push_back(item);
    _sum += item;
    }
    //for testing output
    void print(){
    for(unsigned i = 0; i < bin.size(); ++i)
    {
    cout<< bin<<endl;
    }
    }
    private:
    vector<unsigned> bin;
    unsigned _sum;
    };

    struct Node
    {
    vector<Bin> bins;
    };

    BINS = 3; //just example value

    bool backtrack(vector<unsigned>& items, vector<Bin>& bins, unsigned
    index,unsigned bin_capacity)
    {
    if (bin_capacity - items.front() < 0) return false;

    if (index < items.size())
    {
    //try to put an item into all opened bins
    for(unsigned i = 0; i < bins.size(); ++i)
    {
    if (bins.get_sum() + items[index] + items.back() <=
    bin_capacity || bin_capacity - bins.get_sum() == items[index])
    {
    bins.add(items[index]);
    return backtrack(items, bins, index + 1,
    bin_capacity);

    }
    }
    //put an item without exceeding maximum number of bins
    if (bins.size() < BINS)
    {
    Bin new_bin = Bin();
    bins.push_back(new_bin);
    bins.back().add(items[index]);

    return backtrack(items, bins, index + 1, bin_capacity);

    }
    }
    else
    {
    if (bins.size() == BINS )
    {
    return true;
    }
    }
    return false;

    }


    bool backtrack2(vector<unsigned>& items, vector<Bin>& bins, unsigned
    item_index, unsigned bin_capacity)
    {
    stack<Node> stack;
    Node node, child_node;
    Bin new_bin;
    //init the stack
    node.bins.push_back(new_bin);
    node.bins.back().add(items[item_index]);
    stack.push(node);
    item_index++;

    while(!stack.empty())
    {
    node = stack.top();
    stack.pop();

    if (item_index < items.size())
    {
    if (node.bins.size() < BINS)
    {
    child_node = node;
    Bin empty;
    child_node.bins.push_back(empty);
    child_node.bins.back().add(items[item_index]);
    stack.push(child_node);
    }

    int last_index = node.bins.size() - 1;
    for (unsigned i = 0; i <= last_index; i++)
    {
    if (node.bins[last_index - i].get_sum()
    +items[item_index]+ items.back() <=bin_capacity || bin_capacity -
    node.bins[last_index - i].get_sum() ==items[item_index])
    {
    child_node = node;
    child_node.bins[last_index -
    i].add(items[item_index]);

    stack.push(child_node);
    }
    }
    item_index++;
    }
    else
    {
    if (node.bins.size() == BINS)
    {
    //copy solution
    bins = node.bins;
    return true;
    }
    }
    }
    return false;

    }
    Ania, Dec 8, 2011
    #6
  7. Ania <> wrote:
    > I try to convert my recursive algorithm to an [iterative] one.


    May I ask why?

    I think that unless there's a good reason for that, this is a true case
    of premature optimization (in the most negative sense). It is often the
    case that if an algorithm is recursive in nature, trying to implement it
    iteratively (especially if you need an explicit stack) only produces
    significantly longer and more complicated code. If the amount of recursion
    in the original algorithm is less-than-linear (eg. O(log n) recursions),
    then any possible overhead caused by the recursive calls is insignificant.

    Thus, in such a case, the iterative version will be longer, more
    complicated and with little to no speed benefit. (Hence why it's true
    premature optimization.)
    Juha Nieminen, Dec 9, 2011
    #7
  8. On Friday, December 9, 2011 2:41:12 PM UTC+8, Juha Nieminen wrote:
    > Ania <> wrote:
    > > I try to convert my recursive algorithm to an [iterative] one.

    >
    > May I ask why?
    >
    > I think that unless there's a good reason for that, this is a true case
    > of premature optimization (in the most negative sense). It is often the
    > case that if an algorithm is recursive in nature, trying to implement it
    > iteratively (especially if you need an explicit stack) only produces
    > significantly longer and more complicated code. If the amount of recursion
    > in the original algorithm is less-than-linear (eg. O(log n) recursions),
    > then any possible overhead caused by the recursive calls is insignificant.
    >
    > Thus, in such a case, the iterative version will be longer, more
    > complicated and with little to no speed benefit. (Hence why it's true
    > premature optimization.)


    If you are writing programs to be run infrequently for trivial jobs,
    I have to say that in this kind of trivial cases there is no need for any optimization or improvement for this kind of programming.

    But in my experience, codes fine-tued for speed requirements are not low paid
    programmers' jobs in the industry.
    88888 Dihedral, Dec 9, 2011
    #8
  9. 88888 Dihedral <> wrote:
    > If you are writing programs to be run infrequently for trivial jobs,
    > I have to say that in this kind of trivial cases there is no need for any optimization or improvement for this kind of programming.


    And my point is that *regardless* of where the code might be used,
    converting a naturally recursive algorithm into an iterative form that
    avoids the recursive function call is usually premature optimization of
    the bad kind (makes the code significantly more complicated for little
    to no benefit).
    Juha Nieminen, Dec 10, 2011
    #9
  10. On Saturday, December 10, 2011 5:54:32 PM UTC+8, Juha Nieminen wrote:
    > 88888 Dihedral <> wrote:
    > > If you are writing programs to be run infrequently for trivial jobs,
    > > I have to say that in this kind of trivial cases there is no need for any optimization or improvement for this kind of programming.

    >
    > And my point is that *regardless* of where the code might be used,
    > converting a naturally recursive algorithm into an iterative form that
    > avoids the recursive function call is usually premature optimization of
    > the bad kind (makes the code significantly more complicated for little
    > to no benefit).


    There are very limited cases for recursive functions to be used in C.
    The quick sort in the c lib is notorious to be choked quite often.
    Tree visiting of 30K nodes or less in C is too simple to be modified for speeds.
    88888 Dihedral, Dec 10, 2011
    #10
  11. 88888 Dihedral <> wrote:
    > There are very limited cases for recursive functions to be used in C.


    You don't understand my point.

    > The quick sort in the c lib is notorious to be choked quite often.


    qsort() is not slow because of the recursion. std::sort() uses recursion
    as well. So what?
    Juha Nieminen, Dec 10, 2011
    #11
  12. On Saturday, December 10, 2011 6:33:15 PM UTC+8, Juha Nieminen wrote:
    > 88888 Dihedral <> wrote:
    > > There are very limited cases for recursive functions to be used in C.

    >
    > You don't understand my point.
    >
    > > The quick sort in the c lib is notorious to be choked quite often.

    >
    > qsort() is not slow because of the recursion. std::sort() uses recursion
    > as well. So what?


    There was not my problem. That was problems for non-professionals.
    88888 Dihedral, Dec 10, 2011
    #12
  13. On Saturday, December 10, 2011 6:41:28 PM UTC+8, 88888 Dihedral wrote:
    > On Saturday, December 10, 2011 6:33:15 PM UTC+8, Juha Nieminen wrote:
    > > 88888 Dihedral <> wrote:
    > > > There are very limited cases for recursive functions to be used in C.

    > >
    > > You don't understand my point.
    > >
    > > > The quick sort in the c lib is notorious to be choked quite often.

    > >
    > > qsort() is not slow because of the recursion. std::sort() uses recursion
    > > as well. So what?

    >
    > There was not my problem. That was a problem for non-professionals.
    88888 Dihedral, Dec 10, 2011
    #13
  14. Juha Nieminen <> wrote:
    > 88888 Dihedral <> wrote:
    >> If you are writing programs to be run infrequently for trivial jobs,
    >> I have to say that in this kind of trivial cases there is no need for
    >> any optimization or improvement for this kind of programming.

    >
    > And my point is that *regardless* of where the code might be used,
    > converting a naturally recursive algorithm into an iterative form that
    > avoids the recursive function call is usually premature optimization of
    > the bad kind (makes the code significantly more complicated for little
    > to no benefit).


    One can argue if it is an optimization at all, but why do you always call
    it premature? In my understanding, premature optimization is optimization
    that is done before knowing if it is really worth it. Bad quality alone
    doesn't qualify an optimization as premature.

    The OP has already said that he has encountered stack overflows, so I
    really would not call that premature if he wants to do fix that.
    You cannot always control the stack size awailable to a function especially
    if you are writing a library and not an executable.

    Tobi
    Tobias Müller, Dec 10, 2011
    #14
  15. Ania

    Joe keane Guest

    In article <Xns9FB5D491D88E7myfirstnameosapriee@216.196.109.131>,
    Paavo Helde <> wrote:
    >Increasing the stack size should be relatively harmless unless the app has
    >many threads.


    That's what gets you...

    Stack on multi-thread apps is demanding.

    Even if some memory is needed for a short time, (heap is what the
    threads need at the same time, stack is what all the threads need some
    of the time) the heap allocation may be -faster- (because it uses memory
    efficiently).

    Also running out of stack is ungraceful... If you call malloc and it
    returns NULL (oh wait this C++ you know what mean) you can try to
    restore some semblance of order. Out of stack, blam! Your files,
    shared memory??

    I echo some other posters that we don't know the context of program.
    Some app you only run yourself? Quasi-real-time where some people die
    if it fails?
    Joe keane, Dec 11, 2011
    #15
  16. Ania

    Ania Guest

    This app is just for my personal use and it works quite fast for data
    sets < 50 000 items. However, for larger data sets I encountered stack
    overflows and I was wondering if changing it to an iterative version
    would solve the problem.
    Ania, Dec 11, 2011
    #16
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. BQ
    Replies:
    14
    Views:
    755
    Richard Bos
    Mar 25, 2005
  2. V Green
    Replies:
    0
    Views:
    840
    V Green
    Feb 5, 2008
  3. PA Bear [MS MVP]
    Replies:
    0
    Views:
    952
    PA Bear [MS MVP]
    Feb 5, 2008
  4. V
    Replies:
    4
    Views:
    669
    Ben Bacarisse
    May 13, 2008
  5. Baba
    Replies:
    42
    Views:
    2,382
Loading...

Share This Page