Iteration to recursive function

Question

In my first iterative algorithm, I do this

for (auto &widget : controls.getWidgets())
{
    if (!widget->visible) continue;

    widget->draw();

    for (auto &widget_component : widget->components)
    {
        if (!widget_component->visible) continue;

        widget_component->draw();

        for (auto &ww : widget_component->components)
        {
            if (!ww->visible) continue;

            ww->draw();
        }
    }
}

Now, I see the flaw in this algorithm because of the repetition of code.

I try to write a recursive function call to handle this thing.

void swcApplication::recursiveDisplay(swcWidget *next)
{
    if (next == nullptr) return;

    if ((next->parent != nullptr) &&
        !next->parent->visible) return;

    if (next->visible)
        next->draw();

    for (auto &i : next->components)
    {
        recursiveDisplay(i);
    }
}

void display()
{
    for (auto &widget : controls.getWidgets())
    {
        recursiveDisplay(widget);
    }
}

Display first the parent before all other children, if parent is not visible, then don't draw its children

Is the above phrase satisfy by this algorithm (As far as I can see, it is)? Is this optimal? I don't know what drawbacks might occur here because I just write in a few seconds.

If you didn't find anything wrong here, now, how can I put it back in iterative way? I know iteration is better.

Update

I didn't use any z attribute here and instead I go for painter's algorithm.

The flaw I am referring in my iteration version is that, it is limited to draw widgets depends on how deep I will code for iteration.

Answer 1

You can modify the recursive code to use an explicit stack:

#include <stack>

void display_widgets(control& controls)
{
    std::stack<widget*> widgets;
    for(auto &widget : controls.getWidgets()) {
        widgets.push(widget);
    }

    while(!widgets.empty()) {
        widget* w = widgets.top();
        widgets.pop();
        if(!widget->visible) {
            continue;
        }
        widget->draw();
        for(auto& component : widget->components) {
            widgets.push(component);
        }
    }
}

I know iteration is better.

This is highly dependent on language and usage. It is "better" in that recursion can use O(n) stack space (although not always - tail call optimization gets rid of this limitation), and won't blow your stack. However, in this case, assuming the recursive algorithm actually did what you wanted, it would be better and easier.

You can always turn a recursive solution into an iterative one by replacing the call stack with an actual stack of your own, as above. For very deeply nested recursive calls, this may save you from stack overflows, however, it is more fiddly to code, and in this case, doesn't gain you anything.

Having written the code above, my advice would be to stick with the recursive solution.

Answer 2

There are three ways in which your recursive version doesn't match your non-recursive version.

1. The recursive version will go deeper: it will paint great-grandchild widgets (if there are any)

2. The following tests exist in the recursive version but not in the non-recursive version:

     if (next == nullptr) return;
   
     if ((next->parent != nullptr) &&
         !next->parent->visible) return;
   

3. Most importantly (this is probably a bug), your recursive version displays children even if the parent is not visible. The if (!widget->visible) continue; in your non-recursive version should be if (!next->visible) return; in your recursive version.

I don't see why your parameter name is next: I think I'd call it widget.

Answer 3

You don't need quite so much checking and complexity in your recursive display function.

recursiveDisplay(swcWidget * widget)
{
    // don't draw the widget or any of it's children if it is not visible
    if(widget != nullptr && widget->visible)
    {
        // draw the current widget first
        widget->draw();

        // then draw the children
        // we already know at this point the parent of these children is visible.
        for(auto & widgetComponent : widget->components)
        {
            recursiveDisplay(widgetComponent);
        }
    }
}