Data Structures and Algorithms
Recursion
This Lecture covers:
i. Recursive definations
ii. Base case and the general
case of a recursive defination
iii. Recursive Algorithms
iv. Reccursive Functions
v. Use of recursive functions
to implement recursive algorithms
Recursion Data Structures and Algorithms May 15th, 2021 1 / 13
Outlines
Recursion
Properties of a Recursive Definition
Recursive Algorithm and Recursive Functions
Direct and Indirect Recursion
Designing a Recursive Algorithms General Steps
Exercise on recursive functions
Recursion Data Structures and Algorithms May 15th, 2021 2 / 13
Introduction to recursion
In previous topics, to devise solu-
tions to problems we used the most common technique, called iteration
For certain problems, however,
using the iterative technique to obtain the solution is quite complicated
This chapter introduces another problem solving technique, called
recursion, and provides some examples demonstrating how recursion
works.
Recursion Data Structures and Algorithms May 15th, 2021 3 / 13
Recursive Definitions
The process of solving a problem by reducing it to smaller versions of
itself is called recursion. Recursion is a very powerful way to solve
certain problems for which the solution would otherwise be very
complicated.
In an algebra course, you probably learned how to find the factorial of
a non-negative integer. For example, the factorial of 5, written 5!, =
5 × 4 × 3 × 2 × 1 = 120. Similarly, 4! = 4 × 3 × 2 × 1 = 24. Also,
factorial of 0 is defined to be 0! = 1. Note that
5! = 5 × 4 × 3 × 2 × 1 = 5 × (4 × 3 × 2 × 1) = 5 × 4!. In general, if n
is a nonnegative, the factorial of n, written as n! can be defined as
follows:
0! = 1 (1)
n! = n × (n − 1)!if , n > 0 (2)
Recursion Data Structures and Algorithms May 15th, 2021 4 / 13
Recursive Definitions... II
In this definition, 0! is defined to be 1, and if n is an integer greater
than 0, first we find (n × 1)! and then multiply it by n. To find
(n × 1)!, we apply the definition again. If (n × 1) > 0, then we use
Equation 2; otherwise, we use Equation 1. Thus, for an integer n
greater than 0, n! is obtained by first finding (n × 1)! and then
multiplying (n × 1)! by n.
The solution in Equation 1 is direct—that is, the right side of the
equation contains no factorial notation. The solution in Equation 2 is
given in terms of a smaller version of itself. The definition of the
factorial given in Equations 6-1 and 6-2 is called a recursive
definition. Equation 1 is called the base case (that is, the case for
which the solution is obtained directly); Equation 2 is called the
general case.
Recursion Data Structures and Algorithms May 15th, 2021 5 / 13
Properties of a Recursive Definition
Recursive definition: A definition in which something is defined in terms
of a smaller version of itself.
1 Every recursive definition must have one (or more) base cases.
2 The general case must eventually be reduced to a base case.
3 The base case stops the recursion.
Recursion Data Structures and Algorithms May 15th, 2021 6 / 13
Recursive Algorithm and Recursive Functions
An algorithm that finds the solution to a given problem by reducing
the problem to smaller versions of itself is called a recursive
algorithm. The recursive algorithm must have one or more base
cases, and the general solution must eventually be reduced to a base
case.
A function that calls itself is called a recursive function. That is, the
body of the recursive function contains a statement that causes the
same function to execute again before completing the current call.
Recursive algorithms are implemented using recursive functions.
Recursion Data Structures and Algorithms May 15th, 2021 7 / 13
Recursive function that implements the factorial function
cout ¡¡ fact(3) ¡¡ endl;
The execution of the above following statement.
Recursion Data Structures and Algorithms May 15th, 2021 8 / 13
Execution of fact(3)
The down arrow represents the successive calls to the function fact, and
the upward arrows represent the values returned to the caller, that is, the
calling function.
Recursion Data Structures and Algorithms May 15th, 2021 9 / 13
Note the following from the above example
Recursion Data Structures and Algorithms May 15th, 2021 10 / 13
Direct and Indirect Recursion
1 A function is called directly recursive if it calls itself. A function
that calls another function and eventually results in the original
function call is said to be indirectly recursive.
2 For example, if a function A calls a function B and function B calls
function A, then function A is indirectly recursive. Indirect recursion
can be several layers deep. For example, suppose that function A calls
function B, function B calls function C, function C calls function D,
and function D calls function A. Function A is then indirectly recursive.
3 Indirect recursion requires the same careful analysis as direct
recursion.
Recursion Data Structures and Algorithms May 15th, 2021 11 / 13
Designing a Recursive Algorithms General Steps
Recursion Data Structures and Algorithms May 15th, 2021 12 / 13
Exercise on recursive functions
Write a recursive algorithm to determine the Fibonacci sequence
Write a recursive function that implements the Fibonacci Sequence
Write a recursive algorithm that solves the Tower of Hanoi disk
displacement problem
Recursion Data Structures and Algorithms May 15th, 2021 13 / 13
