Recursive Fibonacci, Subtractive GCD, and Integer Powers

All flashcards

How is a Fibonacci number defined recursively?

The base cases are $F(0)=0$ and $F(1)=1$. For $n>1$, $F(n)=F(n-1)+F(n-2)$.

What is a recursion tree?

A trace of the calls made as recursion branches into smaller calls; it can reveal repeated calculations.

How does the subtractive GCD method work?

For two positive integers, subtract the smaller from the larger and repeat. When they are equal, that value is the GCD.

What base case can a recursive power function use?

Use $x^0=1$. For a positive exponent, calculate $x^y$ as $x\cdot x^{y-1}$ until the exponent reaches zero.

How can a recursive power function handle a negative exponent?

For nonzero $x$, use $x^{-k}=1/x^k$: calculate the positive power recursively and return its reciprocal. Zero cannot be raised to a negative exponent.

Quiz questions

1. What are the two base cases in the recursive definition of the Fibonacci sequence?Answer: $F(0)=0$ and $F(1)=1$
2. What does a recursion tree show?Answer: The calls made as recursion branches into smaller calls.
3. Why can simple recursive Fibonacci be inefficient for large inputs?Answer: It recalculates some Fibonacci values in multiple branches.
4. In the subtractive GCD method, what is returned when two positive inputs become equal?Answer: Their common value, which is their greatest common divisor.
5. What value does `rec_pow(2, -4)` return?Answer: $1/16$