Lecture 6: Recursion and Dictionaries

Recursion

process of repeating items in a self-similar way

What is Recursion (Algorithmically/Abstractly)

a way to design solutions to problems by divide-and-conquer or decrease-and-conquer; reduce a problem to simpler versions of the same problem

What is Recursion (semantically)

a programming technique where a function calls itself

How to make sure not to have infinite recursion in programming

• must have 1 or more base cases that are easy to solve

• must solve the same problem on some other input with the goal of simplifying the larger problem input

Recap of Iterative Algorithms

• looping constructs (while and for loops) lead to iterative algorithms

• can capture computation in a set of state variables that update on each iteration through loop

Iteration vs Recursion

• Recursion may be simpler, more intuitive

• Recursion may be more efficient from Programmer POV

• Recursion may not be efficient from Computer POV

Mathematical Induction

To prove a statement indexed on integers is true for all values of n if can prove it’s true when n is smallest value and then prove that if it’s true for an arbitrary value of n, one can show that it must be true for n+1

Divide and Conquer Algorithm

Solve a hard problem by breaking it into a set of sub-problems such that sub-problems are easier to solve than the original and solutions of the sub-problems can be combined to solve the original.

Python Dictionary

Mutable compound data type that stores pairs (keys and values) of data

Dictionary lookup

similar to indexing a list; looks up the key then returns the value associated with the key; if key isn’t found, gets an error

Dict[new key] = new value

add an entry to dictionary

“Key” in dictionary

test if key in dictionary (either returns a True or False value)

del(Dict[Key])

delete an entry in dictionary

Dict.keys()

gets an iterable that acts like a tuple of keys (no guaranteed order)

Dict.values()

gets an iterable that acts like a tuple of values (no guaranteed order)

Dictionary values

any type (immutable and mutable); can be duplicates, lists, and even other dictionaries

Dictionary Keys

must be unique; immutable/hashable type (int, float(challenging), string, tuple, bool)

list vs dict