*Recursion*

Question 1

Recursive method

Answer 1

A method that calls itself

Question 2

Depth of recursion

Answer 2

The number of times that a method calls itself

Question 3

When can problems be solved with recursion?

Answer 3

A problem can be solved with recursion if it can be broken down into successive smaller problems that are identical to the overall problem.

Question 4

How efficient are recursive algorithms?

Answer 4

They are usually less efficient than iterative algorithms (i.e. using a loop). This is because a method call requires several actions to be performed by the JVM such as allocating memory for parameters and local variables and storing the address of the program location where control returns after the method terminates. These actions, often known as “overhead”, are not necessary with a loop.

Question 5

Direct recursion

Answer 5

Methods that directly call themselves

Question 6

Indirect recursion

Answer 6

A method (A) that calls another method (B) which in turn calls the first method (A). There can even be several methods involved in the recursion. For example, method A could call method B, which could call method C, which calls method A.

Question 7

Why would you use a recursive method if an iterative algorithm executed faster?

Answer 7

The programmer may be able to design a recursive algorithm faster.

Question 8

How does a recursive method work?

Answer 8

If the problem can be solved now, without recursion, then the method solves it and returns (base case). If the problem cannot be solved now, then the method reduces it to a smaller but similar problem and calls itself to solve the smaller problem. Usually a problem is reduced by making the value of one or more parameters smaller with each recursive call (i.e. counts down to zero).

Question 9

What are a few problems that can be solved with recursion?

Answer 9

Calculating the factorial of a number, summing a range of array elements, drawing concentric circles, or finding the greatest common divisor.

Question 10

What happens if you forget to code a base case?

Answer 10

When the base case is reached a recursive method stops calling itself. Without a base case a method will call itself infinitely!

Question 11

Can there be more than 1 base base in a recursive method?

Answer 11

Yes! There are two in the following method to calculate the values of n numbers in a Fibonacci series: public static int fib(int n) { if (n == 0) return 0; else if (n == 1) return 1; else return fib(n - 1) + fib(n - 2); }