CODEWITHSUNDEEP
phpoptimizationrecursion
moo
moo

Reputation: 7789

Optimizing a non-tail-recursive function

I have this function whose essential operations are outlined as follows:

function render($index) {
    foreach($things[$index] as $key => $data) {
        echo '<div>';
        /* irrelevant operations */
        if(isset($data['id'])) {
            echo '<div class="wrap">';
            render($things[$data['id']]);
            echo '</div>';
        }
        echo '</div>';
    }
}

I can not for the life of me figure out how to optimize this function; I fear that PHP implode if the call stack gets too big.

Is there any way to optimize this function?

Upvotes: 1

Views: 669

Answers (4)

Jasper Bekkers
Jasper Bekkers

Reputation: 6809

This code is untested, but from the top of my head, the iterative function should look something like this:

function render($index){
    $stack = array();
    array_push($index);

    $pre = '';
    $post = '';

    while(!empty($stack)){
        $idx = array_pop($stack);

        foreach($things[$idx] as $key => $value){
            $pre .= '<1>';
            $spost = '';

            if(isset($data['id'])){
                $pre .= '<2 class="wrap">';
                $spost .= '</2>';

                $stack[] = $things[$data['id']];
            }

            $spost .= '</1>';
            $post .= $spost;
        }
    }

    return $pre . $post;
}

Upvotes: 3

Paul Sonier
Paul Sonier

Reputation: 39510

You don't NEED to use recursion to do a depth-first traversal of your tree; it just happens to work really really well. If blowing your stack is a concern, you could just run a long loop on all your elements holding just the last and current positions. Recursion is a simpler and (generally) better way to perform the depth-first traversal though.

Upvotes: 3

Simon Broadhead
Simon Broadhead

Reputation: 3483

It's highly doubtful that you have to worry. If you're nesting divs deep enough that the call stack fills up, recursion depth is the least of your worries.

Upvotes: 9

Anthony
Anthony

Reputation: 7146

What you're doing is effectively traversing a tree. Basically, this is no worse than just printing all the values in a tree. Have you experienced any specific troubles with it getting too large? How deeply nested is this tree?

Upvotes: 3

Related Questions