Page 157 - DCAP407_DATA_STRUCTURE

Data Structure

Let us consider a real life problem and analyze how recursion can be used to solve it.

Figure 9.1: A Multi-Story Building

Figure 9.1 depicts a multi-story building. When a ten story building is built, nine stories are first built,
and then an extra story is added. Similarly, to construct nine stories, the builder first needs to build
eight stories and then add an extra story. We can generalize and say that to build an n-story building, n-
1 stories need to be built and then one more story must be added. This is a simple example of recursion.
This is like saying, “build story” function considers an n-story building and if the value of ‘n’ is greater
than one, it first calls itself to build a lower story and then adds one to build the higher ones.
Recursion is a function that directly or indirectly invokes an instance of itself. In C language, almost all
the library functions can be used recursively. Recursion is considered to be an advanced kind of control
flow.
Recursive algorithms are mainly used for manipulating data structures, which are defined recursively.
When a data object is recursively defined, it is easy to state algorithms that work recursively on such
objects. Although some languages like BASIC and COBOL do not have the facility to provide recursion,
all the latest programming languages use recursion as their basic iterative control structure.
If our programming language does not permit recursion, it should not matter as we can easily translate
a recursive program into a nonrecursive one. Recursion is an inherent property of C language. This unit
helps you in understanding how recursion can be implemented using C language.
This unit explains the concept of recursion, which is a problem solving technique. It provides various
examples and explanation to design and understand recursion.

Did you know? Recursion is a familiar concept in Mathematics and Logic. For instance, the natural
numbers are defined recursively as follows:
‘0’ is a natural number
If ‘n’ is a natural number, then s(n) = (n+1) is a natural number, wherein, ‘s’ is a
successor function. In this context, recursion is closely related to mathematical
induction.
It also discusses about recursive call and complexity issues. It also describes the difference between
iteration and recursion.
9.1 Fundamentals of Recursion
The ability of a function to call itself is called recursion. Recursion is an essential concept in Computer
Science. Recursion makes it convenient to solve various problems that would be cumbersome to solve
using iterative constructs such as for, while, and do while.

150 LOVELY PROFESSIONAL UNIVERSITY