# Recursion Review

1.  How does the System stack impact the Big-O of a recursive solution?
1.  Why can recursion be an attractive technique to use in solving a problem?
1.  Is there any situation you can solve with recursion and **can't** solve with a loop?
1.  The Fibonacci Sequence is defined as follows:

`fib(0) = 0, fib(1) = 1, fib(n) = fib(n-1) + fib(n-2) for all n > 0`

Write that sequence as a recursive method.

```ruby
def fib(n)
  # your code here


end
```

5.  What's the time & space complexity of the above method?
