def recsum(x):
if x==1:
return x
else:
return x+recsum(x-1)
为了成功运行上述代码,你需要建立调用栈。但是,
def tailrecsum(x,running_total=0):
if x==0:
return running_total
else:
return tailrecsum(x-1,running_total+x)
2) 要运行上述代码,您不需要构建调用堆栈,因为已经有了running_total。只需为“原始调用”和递归构建调用堆栈,无需构建调用堆栈,因为计算该函数所需的状态存储在running_total中。
另外,关于快速排序,我认为教授可能是指可以通过“使用”尾递归来优化快速排序。对于qsort()的两个分支部分,我们可以在基于枢轴位置的较高项的一侧使用尾递归。
function quicksort(array, 'left', 'right')
// If the list has 2 or more items
if 'left' < 'right'
// See "Choice of pivot" section below for possible choices
choose any 'pivotIndex' such that 'left' ≤ 'pivotIndex' ≤ 'right'
// Get lists of bigger and smaller items and final position of pivot
'pivotNewIndex' := partition(array, 'left', 'right', 'pivotIndex')
// Recursively sort elements smaller than the pivot
quicksort(array, 'left', 'pivotNewIndex' - 1)
// Recursively sort elements at least as big as the pivot
quicksort(array, 'pivotNewIndex' + 1, 'right')
quicksort
的最后一个方法调用是它自己,这就是尾递归。但其他一些实现则不是尾递归。 quicksort(left) + pivot + quicksort(right)
已排序的左部分 + 枢轴元素 + 已排序的右部分
。