Algorithms: Recursion

Question 1

Recursion

Answer 1

A subroutine is said to be recursive if it calls itself, either directly or indirectly. What this means is that the subroutine is used in its own definition. Recursion can often be used to solve
complex problems by reducing them to simpler problems of the same type.

Generation of factorial, Fibonacci number series are the examples of recursive algorithms.

int fact(int n)
{
    if (n < = 1) // base case
        return 1;
    else    
        return n*fact(n-1);    
}

Question 2

How a particular problem is solved using recursion?

Answer 2

The idea is to represent a problem in terms of one or more smaller problems, and add one or more base conditions that stop the recursion. For example, we compute factorial n if we know factorial of (n-1). The base case for factorial would be n = 0. We return 1 when n = 0.

Question 3

Why Stack Overflow error occurs in recursion?

Answer 3

If the base case is not reached or not defined, then the stack overflow problem may arise. Let us take an example to understand this.

Question 4

2 keys or rules to succesful recursion

Answer 4

The key to using recursion successfully is to note two things that must be true for recursion to work properly:

1. There must be one or more base cases, which can be handled without using recursion.
2. When recursion is applied during the solution of a problem, it must be applied to a problem that is in some sense smaller – that is, closer to the base cases – than the original problem. The idea is that if you can solve small problems and if you can reduce big problems to smaller problems, then you can solve problems of any size.

Question 5

What happens when the 2 rules of recursion are violated?

Answer 5

If these rules are violated, the result can be an infinite recursion, where the subroutine keeps calling itself over and over, without ever reaching a base case. In Java, the program will crash with an exception of type StackOverflowError.

Question 6

Examples of Recursion?

Answer 6

Towers of Hanoi
QuickSort
Blob Counting
Binary Search

Question 7

What is a recursive definition?

Answer 7

A recursive definition is one that uses the concept or thing that is being defined as part of the definition. For example: An “ancestor” is either a parent or an ancestor of a parent. A “sentence” can be, among other things, two sentences
joined by a conjunction such as “and.” A “directory” is a part of a disk drive that can hold files and directories. In mathematics, a “set” is a collection of elements, which can themselves be
sets. A “statement” in Java can be a while statement, which is made up of the word “while”, a boolean-valued condition, and a statement.

Question 8

Direct and indirect recursion

Answer 8

Recursion can be used as a programming technique. A recursive subroutine (or recursive
method) is one that calls itself, either directly or indirectly. To say that a subroutine calls itself
directly means that its definition contains a subroutine call statement that calls the subroutine
that is being defined. To say that a subroutine calls itself indirectly means that it calls a second
subroutine which in turn calls the first subroutine (either directly or indirectly).

Question 9

Advantages of Recursion?

Answer 9

Less code - A subroutine can define a complex task in just a few lines of code.

Question 10

Base case

Answer 10

A base case for a recursive

algorithm is a case that is handled directly, rather than by applying the algorithm recursively.