Procedural-Recursion : Eric-Roberts Notes | EduRev

: Procedural-Recursion : Eric-Roberts Notes | EduRev

 Page 1


Procedural Recursion 
Eric Roberts 
CS 106B 
April 15, 2009 
Page 2


Procedural Recursion 
Eric Roberts 
CS 106B 
April 15, 2009 
Recursion 
• One of the most important “Great Ideas” in CS 106B is the 
concept of recursion, which is the process of solving a 
problem by dividing it into smaller subproblems of the same 
form.  The italicized phrase is the essential characteristic of 
recursion; without it, all you have is a description of stepwise 
refinement of the sort we teach in CS 106A. 
• The fact that recursive decomposition generates subproblems 
that have the same form as the original problem means that 
recursive programs will use the same function or method to 
solve subproblems at different levels of the solution.  In terms 
of the structure of the code, the defining characteristic of 
recursion is having functions that call themselves, directly or 
indirectly, as the decomposition process proceeds.  
Page 3


Procedural Recursion 
Eric Roberts 
CS 106B 
April 15, 2009 
Recursion 
• One of the most important “Great Ideas” in CS 106B is the 
concept of recursion, which is the process of solving a 
problem by dividing it into smaller subproblems of the same 
form.  The italicized phrase is the essential characteristic of 
recursion; without it, all you have is a description of stepwise 
refinement of the sort we teach in CS 106A. 
• The fact that recursive decomposition generates subproblems 
that have the same form as the original problem means that 
recursive programs will use the same function or method to 
solve subproblems at different levels of the solution.  In terms 
of the structure of the code, the defining characteristic of 
recursion is having functions that call themselves, directly or 
indirectly, as the decomposition process proceeds.  
A Simple Illustration of Recursion 
• Suppose that you are the national fundraising director for a 
charitable organization and need to raise $1,000,000. 
• One possible approach is to find a wealthy donor and ask for 
a single $1,000,000 contribution.  The problem with that 
strategy is that individuals with the necessary combination of 
means and generosity are difficult to find.  Donors are much 
more likely to make contributions in the $100 range. 
• Another strategy would be to ask 10,000 friends for $100 
each.  Unfortunately, most of us don’t have 10,000 friends. 
• There are, however, more promising strategies.  You could, 
for example, find ten regional coordinators and charge each 
one with raising $100,000.  Those regional coordinators could 
in turn delegate the task to local coordinators, each with a 
goal of $10,000, continuing the process reached a manageable 
contribution level.  
Page 4


Procedural Recursion 
Eric Roberts 
CS 106B 
April 15, 2009 
Recursion 
• One of the most important “Great Ideas” in CS 106B is the 
concept of recursion, which is the process of solving a 
problem by dividing it into smaller subproblems of the same 
form.  The italicized phrase is the essential characteristic of 
recursion; without it, all you have is a description of stepwise 
refinement of the sort we teach in CS 106A. 
• The fact that recursive decomposition generates subproblems 
that have the same form as the original problem means that 
recursive programs will use the same function or method to 
solve subproblems at different levels of the solution.  In terms 
of the structure of the code, the defining characteristic of 
recursion is having functions that call themselves, directly or 
indirectly, as the decomposition process proceeds.  
A Simple Illustration of Recursion 
• Suppose that you are the national fundraising director for a 
charitable organization and need to raise $1,000,000. 
• One possible approach is to find a wealthy donor and ask for 
a single $1,000,000 contribution.  The problem with that 
strategy is that individuals with the necessary combination of 
means and generosity are difficult to find.  Donors are much 
more likely to make contributions in the $100 range. 
• Another strategy would be to ask 10,000 friends for $100 
each.  Unfortunately, most of us don’t have 10,000 friends. 
• There are, however, more promising strategies.  You could, 
for example, find ten regional coordinators and charge each 
one with raising $100,000.  Those regional coordinators could 
in turn delegate the task to local coordinators, each with a 
goal of $10,000, continuing the process reached a manageable 
contribution level.  
A Simple Illustration of Recursion 
The following diagram illustrates the recursive strategy for 
raising $1,000,000 described on the previous slide: 
Goal: 
$1,000,000 
Goal: 
$100,000 
Goal: 
$100,000 
Goal: 
$100,000 
Goal: 
$100,000 
Goal: 
$100,000 
Goal: 
$100,000 
Goal: 
$100,000 
Goal: 
$100,000 
Goal: 
$100,000 
Goal: 
$100,000 
Goal: 
$10,000 
Goal: 
$10,000 
Goal: 
$10,000 
Goal: 
$10,000 
Goal: 
$10,000 
Goal: 
$10,000 
Goal: 
$10,000 
Goal: 
$10,000 
Goal: 
$10,000 
Goal: 
$10,000 
Goal: 
$1000 
Goal: 
$1000 
Goal: 
$1000 
Goal: 
$1000 
Goal: 
$1000 
Goal: 
$1000 
Goal: 
$1000 
Goal: 
$1000 
Goal: 
$1000 
Goal: 
$1000 
Goal: 
$100 
Goal: 
$100 
Goal: 
$100 
Goal: 
$100 
Goal: 
$100 
Goal: 
$100 
Goal: 
$100 
Goal: 
$100 
Goal: 
$100 
Goal: 
$100 
Page 5


Procedural Recursion 
Eric Roberts 
CS 106B 
April 15, 2009 
Recursion 
• One of the most important “Great Ideas” in CS 106B is the 
concept of recursion, which is the process of solving a 
problem by dividing it into smaller subproblems of the same 
form.  The italicized phrase is the essential characteristic of 
recursion; without it, all you have is a description of stepwise 
refinement of the sort we teach in CS 106A. 
• The fact that recursive decomposition generates subproblems 
that have the same form as the original problem means that 
recursive programs will use the same function or method to 
solve subproblems at different levels of the solution.  In terms 
of the structure of the code, the defining characteristic of 
recursion is having functions that call themselves, directly or 
indirectly, as the decomposition process proceeds.  
A Simple Illustration of Recursion 
• Suppose that you are the national fundraising director for a 
charitable organization and need to raise $1,000,000. 
• One possible approach is to find a wealthy donor and ask for 
a single $1,000,000 contribution.  The problem with that 
strategy is that individuals with the necessary combination of 
means and generosity are difficult to find.  Donors are much 
more likely to make contributions in the $100 range. 
• Another strategy would be to ask 10,000 friends for $100 
each.  Unfortunately, most of us don’t have 10,000 friends. 
• There are, however, more promising strategies.  You could, 
for example, find ten regional coordinators and charge each 
one with raising $100,000.  Those regional coordinators could 
in turn delegate the task to local coordinators, each with a 
goal of $10,000, continuing the process reached a manageable 
contribution level.  
A Simple Illustration of Recursion 
The following diagram illustrates the recursive strategy for 
raising $1,000,000 described on the previous slide: 
Goal: 
$1,000,000 
Goal: 
$100,000 
Goal: 
$100,000 
Goal: 
$100,000 
Goal: 
$100,000 
Goal: 
$100,000 
Goal: 
$100,000 
Goal: 
$100,000 
Goal: 
$100,000 
Goal: 
$100,000 
Goal: 
$100,000 
Goal: 
$10,000 
Goal: 
$10,000 
Goal: 
$10,000 
Goal: 
$10,000 
Goal: 
$10,000 
Goal: 
$10,000 
Goal: 
$10,000 
Goal: 
$10,000 
Goal: 
$10,000 
Goal: 
$10,000 
Goal: 
$1000 
Goal: 
$1000 
Goal: 
$1000 
Goal: 
$1000 
Goal: 
$1000 
Goal: 
$1000 
Goal: 
$1000 
Goal: 
$1000 
Goal: 
$1000 
Goal: 
$1000 
Goal: 
$100 
Goal: 
$100 
Goal: 
$100 
Goal: 
$100 
Goal: 
$100 
Goal: 
$100 
Goal: 
$100 
Goal: 
$100 
Goal: 
$100 
Goal: 
$100 
A Pseudocode Fundraising Strategy 
If you were to implement the fundraising strategy in the form of 
a C++ function, it would look something like this: 
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. 
   } 
} 
What makes this strategy recursive is that the line 
Get each volunteer to collect n/10 dollars. 
will be implemented using the following recursive call: 
CollectContributions(n / 10); 
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!