cs126 recursion

What is a recursion base case?

Values of the input variables for which we perform no recursive call.

What is a recursive call?

A call to a recursive method inside the method.

What are the two rules for a recursive method?

• Every possible chain of recursive calls must eventually reach a base case.

• Each call should be defined so that it progresses towards a base case.

Define tail recursion.

• When a linearly recursive method makes its recursive call as its last step 

• e.g. reverse_array()

What is the cost of reversing the order of an array using linear recursion?

ϴ(n)

What is the cost of running the recursive factorial algorithm?

ϴ(n)

What is the cost of running the recursive Fibonacci algorithm?

O(2ⁿ)

Define a fractal.

• A geometric figure that can be divided into parts

• Each of which is a reduced-size copy of the whole figure

• e.g. the Sierpinski Triangle