Page 156 - DCAP407_DATA_STRUCTURE

Sahil Rampal, Lovely Professional University Unit 9: Recursion

Unit 9: Recursion

CONTENTS
Objectives

Introduction
9.1 Fundamentals of Recursion
9.1.1 Definition of Recursion
9.1.2 Types of Recursion
9.2 Anatomy of Recursive Call
9.3 Function Call and Recursion Examples

9.3.1 Factorial of a Number
9.3.2 Fibonacci Series
9.3.3 Tower of Hanoi
9.4 Complexity Issues
9.5 Iteration vs. Recursion
9.6 Summary
9.7 Keywords
9.8 Self Assessment

9.9 Review Questions
9.10 Further Readings
Objectives

After studying this unit, you will be able to:
• Discuss the fundamentals of recursion
• Explain the anatomy of recursive call
• Describe function call and recursion examples

• Analyze the complexity issues
• Compare iteration and recursion
Introduction

Recursion is one of the methods that can be used to solve problems related to mathematics, gaming, and
so on. The conventional problem solving methods decompose the solution into steps and execute each
step one by one. The recursive method of solving a problem breaks the problem into a smaller instance
of the same type and solves the smaller instances. High level languages implement recursion by
allowing a function to call itself.

LOVELY PROFESSIONAL UNIVERSITY 149