这两种递归方法有什么区别

Question

我有相同算法的两个版本，它们递归地查找链表中的最小元素。一种算法首先检查是否已到达列表的末尾，如果是，returns 该元素然后检查当前元素（列表的头部）是否小于递归调用的当前最小值。如果当前元素更大，则返回当前最小值（通过递归调用找到）。

另一个算法略有不同，在检查基本情况后，它将递归调用存储在一个临时变量中，然后使用临时变量与当前列表元素进行比较。

我发现第一种方法的重复是：

T(n) = 1T(n-1) + O(1)

（我不太确定）

我想不通的是，第二种算法在重复出现时会有什么不同，因为它们似乎在做同样的事情。存储在临时变量中的递归调用是否为重复增加了额外的工作？

两种算法的伪代码如下：

第一种方法

function min_list_1(L) // L is a non-empty list of numbers
    if has_only_one_element(L): return L.head
    if L.head < min_list_1(L.next): return L.head
    else:
        return min_list_1(L.next)

第二种方法

function min_list_2(L) // L is a non-empty list of numbers
    if has_only_one_element(L): return L.head
    temp = min_list_2(L.next)
    if L.head < temp: return L.head
    else:
        return temp

Answer 1

对于大多数情况，第一个将进行两次递归调用（当 L.head 不是找到的最小值时）：一次是评估条件，第二次是 return 新的价值。这会导致 2^n 的复杂性。使用 temp 保持线性。

Answer 2

在loremIpsum1771的回答之上，我在这里打个简单的比方：

for(int i=0; i< strlen(s); i++){
     ...
}
     
     
     vs
     
for(int i=0, len=strlen(s); i<len; i++){
     ...
}

哪个更快，为什么？

第一个慢得多，原因与您的 OP 完全相同，您每次/多次调用某些东西，而您确实可以预计算一次

这两种递归方法有什么区别

What is the difference between these two recursive approaches

algorithm

recursion

recurrence