Page 37 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures Manmohan Sharma, Lovely Professional University

Notes Unit 3: Recursion

CONTENTS
Objectives
Introduction

3.1 Concept of Recursion
3.1.1 Advantages of Recursion
3.1.2 Disadvantages of Recursion

3.1.3 Significance of Recursion
3.2 Recursive Function
3.3 Summary
3.4 Keywords
3.5 Review Questions

3.6 Further Readings

Objectives

After studying this unit, you will be able to:

Discuss the concept of recursion
Explain recursive functions
Discuss examples of recursive functions

Introduction

Sometimes a problem is too difficult or too complex to solve because it is too big. If the problem
can be broken down into smaller versions of itself, we may be able to find a way to solve one of
these smaller versions and then be able to build up to a solution to the entire problem. This is the
idea behind recursion; recursive algorithms break down a problem into smaller pieces which
you either already know the answer to, or can solve by applying the same algorithm to each
piece, and then combining the results. Recursion turns out to be a wonderful technique for
dealing with many interesting problems. Solutions written recursively are often simple.
Recursive solutions are also often much easier to conceive of and code than their iterative
counterparts. In this unit, we will discuss the concept of recursion and recursive functions.

3.1 Concept of Recursion

A recursive definition is defined in terms of itself. Recursion is a computer programming
technique involving the use of a procedure, subroutine, function, or algorithm that calls itself in
a step having a termination condition so that successive repetitions are processed up to the
critical step where the condition is met at which time the rest of each repetition is processed
from the last one called to the first.

In computer programming, a recursion is programming that is recursive, and recursive has two
related meanings:

30 LOVELY PROFESSIONAL UNIVERSITY