Recursion

Question 1

Recursive Mindset

Answer 1

1. no for/while loops
2. no list comprehensions
3. no builtins like min, sum, len
4. have def and return

Question 2

Elements of recursion

Answer 2

• solve problem in divide and conquer manner
  1. recursive function call(s) on smaller inputs
  2. reachable base case to ensure calculation halts
• based on solving smaller instances of the same big problem

Question 3

Linear search

Answer 3

• match element to be searched with entire list of elements

- brute force

Question 4

Binary search

Answer 4

• used to find item in ordered list

- search sorted array by repeatedly dividing search interval in half

Question 5

When to use recursion

Answer 5

when number of loops cannot be determined beforehand

Question 6

Head recursion

Answer 6

Recurse then local calculation

Question 7

Tail recursion

Answer 7

Local calculation then recurse