AP CSA Recursion 2

Question 1

How many times is the base case reached when computing factorial(3) recursively?

Accepted Answer

1

Answer

factorial(3) calls factorial(2) which calls factorial(1) which calls factorial(0) — the base case is reached exactly once.

Question 2

What is the time complexity of a simple linear recursion that calls itself once per step from n down to 0?

Accepted Answer

O(n)

Answer

A recursion that makes one call per level and counts down from n to 0 executes n+1 calls, giving O(n) time complexity.

Question 3

In the Fibonacci sequence defined recursively as fib(n)=fib(n-1)+fib(n-2), what are the base cases?

Accepted Answer

fib(0)=0 and fib(1)=1

Answer

The standard recursive Fibonacci has two base cases: fib(0)=0 and fib(1)=1, terminating the recursion.

Question 4

What is the output of: `public void count(int n){ if(n==0) return; System.out.print(n+" "); count(n-1); }` called with count(3)?

Accepted Answer

3 2 1

Answer

count(3) prints 3, then calls count(2) which prints 2, then count(1) which prints 1, then count(0) returns.

Question 5

What is the output if `System.out.print(n+" ");` is moved AFTER `count(n-1);` in the previous question?

Accepted Answer

1 2 3

Answer

When the print is after the recursive call, execution prints on the way back up the call stack, giving ascending order.

AP CSA - Advanced Placement Computer Science A Practice Test