Recursive sum

Watch calls build up, reach the base case, then return in reverse order.

1def recursive_sum(n):2    if n == 0:3        return 04    subtotal = recursive_sum(n - 1)5    return n + subtotal

B2.4.5: a simple non-branching recursive function. Each call makes at most one recursive call. For non-negative n: O(n) time and O(n) auxiliary call-stack space. A loop can use O(1) auxiliary space.