Chapter 5Introduction to RecursionAnd often enough, our faith beforehand in a certain resultis the only thing that makes the result come true.— William James, The Will To Believe, 1897Objectives•To be able to define the concept of recursion as a programming strategy distinct fromother forms of algorithmic decomposition.• To recognize the paradigmatic form of a recursive function.• To understand the internal implementation of recursive calls.• To appreciate the importance of the recursive leap of faith.• To understand the concept of wrapper functions in writing recursive programs.• To be able to write and debug simple recursive functions at the level of those presentedin this chapter.Introduction to Recursion – 176 –Most algorithmic strategies used to solve programming problems have counterpartsoutside the domain of computing. When you perform a task repeatedly, you are usingiteration. When you make a decision, you exercise conditional control. Because theseoperations are familiar, most people learn to use the control statements for, while, andif with relatively little trouble.Before you can solve many sophisticated programming tasks, however, you will haveto learn to use a powerful problem-solving strategy that has few direct counterparts in thereal world. That strategy, called recursion, is defined as any solution technique in whichlarge problems are solved by reducing them to smaller problems of the same form. Theitalicized phrase is crucial to the definition, which otherwise describes the basic strategyof stepwise refinement. Both strategies involve decomposition. What makes recursionspecial is that the subproblems in a recursive solution have the same form as the originalproblem.If you are like most beginning programmers, the idea of breaking a problem down intosubproblems of the same form does not make much sense when you first hear it. Unlikerepetition or conditional testing, recursion is not a concept that comes up in day-to-daylife. Because it is unfamiliar, learning how to use recursion can be difficult. To do so,you must develop the intuition necessary to make recursion seem as natural as all theother control structures. For most students of programming, reaching that level ofunderstanding takes considerable time and practice. Even so, learning to use recursion isdefinitely worth the effort. As a problem-solving tool, recursion is so powerful that it attimes seems almost magical. In addition, using recursion often makes it possible to writecomplex programs in simple and profoundly elegant ways.5.1 A simple example of recursionTo gain a better sense of what recursion is, let’s imagine you have been appointed as thefunding coordinator for a large charitable organization that is long on volunteers andshort on cash. Your job is to raise $1,000,000 in contributions so the organization canmeet its expenses.If you know someone who is willing to write a check for the entire $1,000,000, yourjob is easy. On the other hand, you may not be lucky enough to have friends who aregenerous millionaires. In that case, you must raise the $1,000,000 in smaller amounts. Ifthe average contribution to your organization is $100, you might choose a different tack:call 10,000 friends and ask each of them for $100. But then again, you probably don’thave 10,000 friends. So what can you do?As is often the case when you are faced with a task that exceeds your own capacity, theanswer lies in delegating part of the work to others. Your organization has a reasonablesupply of volunteers. If you could find 10 dedicated supporters in different parts of thecountry and appoint them as regional coordinators, each of those 10 people could thentake responsibility for raising $100,000.Raising $100,000 is simpler than raising $1,000,000, but it hardly qualifies as easy.What should your regional coordinators do? If they adopt the same strategy, they will inturn delegate parts of the job. If they each recruit 10 fundraising volunteers, those peoplewill only have to raise $10,000. The delegation process can continue until the volunteersare able to raise the money on their own; because the average contribution is $100, thevolunteer fundraisers can probably raise $100 from a single donor, which eliminates theneed for further delegation.Introduction to Recursion – 177 –If you express this fundraising strategy in pseudocode, it has the following structure:void CollectContributions(int n) { if (n <= 100) { Collect the money from a single donor. } else { Find 10 volunteers. Get each volunteer to collect n/10 dollars. Combine the money raised by the volunteers. }}The most important thing to notice about this pseudocode translation is that the lineGet each volunteer to collect n/10 dollars.is simply the original problem reproduced at a smaller scale. The basic character of thetask—raise n dollars—remains exactly the same; the only difference is that n has asmaller value. Moreover, because the problem is the same, you can solve it by calling theoriginal function. Thus, the preceding line of pseudocode would eventually be replacedwith the following line:CollectContributions(n / 10);It’s important to note that the CollectContributions function ends up calling itself ifthe contribution level is greater than $100. In the context of programming, having afunction call itself is the defining characteristic of recursion.The structure of the CollectContributions procedure is typical of recursivefunctions. In general, the body of a recursive function has the following form:if (test for simple case) { Compute a simple solution without using recursion.} else { Break the problem down into subproblems of the same form. Solve each of the subproblems by calling this function recursively. Reassemble the solutions to the subproblems into a solution for the whole.}This structure provides a template for writing recursive functions and is therefore calledthe recursive paradigm. You can apply this technique to programming problems aslong as they meet the following conditions:1. You must be able to identify simple cases for which the answer is easily determined.2. You must be able to identify a recursive decomposition that allows you to break anycomplex instance of the problem into simpler problems of the same form.The CollectContributions example illustrates the power of recursion. As in anyrecursive technique, the original problem is solved by breaking it down into