This notebook was prepared by Donne Martin. Source and license info is on GitHub.

# Solution Notebook¶

## Constraints¶

• Does the sequence start at 0 or 1?
• 0
• Can we assume the inputs are valid non-negative ints?
• Yes
• Are you looking for a recursive or iterative solution?
• Either
• Can we assume this fits memory?
• Yes

## Test Cases¶

• n = 0 -> 0
• n = 1 -> 1
• n = 6 -> 8
• Fib sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34...

## Algorithm¶

Recursive:

• Fibonacci is as follows: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34...
• If n = 0 or 1, return n
• Else return fib(n-1) + fib(n-2)

Complexity:

• Time: O(2^n) if recursive or iterative, O(n) if dynamic
• Space: O(n) if recursive, O(1) if iterative, O(n) if dynamic

## Code¶

In [1]:
class Math(object):

def fib_iterative(self, n):
a = 0
b = 1
for _ in range(n):
a, b = b, a + b
return a

def fib_recursive(self, n):
if n == 0 or n == 1:
return n
else:
return self.fib_recursive(n-1) + self.fib_recursive(n-2)

def fib_dynamic(self, n):
cache = {}
return self._fib_dynamic(n, cache)

def _fib_dynamic(self, n, cache):
if n == 0 or n == 1:
return n
if n in cache:
return cache[n]
cache[n] = self._fib_dynamic(n-1, cache) + self._fib_dynamic(n-2, cache)
return cache[n]


## Unit Test¶

In [2]:
%%writefile test_fibonacci.py
import unittest

class TestFib(unittest.TestCase):

def test_fib(self, func):
result = []
expected = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
for i in range(len(expected)):
result.append(func(i))
self.assertEqual(result, expected)
print('Success: test_fib')

def main():
test = TestFib()
math = Math()
test.test_fib(math.fib_recursive)
test.test_fib(math.fib_dynamic)
test.test_fib(math.fib_iterative)

if __name__ == '__main__':
main()

Overwriting test_fibonacci.py

In [3]:
%run -i test_fibonacci.py

Success: test_fib
Success: test_fib
Success: test_fib
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://nbviewer.ipython.org/github/donnemartin/interactive-coding-challenges/blob/master/recursion_dynamic/fibonacci/fibonacci_solution.ipynb", "fetch_time": 1653306696000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2022-21/segments/1652662558015.52/warc/CC-MAIN-20220523101705-20220523131705-00508.warc.gz", "warc_record_offset": 475755410, "warc_record_length": 5406, "token_count": 622, "char_count": 1832, "score": 3.71875, "int_score": 4, "crawl": "CC-MAIN-2022-21", "snapshot_type": "latest", "language": "en", "language_score": 0.477594256401062, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00012-of-00064.parquet"}