Recursion (Module 4)

Question 1

What is a programming technique where a method calls itself to solve a problem, and will continue to call itself until a certain condition (base case) is met?

Answer 1

recursion

Question 2

How does recursion work?

Answer 2

breaking down a problem into smaller sub-problems, then solving each sub-problem by recursively calling the method

Question 3

In recursion, what is used to keep track of method invocations?

Answer 3

stack

Question 4

What is a factorial?

Answer 4

the product of a number, n, and every number below it (6! = 6 * 5 * 4 * 3 * 2 *1)

Question 5

Let’s say that we call factorial(6). What happens to it? Then what happens if we call factorial(5)?

Answer 5

• factorial(6) is pushed to the call stack. When factorial(5) is called, it’s pushed to the top of the call stack

Question 6

What must every recursive program include a ________ case.

Answer 6

base (stopping)

Question 7

What is a condition under which a method stops making recursive calls?

Answer 7

base (stopping case)

Question 8

What happens when a a stopping case is absent?

Answer 8

infinite recursion

Question 9

What happens when infinite recursion occurs?

Answer 9

it leads to runtime errors and a stack overflow

Question 10

What formulas define a sequence in terms of previous terms in the sequence?

Answer 10

recursive formulas

Question 11

What formulas define a sequence directly, without referencing previous terms?

Answer 11

iterative formulas

Question 12

What are the advantages of recursion?

Answer 12

• it makes code shorter and cleaner
• required in data structures and advanced algorithms

Question 13

What are the disadvantages of recursion?

Answer 13

• it takes a lot of stack space (memory)
• takes more processing time
• more difficult to debug