從 1 到 n 的數字之和

如果我想找出從 1 到 n 的數字總和，其中 n 是一個自然數，我可以做 1 + 2 + 3 + 4 + ... + (several hours later) + n。或者，我可以寫一個 for 迴圈：

n = 0
for i in range (1, n+1):
    n += i

或者我可以使用一種稱為遞迴的技術：

def recursion(n):
    if n == 1:
        return 1
    return n + recursion(n - 1)

遞迴優於上述兩種方法。遞迴花費的時間少於寫出 1 + 2 + 3 的總和從 1 到 3.對於 recursion(4)，遞迴可用於向後工作：

函式呼叫：（4 - > 4 + 3 - > 4 + 3 + 2 - > 4 + 3 + 2 + 1 - > 10）

而 for 迴圈正在嚴格地工作：（1 - > 1 + 2 - > 1 + 2 + 3 - > 1 + 2 + 3 + 4 - > 10）。有時遞迴解決方案比迭代解決方案簡單。在實現連結串列的反轉時，這是顯而易見的。