Page 40 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 3: Recursion

Notes

Notes If you are using Turbo C/C++ compiler then you need to press Ctrl + Break key to
break this in definite loop.
Let us consider another example:

Example:
Below is an example of a recursive function.
function Count (integer N)
if (N <= 0) return “Must be a Positive Integer”;
if (N > 9) return “Counting Completed”;
else return Count (N+1);
end function

The function Count() above uses recursion to count from any number between 1 and 9, to the
number 10. For example, Count(1) would return 2,3,4,5,6,7,8,9,10. Count(7) would return 8,9,10.
The result could be used as a roundabout way to subtract the number from 10.
Recursive functions are common in computer science because they allow programmers to write
efficient programs using a minimal amount of code. The downside is that they can cause infinite
loops and other unexpected results if not written properly.

Example: In the example above, the function is terminated if the number is 0 or less or
greater than 9.

Notes If proper cases are not included in the function to stop the execution, the recursion
will repeat forever, causing the program to crash, or worse yet, hang the entire computer
system.
Before we move to another example lets have attributes of “recursive function”:-

A recursive function is a function which calls itself.
The speed of a recursive program is slower because of stack overheads. (This attribute is
evident if you run above C program.)

A recursive function must have recursive conditions, terminating conditions, and recursive
expressions.

Did u know? Every recursive function must be provided with a way to end the recursion.

Example 1: Calculating factorial value using recursion
To understand how recursion works lets have another popular example of recursion. In this
example we will calculate the factorial of n numbers. The factorial of n numbers is expressed as
a series of repetitive multiplication as shown below:
Factorial of n = n(n-1)(n-2)……1.

LOVELY PROFESSIONAL UNIVERSITY 33