2.2.1 programming techniques

Question 1

what is recursion?

Answer 1

a function that calls on itself
it has a terminating/base case
it also has a general case

Question 2

how do you convert a recursive algorithm to an iterative algorithm?

Answer 2

• the opposite of the base case is used for the while loop condition
• the parameters in the recursive calls of the function are set as changing the variables

Question 3

what are the advantages of recursive algorithms?

Answer 3

• uses less lines of code
• well suited to certain problems/elegant solution

Question 4

what are some disadvantages of recursive algorithms?

Answer 4

• risk of stack overflow
• uses more memory

Question 5

how can you trace through a recursive algorithm?

Answer 5

1. use a table (if provided) and write each function call, the value of the parameters and the return
2. write each line of code and write the decisions (true/false) next to it. Then do this for the next call of the function with the correct values. finally, write the return values of each instance of the function call

Question 6

What are some examples of recursive algorithms?

Answer 6

• merge sort
• binary tree search
• calculating factorials