AP CSA Recursion 2

Question 1

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

Accepted Answer

1

Answer

3

Answer

4

Answer

0

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

O(n²)

Answer

O(log n)

Answer

O(1)

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

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

Answer

fib(1)=1 only

Answer

fib(0)=0 only

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

1 2 3

Answer

3 2 1 0

Answer

0 1 2 3

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

3 2 1

Answer

0 1 2

Answer

3 2 1 0

Question 6

Which concept does recursion naturally model when processing nested data structures like trees?

Accepted Answer

Divide and conquer

Answer

Parallel processing

Answer

Iteration

Answer

Linear search