Page 38 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 3: Recursion

A recursive procedure or routine is one that has the ability to call itself. This usually Notes
means that it has the capability to save the condition it was in or the particular process it
is serving when it calls itself (otherwise, any variable values that have been developed in
executing the code are overlaid by the next iteration or go-through).

Did u know? Typically, this is done by saving values in registers or data area stacks before
calling itself or at the beginning of the sequence where it has just been reentered.
A recursive expression is a function, algorithm, or sequence of instructions (typically, an
IF, THEN, ELSE sequence) that loops back to the beginning of itself until it detects that
some condition has been satisfied.

3.1.1 Advantages of Recursion

Recursion is more elegant and requires few variables which make program clean.
Recursion can be used to replace complex nesting code by dividing the problem into same
problem of its sub-type.
Recursion may provide a simpler solution than an iterative one. Sometimes iterative
solutions lend themselves to complex algorithms.
It may lead to reduction in code size.

3.1.2 Disadvantages of Recursion

It is hard to think the logic of a recursive function.
It is also difficult to debug the code containing recursion.

It may require large amounts of memory.
3.1.3 Significance of Recursion

Given that recursion is in general less efficient, why would we use it? There are two situations
where recursion is the best solution:
The problem is much more clearly solved using recursion: there are many problems
where the recursive solution is clearer, cleaner, and much more understandable.

!

Caution As long as the efficiency is not the primary concern, or if the efficiencies of the
various solutions are comparable, then you should use the recursive solution.
Some problems are much easier to solve through recursion: there are some problems
which do not have an easy iterative solution. Here you should use recursion.

Example: The Towers of Hanoi problem is an example of a problem where an iterative
solution would be very difficult. We’ll look at Towers of Hanoi in a later section of this guide.

Task Analyze the applications of recursion.

LOVELY PROFESSIONAL UNIVERSITY 31