Recursion is an algorithm design technique, closely related to induction.

**Recursion**

Recursion is an algorithm design
technique, closely related to induction. It is similar to iteration, but more
powerful. Using recursion, we can solve a problem with a given input, by
solving the instances of the problem with a part of the input.

**Example 8.10. **Customers are waiting in a** **line at a counter. The man at the
counter wants to know how many customers are waiting in the line.

Instead of counting the length
himself, he asks customer A for the length of the line with him at the head,
customer A asks customer B for the length of the line with customer B at the
head, and so on. When the query reaches the last customer in the line, E, since
there is no one behind him, he replies 1 to D who asked him. D replies 1+1 = 2
to C, C replies 1+2 = 3 to B, B replies 1+3 = 4 to A, and A replies 1+4= 5 to
the man in the counter

**Example 8.10 **illustrates a recursive** **process. Let us represent the
sequence of 5 customers A, B, C, D and E as

**[A,B,C,D,E]**

The problem is to calculate the
length of the sequence [A,B,C,D,E]. Let us name our solver length. If we pass a
sequence as input, the solver length should output the length of the sequence.

**length [A,B,C,D,E] = 5**

Solver length breaks the sequence
[A,B,C,D,E] into its first customer and the rest of the sequence.

**first [A ,B,C,D,E] = A**

**rest [A ,B,C,D,E] = [B ,C,D,E]**

To solve a problem recursively,
solver length passes the reduced sequence [B,C,D,E] as input to a sub-solver,
which is another instance of length. The solver assumes that the sub-solver
outputs the length of [B,C,D,E], adds 1, and outputs it as the length of
[A,B,C,D,E].

**length [A,B,C,D,E] = 1 + length [B,C,D,E]**

**Each solver**

1.
receives
an input,

2.
passes
an input of reduced size to a sub-solver,

3. receives the solution to the reduced input from the sub-solver, and produces the solution for the given input as illustrated in Figure 8.5.

Figure 8.6 shows the input
received and the solution produced by each solver for Example 8.10. Each solver
reduces the size of the input by one and passes it on to a sub-solver,
resulting in 5 solvers. This continues until the input received by a solver is
small enough to output the solution directly. The last solver received [E] as
the input. Since [E] is small enough, the solver outputs the length of [E] as 1
immediately, and the recursion stops.

The recursive process for length
[A,B,C,D,E] is shown in Figure 8.7.

1 length [A,B,C,D,E]

2= 1 + 1 length [B,C,D,E]

3= 1 +1 + length [C,D,E]

4= 1 + 1+ 1 + length [D,E]

5= 1 + 1+ 1 + 1 + length [E]

6= 1 + 1 + 1 + 1 +1

7= 1 +1 +1 + 2

8= 1 + 1 + 3

9= 1 + 4

10 = 5

*Figure
8.7: Recursive process for computing the length of a sequence*

Each solver should test the size
of the input. If the size is small enough, the solver should output the
solution to the problem directly. If the size is not small enough, the solver
should reduce the size of the input and call a sub-solver to solve the problem
with the reduced input. For Example 8.10, solver's algorithm can be expressed
as length of sequesce.

To solve a problem recursively,
the solver reduces the problem to sub-problems, and calls another instance of the
solver, known as sub-solver, to solve the sub-problem. The input size to a
sub-problem is smaller than the input size to the original problem. When the
solver calls a sub-solver, it is known as recursive call. The magic of
recursion allows the solver to assume that the sub-solver (recursive call)
outputs the solution to the sub-problem. Then, from the solution to the
sub-problem, the solver constructs the solution to the given problem.

As the sub-solvers go on reducing
the problem into sub-problems of smaller sizes, eventually the sub-problem
becomes small enough to be solved directly, without recursion. Therefore, a
recursive solver has two cases:

**1.
****Base case: **The problem size is small** **enough
to be solved directly. Output the solution. There must be at least one base
case.

**2.
****Recursion step: **The problem size is** **not
small enough. Deconstruct the problem into a sub-problem, strictly smaller in
size than the given problem. Call a sub-solver to solve the sub-problem. Assume
that the sub-solver outputs the solution to the sub-problem. Construct the
solution to the given problem.

This outline of recursive problem
solving technique is shown below.

**solver (input)**

**if input is small enough**

**construct solution **

**else **

**find sub_problems of reduced **

**input **

**solutions to sub_problems = **

**solver for each sub_problem **

**construct solution to the 2 × 16**

**problem from **

**solutions to the sub_problems**

**Problems**

Whenever we solve a problem using
recursion, we have to ensure these two cases: In the recursion step, the size
of the input to the recursive call is strictly smaller than the size of the
given input, and there is at least one base case.

**3. Recursion — Examples**

**Example 8.11. **The recursive algorithm** **for length of a sequence can be
written as

length (s)

--inputs : s

--outputs : length of s

if s has one customer -- base case
1

else

1 + length(tail(s)) -- recursion
step

**Example 8.12. **Design a recursive** **algorithm to compute a^{n}.
We constructed an iterative algorithm to compute a^{n} in Example 8.5.
a^{n} can be defined recursively as

The recursive process with solvers for calculating power(2, 5) is shown in Figure 8.8.

The recursive process resulting
from power(2, 5) is shown in Figure 8.9*.*

power (2,5)

=2 × power (2,4)

=2 × 2 × power(2,3)

=2 × 2 × 2 × power(2, 2)

=2 × 2 × 2 × 2 × power (2,1)

=2 × 2 × 2 × 2 × 2 × power (2,0)

=2 × 2 × 2 × 2 × 2 × 1

=2 × 2 × 2 × 2 × 2

=2 × 2 × 2 × 4

=2 × 2 × 8

=2 × 16

=32

*Figure
8.9: Recursive process for power(2, 5)*

**Example 8.13. **A corner-covered board is a** **board of 2^{n} × 2^{n}
squares in which the square at one corner is covered with a single square tile.
A triominoe is a L-shaped tile formed with three adjacent squares (see Figure
8.10). Cover the corner-covered board with the L-shaped triominoes without
overlap. Triominoes can be rotated as needed.

The size of the problem is n
(board of size 2^{n} × 2^{n}). We can solve the problem by
recursion. The base case is n = 1. It is a 2 × 2 corner-covered board. We can
cover it with one triominoe and solve the problem. In the recursion step,
divide the corner-covered board of size 2^{n} × 2^{n} into 4
sub-boards, each of size 2^{n-1} × 2^{n-1}, by drawing
horizontal and vertical lines through the centre of the board. Place atriominoe
at the center of the entire board so as to not cover the corner-covered
sub-board, as shown in the left-most board of Figure 8.11. Now, we have four
corner-covered boards, each of size 2^{n-1} × 2^{n-1}.

We have 4 sub-problems whose size
is strictly smaller than the size of the given problem. We can solve each of
the sub-problems recursively.

tile corner_covered board of size
n

if n = 1 -- base case

cover the
3 squares with
one

triominoe

else -- recursion step

divide board into 4 sub_boards of
size n-1

place a triominoe at centre of
board ,

leaving out the corner_covered sub

-board

tile each sub_board of size n-1

The resulting recursive process
for covering a 2^{3} x 2^{3} corner-covered board is illus*trated in Figure 8.11.*

Tags : Computer Science , 11th Computer Science : Chapter 8 : Iteration and recursion

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

11th Computer Science : Chapter 8 : Iteration and recursion : Recursion | Computer Science

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.