优化递归函数

Question

我目前正在处理一个处理大量递归调用的副项目。我不是计算机科学家，所以我不确定如何优化我的代码。我知道递归函数的效率不是很高，而且我听说您经常可以用尾调用替换它，但我不确定如何去做。该函数接受三个数组：appendList、sequence 和 used。其他参数 base、length、index 和 last word 都是整数。

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

将此递归转换为尾调用是否可以快速解决？如果不是，我可以做些什么来优化这个功能？

Answer 1

一般来说，任何递归都可以转换为循环，循环通常会有更好的性能，因为它具有相似的算法性能，不需要分配新的帧和存储额外的信息。

“尾调用优化”是编译器（或运行时）所做的事情，如果递归调用是函数中的最后一次调用（因此得名 - “尾调用”），它会自动将递归转换为循环，通常是通过重用相同的调用帧，而不是分配一个新的调用帧。重用框架是可以的，因为如果你对递归调用的结果所做的只是返回它，那么你不需要来自封闭函数调用的任何其他东西，所以没有理由首先保持框架处于活动状态。

所以，你需要检查的是：

1. 您的编译器是否支持尾调用优化。
2. 为了允许编译器这样做，您必须做什么 - 通常简单的return f(...)模式会起作用，但有时编译器可以支持更复杂的代码。

两者都取决于您的特定编译器，因此我会查找有关它的文档-我无法从您的问题中得知它是什么。