The Fibonacci sequence starts with 0 and 1; each later term equals the sum of the two preceding terms. In quantum outcome selection, the same recurrence counts binary strings that contain no consecutive 1s. section 5.4
A recursive implementation mirrors the definition:
- Return n directly when n is 0 or 1. section 5.4
- Otherwise return recursive_fib(n - 1) + recursive_fib(n - 2). section 5.4
- The first ten values are 0, 1, 1, 2, 3, 5, 8, 13, 21, and 34. section 5.4
Counting valid binary outcomes
For three-bit strings, the valid outcomes are 000, 001, 010, 100, and 101. Their count is 5: strings beginning with 0 extend a valid two-bit string, while strings beginning with 1 must continue with 0 and then extend a valid one-bit string. section 5.4
def recursive_fib(n):
assert n >= 0
if n <= 1:
return n
else:
return recursive_fib(n - 1) + recursive_fib(n - 2)
Inspect the recursive Python implementation that directly encodes the two-term recurrence. section 5.4
