CS Week 9 - Recursion

Question 1

algorithm

Answer 1

a sequence of steps for solving a problem

Question 2

recursive algorithm

Answer 2

an algorithm that breaks the problem into smaller subproblems and applies the same algorithm to solve the smaller subproblems

Question 3

base case

Answer 3

how to actually do something
where the recursion ends

Question 4

recursive function

Answer 4

a function that calls itself

Question 5

creating a recursive function

Answer 5

1.write the base case
returns a value without performing a recursive call

2.write the recursive case

Question 6

a few that can be solved with recursion

Answer 6

Fibonacci sequence
greatest common divisor
binary search
finding all possible combinations
finding all possible subsets of a set of items
finding all possible paths

Question 7

stack frame

Answer 7

for local parameters, local variables, and more function items
Upon return, the frame is deleted

Question 8

stack overflow

Answer 8

meaning a stack frame extends beyond the memory region allocated for stack

Question 9

binary search

Answer 9

algorithm begins at the midpoint of the range and halves the range after each guess