Time complexity of listing all paths down stairs?

Question

I am unable to determine the time complexity of a backtracking solution for the climbing stairs problem which states

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Input: 2

Output: 2

Explanation: There are two ways to climb to the top.

1. 1 step + 1 step
2. 2 steps

My algorithm:

input = [1, 2]
output = set()
n = 4
def helper(temp):
    if sum(temp) == n:
        output.add(tuple(temp))
    elif sum(temp) > n:
        return
    else:
        for i in input:
            helper(temp + [i])
helper([])

print(output)

Output for n = 4:

{(1, 2, 1), (2, 1, 1), (1, 1, 2), (2, 2), (1, 1, 1, 1)}

Answer 1

This function's runtime is the unusual Θ(n · φⁿ), where φ is the golden ratio, (1 + √5) / 2.

To see why this is, let's talk about how to analyze the code that you've written. Imagine the recursion tree for this code. (That's the tree with one node for each recursive call made). Notice that each recursive call branches - there's one call to a subproblem of size n - 1 and one subcall to a problem of size n - 2. In any tree where each internal node is branching, the number of total nodes is at most twice the number of leaves. And in your case, there's one leaf for each solution found, plus some additional leaves for when the recursion overshoots the value of n. (For now, we'll ignore that second group, but we'll talk about why that is later on.) This means that the total number of recursive calls is (with the previous caveat addressed later) at most twice the number of paths down stairs.

So how many solutions are there to this problem? Turns out, the number of solutions for a staircase of height n is exactly equal to the nth Fibonacci number, and the nth Fibonacci number happens to be Θ(φⁿ). So that means that there are a total of Θ(φⁿ) total recursive calls made.

So how much work do those recursive calls take? We can conservatively upper-bound each recursive call's work at O(n), since in the worst case summing up the list adds up 1 + 1 + 1 + ... + 1 n times. But we can also lower-bound the work done at the leaves, where the work is greatest, at Ω(n) because in the best case we add up 2 + 2 + ... + 2 a total of n / 2 times.

Overall, we have Θ(φⁿ) calls, of which the bottom ones do Θ(n) work each, for a total of Θ(n · φⁿ) work.

There's one last detail to address - what about the recursive calls that "overshoot" and add up to something bigger than n? Turns out, there's also O(φⁿ) of these as well. One way to see this is that the number of ways of overshooting to hit n + 1 is at most the number of solutions to listing all paths of size n + 1, and there's O(φⁿ) of these. So adding these back in doesn't change anything.

Hope this helps!