在Cairo智能合约中何时使用尾部调用优化

Question

我通常可以用一些不那么优雅的代码创建函数的终端递归版本。我应该这样做，因为这样可以减少费用，还是应该保留未优化的版本?

例如，这里有一个"未优化的"对数组元素求和的函数:

@view
func get_convoy_strength{syscall_ptr : felt*, pedersen_ptr : HashBuiltin*, range_check_ptr}(
convoy_id : felt
) -> (strength : felt):
alloc_locals
let (convoyables_len : felt, convoyables : felt*) = get_convoyables(convoy_id)
return _get_convoyables_strength(convoyables_len, convoyables)
end

下面是尾部调用优化:

func _get_convoyables_strength_tc{
syscall_ptr : felt*, pedersen_ptr : HashBuiltin*, range_check_ptr
}(convoyables_len : felt, convoyables : felt*, sum : felt) -> (strength : felt):
if convoyables_len == 0:
return (sum)
else:
let convoyable_id = [convoyables]
alloc_locals
let (convoyable_strength) = _get_strength(convoyable_id)
return _get_convoyables_strength_tc(
convoyables_len - 1, convoyables + 1, sum + convoyable_strength
)
end
end

正如你所看到的，它有点不太友好，因为它需要一个额外的参数(它总是0)。在普通的计算机上，这可以优化为不填满调用堆栈，但正如FeedTheFed指出的那样，这里的内存是不可变的，所以它似乎没有用。不过，他确实说过，"不为中间返回值浪费内存单元"可能会很有趣。如果能有更详细的解释对我很有帮助，因为我不太明白。

下面是与此相关的cairo文档:https://www.cairo-lang.org/docs/how_cairo_works/functions.html?highlight=tail#tail-recursion

Answer 1

简短的回答:相对于访问存储和使用其他系统调用，几个额外Cairo步骤的成本可能可以忽略不计，因此我将从"未优化"的方法开始。只有当函数大量使用时，才尝试优化。它似乎对总成本有很大影响。

较长的答案:

正如您提到的，由于不可变内存，通常的重用堆栈的尾部调用优化在Cairo中是不相关的。在Cairo中，尾调用递归的优点是，当被调用的函数返回时，您不需要对返回值做任何操作。这意味着在尾调用递归中，从内部调用返回的只是ret指令的序列。

另一方面，非尾部调用递归(如示例中的递归)将具有处理内部调用返回值的指令，例如复制隐式参数和计算当前结果与下一个元素的和。

在某些(非常简单的)情况下，它不会比尾部调用版本更糟糕。例如，考虑下面计算1 + 2 + ... + i的函数:

func sum(i : felt) -> (res : felt):
if i == 0:
return (res=0)
end
let (partial_sum) = sum(i=i-1)
return (res=partial_sum + i)
end

此函数每次迭代需要5步:递归调用前3步(if, pushi-1,call sum)，后2步(计算和，ret)。"optimized"尾部调用版本每次迭代也需要5步:4步之前和1步之后。

但是这是一个非常简单的情况，没有隐式参数，只有一个返回参数。如果我们添加一个隐式参数(即使它在函数中未使用)，尾部调用版本将执行得更好:每次迭代只增加1步，而非尾部调用版本则增加2步。在您的示例中，您有3个隐式参数，因此尾部调用版本可能会更好(尽管，我猜它不会很重要，但这取决于其余的代码)。