Recursion

Question 1

Recursion

What are the 2 types of cases that all recursive algorithms must have?

Answer 1

1. Base case (return)
2. Recursive case (call the function again)

Question 2

When are recursive algorithms useful?

Answer 2

When dealing with data structures that have unknown dephs (e.g. searching through a binary tree or file system)

Question 3

What is a factorial and what is it used for?

Answer 3

Factorials determine the number of possible combinations (permutations) of n

More specifically, a factorial of n is the product of all positive integers less than or equal to n. However, it is important to remember the factorial of 0 is 1 and not 0. This is because the possible combinations of 0 is no combination which counts as a combination itself

if n = 0, n! = 1

if n >= 1, n! = n * (n-1)!

Question 4

True or False

Any iterative algorithm can be written recursively

Answer 4

True

Question 5

Code a function that computes a fibonacci sequence recursively