Halve or Subtract One Steps
Problem
Start from a whole number n that is zero or more. In one step, halve it if it is even, or subtract one if it is odd. Return how many steps it takes to reach zero. The number can be as large as 2 to the power 1000, so a solution that makes one recursive call per step will run past Python's default recursion limit.
Examples
Input: n = 14
Output: 6
Why: 14 -> 7 -> 6 -> 3 -> 2 -> 1 -> 0Input: n = 2 ** 1000
Output: 1001
Why: 1000 halvings reach 1, and one subtraction reaches 0Input: n = 0
Output: 0
Why: edge case, already at zero, so no steps are takenHints
0 / 3
The natural recursive answer is one plus the answer for the next number. Count how deep the call stack gets for the largest input.
Rewrite the recursion so the step counter travels along as an extra argument. Now the recursive call is the very last thing the function does.
A call that is the last action can be replaced by reassigning the arguments and jumping back to the top: a loop that updates n and the counter until n is zero.
Solution
With an accumulator, the recursion becomes a tail call: the answer for n is the answer for the next number with the counter raised by one, and nothing is left to do after the call returns. Python does not remove tail calls by itself, so the call is turned into a loop that reassigns n and the counter, and the stack never grows. The count also has a closed form for n above zero: one step per binary digit after the first, plus one per set bit. Time is O(log n) steps, and space is O(1) beyond the number itself.
def steps_to_zero(n):
# tail-recursive shape: steps(n, done) = done if n == 0 else steps(next n, done + 1)
done = 0
while n: # the tail call, as a loop
n = n // 2 if n % 2 == 0 else n - 1
done += 1
return done
print(steps_to_zero(14)) # -> 6
print(steps_to_zero(2 ** 1000)) # -> 1001
print(steps_to_zero(0)) # -> 0Stuck on the idea rather than the code? Tail Calls and Loops covers it.