TABLE OF CONTENTS We can use recursion as an alternative to iteration. Solutions to some problems can be naturally expressed using recursion. We start this chapter with an overview of recursive procedures. Next we give some example recursive procedures in the MIPS assembly language. The advantages and pitfalls associated with a recursive solution as opposed to an iterative solution are discussed towards the end of the chapter.
A recursive procedure calls itself, either directly or indirectly through another procedure. In direct recursion, a procedure calls itself directly. In indirect recursion, procedure P makes a call to procedure Q, which in turn calls procedure P. The sequence of calls could be longer before a call is made to procedure P.
Recursion is a powerful tool that allows us to express our solution elegantly. Some solutions can be naturally expressed using recursion. Computing factorials is a classic example. Factorial n, denoted n!, is the product of positive integers from 1 to n. For example,
The factorial function can be formally defined as
Recursion shows up in this definition as we define factorial( n) in terms of factorial( n - 1).Every recursive function should have a termination condition to end the recursion. In this example, when n = 0, recursion stops. Some other examples include the binary search, quicksort, and Fibonacci function. Towards the end of this chapter, we give examples of quicksort and the Fibonacci function.
How do we express such recursive functions in programming languages? Let us first...
