Page 45 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes Self Assessment

Fill in the blanks:
7. A ....................... is a function that calls itself during its execution.
8. If you are using Turbo C/C++ compiler then you need to press Ctrl + Break key to break
in ....................... loop.
9. The function ....................... uses recursion to count from any number to any other number.
10. Recursive functions can cause ....................... loops and other unexpected results if not written
properly.
11. If proper cases are not included in the function to stop the......................., the recursion will
repeat forever.

12. The speed of a recursive program is slower because of ....................... .
13. Every recursive function must be provided with a way to ....................... the recursion.
14. Positive integers are known as ....................... .

15. ....................... function stores the first letter entered by user and stores in variable c.

Case Study Recursive Functions

e’re going to implement a recursive function in MIPS. Recursion is one of those
programming concepts that seem to scare students. One reason is that recursive
Wfunctions can be difficult to trace properly without knowing something about
how a stack works.

”Classic” recursion attempts to solve a “big” problem by solving smaller versions of the
problem, then using the solutions to the smaller versions of the problem to solve the big
problem.
”Classic” recursion is a divide-and-conquer method. For example, consider merge sorting.
The idea behind merge sorting is to divide an array into two halves, and sort each half.
Then, you “merge” the two sorted halves to sort the entire list.
Thus, to solve the big problem of sorting an array, solve the smaller problem of sorting
part of an array, and use the solution of the smaller sorted array to solve the big problem
(by merging).
How do you solve the smaller version of the problem? You break that smaller problem
into even smaller problems, and solve those.
Eventually, you get to the smallest sized problem, which is called the base case. This can be
solved without using recursion.
Recursion allows you to express solutions to a problem very compactly and elegantly.
This is why people like using recursion.

However, recursion can use a lot of stack, and if you’re not careful, you can overflow the
stack.

Contd...

38 LOVELY PROFESSIONAL UNIVERSITY