Optimizing Recursive Function

Question

I'm currently working on a side project that deals with a lot of recursive calls. I'm not a computer scientist, so I'm not exactly sure how to optimize my code. I know that recursive functions are not very efficient and I've heard that you can often replace it with tail calls, but I'm not exactly sure how to go about doing this. This function takes in three arrays: appendList, sequence, and used. The other arguments, base, length, index and last word are integers.

function Recursion(appendList, base, length, sequence, used, lastWord, index)
#Global variables:
global G_Seq_List
global G_Seq_Index

used = ones(UInt8, 1, base^length)
used[1] = 0

if index == base^length
    check = zeros(UInt8, base^length, 1)

    for i = 1 : base^length
        index = 1
        for j = 1 : length
            k = mod(i+j-1,base^length)
            index = index + base^(length - j)*sequence[k+1] 
        end

        check[index] = check[index] + 1

        if check[index] != 1 
            return
        end
    end

    G_Seq_List[G_Seq_Index,:] = sequence[:] 
    G_Seq_Index = G_Seq_Index + 1 

    return
end

#Builds Sequence
for i = 1 : base^length
    if appendList[i , mod(lastWord - 1, base^(length - 1)) + 1] == 1
        if used[i] == 1 
            tempUsed = used
            tempUsed[i] = 0
            tempCounter = index + 1 
            tempSequence = sequence
            tempSequence[tempCounter] = mod(i - 1, base)
            Recursion(appendList, base, length, tempSequence, tempUsed, i, tempCounter)
        end
    end
end
end

Is it a quick fix to turn this recursion into a tail call? If not, what kind of things can I do to optimize this function?

Can you also explain what you are trying to accomplish with this function? Also, the first step of doing optimization is knowing why you want to optimize. Is it slow? What's the typical input size? — justhalf
– justhalf, Commented Apr 27, 2017 at 5:29

Oak · Accepted Answer · 2017-04-27 13:24:21Z

In general, any recursion can be converted to a loop, and a loop will generally have better performance, since it has similar algorithmic performance without the need to allocate new frames and store extra information.

"Tail call optimization" is something the compilers (or runtimes) do, which is to automatically convert the recursion to a loop if the recursive call is a last call in the function (hence the name - "tail call"), typically by reusing the same call frame instead of allocating a new one. Reusing the frame is okay since if all you do with the result of the recursive call is return it, you don't need anything else from the enclosing function invocation, so there's no reason to keep the frame alive in the first place.

So, what you need to check is:

Whether your compiler supports tail-call optimization.
What you have to do in order to allow the compiler to do so - usually the straightforward return f(...) pattern will work, but sometimes the compiler can support more complex code.

Both depend on your specific compiler, so I would look up documentation about it - I could not tell what it is from your question.

Collectives™ on Stack Overflow

Optimizing Recursive Function

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related