Removing recursion from inside of a loop

Question

Given code that looks something like this (pseudocode):

f(args)
    result = simple_case
    if (base_case(args))
        return result
    new_args = args
    for each x in args list
        remove x from new_args
        if (need_to_update_result_based_on_x(result,x))         
            result = f(new_args)
    return result

I already know how to remove tail-recursion from a function, but I am unsure if there are straightforward techniques for removing recursion that itself is inside of a loop, as above.

In particular, I am especially wondering if it is it possible to rewrite it so that it is purely iterative? By which I mean that it does not even need to effectively emulate the recursive design by simply implementing it's own stack? If not, what would generally be the most economical (in terms of storage and time) way to rewrite such a function?

In the recursion part, you are assigning `f(new_args)` to `result` - are you sure your intent isn't to somehow aggregate the result? — CptBartender, May 10 '15 at 20:36
No, but it is derived from up to the first k entries in args, and k is constant. — markt1964, May 10 '15 at 20:40
It is impossible to rewrite this code in pure iterative way without using extra O(args.length) memory (it may be separate stack or an unused field of every args[i]). — Egor Skriptunoff, May 10 '15 at 21:13
Please give evaluative information: 1) how many bytes are required to store `result`, 2) how many bytes are required to store one argument `args[i]`, 3) how many arguments are in list `args`, 4) what is the probability for `need_to_update_result_based_on_x(result,x)` to return `true`? — Egor Skriptunoff, May 10 '15 at 21:30
@EgorSkriptunoff: 1) 64 bytes. 2) 16 bytes. 3) Args is actually an array, with a fixed additional amount of overhead the same size as result. 4) The average probability that need_to_update_result_based_on_x(result,x) returns true is, in general, going to be proportional to the number of elements remaining in args after 'x'. — markt1964, May 10 '15 at 22:13
3) How many elements are in `args`? N=10? 100? 1000? Can you allocate N*(64+4) bytes for emulating stack? 4) Is this probability near to zero? 5) Can assignment `new_args = args` be implemented as simply saving a pointer to the first array's element instead of full array copying? 6) Can operation `remove x from new_args` be implemented by incrementing that pointer (without modifying overhead data)? — Egor Skriptunoff, May 10 '15 at 22:35

jxh · Accepted Answer · 2015-05-10T20:48:43.203

2

The args list is being reduced by each iteration for the for loop in the function, and the reduced list is also passed to the next recursive call. So, when the recursive call returns, the loop picks up with the list that it had when it made the recursive call, but the recursive call itself has already worked out results for the reduced versions of that list.

To avoid redoing work already done, you can cache the results of the previous recursive calls so that future recursive calls need not redo the complete computation. This technique is often referred to as memoization.

So, to remove the recursion altogether, the base case results can be computed upfront and remembered (memoized). These memoizations can be used to compute results for the base case plus one of the other arguments in the list, and these results also memoized (at this point, the base case results can be tossed). You can repeatedly compute memoizations for each successive larger list size until you achieve a result for the desired argument list.

edited May 10 '15 at 20:48

answered May 10 '15 at 20:36

jxh

69,070
8
110
193

To expand on that answer, you can also start calculating the result from the back (meaning, for the last argument first, then for the last two and so on) and cache these results - this way you can skip the recursion completely. – CptBartender May 10 '15 at 20:37
@CptBartender: Thanks, expanded the answer accordingly. – jxh May 10 '15 at 20:48
@CptBartender: Would you be able to elaborate on how I would have to rewrite the function to do something like that? – markt1964 May 10 '15 at 21:06
Please see @jxh's updated answer - it covers this aspect pretty well. – CptBartender May 10 '15 at 21:08
Please see [What's the difference...?](http://stackoverflow.com/q/12133754/315052) and its duplicate [Dynamic programming...](http://stackoverflow.com/q/6164629/315052). – jxh May 12 '15 at 16:36

Removing recursion from inside of a loop

1 Answers1