Page 180 - DCAP407_DATA_STRUCTURE

Unit 9: Recursion

declared. Then variable ‘j’ and ‘prod’ (int n), the function prototype is
are defined as integer. And prod is declared. If the value of ‘n’ entered is
assigned a value ‘1’. prod = ‘0’, then value ‘1’ is returned.
(prod * j) is calculated until the value Otherwise, (n*factorial (n-1)) value is
of ‘j’ is lesser than the value of ‘n’. returned until the value of ‘n’ becomes
Finally, the program returns the value zero.
of ‘prod’.
Iterative functions can be designed Every time a function is invoked, all
easily. They occupy less memory and the formal parameters, local variables,
execute much faster. and return address are pushed onto
the stack. Therefore, it occupies more
space in the stack and more time is
consumed in pushing and popping.
Hence, recursion is costly in terms of
memory usage and processor time.
Iteration is not suitable for problems Recursion is suitable for problems like
like tree traversals, Tower of Hanoi tree traversal techniques, Tower of
and so on. Although these problems Hanoi, and so on. Recursive functions
can be solved with the help of are easily understandable and efficient.
iterative functions, they are difficult to
design, time-consuming and more
error prone.

1. Write a recursive function to add the first ‘n’ natural numbers. [Hint:
(addition) = 1 + 2 + … + n]].
2. Write a recursive function to determine the sum of digits of a number that
is entered through a keyboard.
9.6 Summary

• Recursion is a function that directly or indirectly invokes an instance of itself.
• Recursion procedures solve a given problem by breaking down the problem into an instance of the
same problem.
• The two types of recursion are - direct and indirect recursion. Direct recursion is a kind of
recursion in which the function invokes itself. Indirect recursion is a kind of recursion in which
two functions invoke each other.
• Recursive function comprises two types of cases namely, base case and recursive case. Base case is
the smallest instance of the problem and its solution should not be recursive to guarantee function
termination. Recursive case comprises a recursive function call.

• Function is a block of statements that can be utilized to perform a particular task. A function is
activated only when a function call is invoked.
• Factorial, Fibonacci series and Tower of Hanoi are few examples of problems that can be solved
using recursion.
• Recursive procedures or algorithms invoke themselves. Therefore, the running time is described
using a recursive equation.

• Iterative functions can be designed easily. They occupy less memory and execute much faster,
whereas, recursion is costly in terms of memory usage and processor time.

LOVELY PROFESSIONAL UNIVERSITY 173