<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="7e97bb04683011ef86010214bd5530e3" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@5c633101022f46fdb80e1c6e89a3963d" data-block-type="vertical" data-graded="True" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-version="1">
<h2 class="hd hd-2 unit-title">This course on Open Learning Library</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@c5a6fa5e39294a92b940cef6f76379f8">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="7e97bb04683011ef86010214bd5530e3" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@c5a6fa5e39294a92b940cef6f76379f8" data-block-type="html" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p style="text-rendering: optimizelegibility; margin-top: 0px; margin-right: 0px; margin-left: 0px; padding: 0px; border: 0px; outline: 0px; font-variant-numeric: inherit; font-variant-east-asian: inherit; font-stretch: inherit; font-family: 'Open Sans', 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 16px; vertical-align: baseline; color: #313131;">In this version of <em>Advanced</em> <em style="text-rendering: optimizelegibility; margin: 0px; padding: 0px; border: 0px; outline: 0px; font-variant: inherit; font-weight: inherit; font-stretch: inherit; line-height: 1.4em; font-family: inherit; vertical-align: baseline;">Software Construction in JavaPractices</em> on Open Learning Library:</p>
<ul style="text-rendering: optimizelegibility; border: 0px; outline: 0px; font-variant-numeric: inherit; font-variant-east-asian: inherit; font-stretch: inherit; line-height: 1.4em; font-family: 'Open Sans', 'Helvetica Neue', Helvetica, Arial, sans-serif; vertical-align: baseline; color: #313131;">
<li style="text-rendering: optimizelegibility; margin-top: 0px; margin-right: 0px; margin-left: 0px; padding: 0px; border: 0px; outline: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; font-stretch: inherit; line-height: 1.4em; font-family: inherit; vertical-align: baseline;">No certificates can be earned on Open Learning Library</li>
<li style="text-rendering: optimizelegibility; margin-top: 0px; margin-right: 0px; margin-left: 0px; padding: 0px; border: 0px; outline: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; font-stretch: inherit; line-height: 1.4em; font-family: inherit; vertical-align: baseline;">Runs as ‘self-paced’ and all dates mentioned within are irrelevant</li>
<li style="text-rendering: optimizelegibility; margin-top: 0px; margin-right: 0px; margin-left: 0px; padding: 0px; border: 0px; outline: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; font-stretch: inherit; line-height: 1.4em; font-family: inherit; vertical-align: baseline;">Some assessment material may have been removed and grading adjusted accordingly</li>
<li style="text-rendering: optimizelegibility; margin-top: 0px; margin-right: 0px; margin-left: 0px; padding: 0px; border: 0px; outline: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; font-stretch: inherit; line-height: 1.4em; font-family: inherit; vertical-align: baseline;">Any discussion forums have been removed</li>
<li style="text-rendering: optimizelegibility; margin-top: 0px; margin-right: 0px; margin-left: 0px; padding: 0px; border: 0px; outline: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; font-stretch: inherit; line-height: 1.4em; font-family: inherit; vertical-align: baseline;">All assessments have been set to unlimited attempts</li>
<li style="text-rendering: optimizelegibility; margin-top: 0px; margin-right: 0px; margin-left: 0px; padding: 0px; border: 0px; outline: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; font-stretch: inherit; line-height: 1.4em; font-family: inherit; vertical-align: baseline;">Some course content may have been removed </li>
</ul>
<p></p>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="7e97bb04683011ef86010214bd5530e3" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@vertical-recursion-reading" data-block-type="vertical" data-graded="True" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-version="1">
<h2 class="hd hd-2 unit-title">Reading 1 Objectives</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_3bc68a9e3edc">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="7e97bb04683011ef86010214bd5530e3" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_3bc68a9e3edc" data-block-type="html" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<h4>Software in 6.005</h4>
<table class="table table-striped no-markdown">
<tbody>
<tr>
<th width="33%">Safe from bugs</th>
<th>Easy to understand</th>
<th>Ready for change</th>
</tr>
<tr>
<td>
Correct today and correct in the unknown future.
</td>
<td>
Communicating clearly with future programmers, including future you.
</td>
<td>
Designed to accommodate change without rewriting.
</td>
</tr>
</tbody>
</table>
<h4>Objectives</h4>
<p>After today's class, you should:</p>
<ul>
<li>be able to decompose a recursive problem into recursive steps and base cases</li>
<li>know when and how to use helper methods in recursion</li>
<li>understand the advantages and disadvantages of recursion vs. iteration</li>
</ul>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="7e97bb04683011ef86010214bd5530e3" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@Recursion" data-block-type="vertical" data-graded="True" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-version="1">
<h2 class="hd hd-2 unit-title">Recursion</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_f109ca9c5146">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="7e97bb04683011ef86010214bd5530e3" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_f109ca9c5146" data-block-type="html" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<h2 id="recursion">Recursion</h2>
<div data-outline="recursion">
<p>In today's class, we're going to talk about how to implement a method, once you already have a specification. We'll focus on one particular technique, <em>recursion</em>. Recursion is not appropriate for every problem, but it's an important tool in your software development toolbox, and one that many people scratch their heads over. We want you to be comfortable and competent with recursion, because you will encounter it over and over. (That's a joke, but it's also true.)</p>
<p>Hopefully recursion is not completely new to you, and you have seen and written recursive functions like factorial and fibonacci before. Today's class will delve more deeply into recursion than you may have gone before. Comfort with recursive implementations will be necessary for upcoming classes.</p>
<p>A recursive function is defined in terms of <em>base cases</em> and <em>recursive steps</em>.</p>
<ul>
<li>In a base case, we compute the result immediately given the inputs to the function call.</li>
<li>In a recursive step, we compute the result with the help of one or more <em>recursive calls</em> to this same function, but with the inputs somehow reduced in size or complexity, closer to a base case.</li>
</ul>
<p>Consider writing a function to compute factorial. We can define factorial in two different ways:</p>
<div class="pull-margin">
<table class="table no-markdown" style="margin-bottom:0;">
<thead>
<tr>
<th width="50%">Product</th>
<th>Recurrence relation</th>
</tr>
</thead>
<tbody>
<tr>
<td><img src="/assets/courseware/v1/45bee46b3a642fbde76070260911364c/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/01-factorial-product.png" width="294">
<br> (where the empty product equals
<br> multiplicative identity <em>1</em>)</td>
<td><img src="/assets/courseware/v1/060439463a8cb4854f0a327f3a6d8c61/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/01-factorial-recurrence.png" width="232"></td>
</tr>
</tbody>
</table>
<p>which leads to two different implementations:</p>
<table class="table" style="margin-bottom:0;">
<thead class="no-markdown">
<tr>
<th width="50%">Iterative</th>
<th>Recursive</th>
</tr>
</thead>
<tbody>
<tr>
<td><pre><code class="language-java hljs"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">long</span> <span class="hljs-title">factorial</span><span class="hljs-params">(<span class="hljs-keyword">int</span> n)</span> </span>{
<span class="hljs-keyword">long</span> fact = <span class="hljs-number">1</span>;
<span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>; i <= n; i++) {
fact = fact * i;
}
<span class="hljs-keyword">return</span> fact;
}</code></pre></td>
<td><pre><code class="language-java hljs"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">long</span> <span class="hljs-title">factorial</span><span class="hljs-params">(<span class="hljs-keyword">int</span> n)</span> </span>{
<span class="hljs-keyword">if</span> (n == <span class="hljs-number">0</span>) {
<span class="hljs-keyword">return</span> <span class="hljs-number">1</span>;
} <span class="hljs-keyword">else</span> {
<span class="hljs-keyword">return</span> factorial(n-<span class="hljs-number">1</span>) * n;
}
}</code></pre></td>
</tr>
</tbody>
</table>
</div>
<p>In the recursive implementation on the right, the base case is <em>n = 0</em>, where we compute and return the result immediately: <em>0!</em> is defined to be <em>1</em>. The recursive step is <em>n > 0</em>, where we compute the result with the help of a recursive call to obtain <em>(n-1)!</em>, then complete the computation by multiplying by <em>n</em>.</p>
<p>To visualize the execution of a recursive function, it is helpful to diagram the <em>call stack</em> of currently-executing functions as the computation proceeds.</p>
<p>Let's run the recursive implementation of <code>factorial</code> in a main method:</p><pre><code class="language-java hljs"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> </span>{
<span class="hljs-keyword">long</span> x = factorial(<span class="hljs-number">3</span>);
}</code></pre>
<p>At each step, with time moving left to right:</p>
<div id="factorial-call-stacks" class="pull-margin overflow:scroll">
<table class="table">
<thead>
<tr>
<td>
<p>starts in
<br><code>main</code></p>
</td>
<td>
<p>calls
<br><code>factorial(3)</code></p>
</td>
<td>
<p>calls
<br><code>factorial(2)</code></p>
</td>
<td>
<p>calls
<br><code>factorial(1)</code></p>
</td>
<td>
<p>calls
<br><code>factorial(0)</code></p>
</td>
<td>
<p>returns to
<br><code>factorial(1)</code></p>
</td>
<td>
<p>returns to
<br><code>factorial(2)</code></p>
</td>
<td>
<p>returns to
<br><code>factorial(3)</code></p>
</td>
<td>
<p>returns to
<br><code>main</code></p>
</td>
</tr>
</thead>
<tbody class="no-markdown">
<tr>
<td>
<div class="panel panel-primary">
<div class="panel-heading">main</div>
<div class="panel-body"> </div>
</div>
</td>
<td>
<div class="panel panel-primary">
<div class="panel-heading">factorial</div>
<div class="panel-body">n = 3
<br> </div>
</div>
<div class="panel panel-info">
<div class="panel-heading">main</div>
<div class="panel-body">x</div>
</div>
</td>
<td>
<div class="panel panel-primary">
<div class="panel-heading">factorial</div>
<div class="panel-body">n = 2
<br> </div>
</div>
<div class="panel panel-info">
<div class="panel-heading">factorial</div>
<div class="panel-body">n = 3
<br> </div>
</div>
<div class="panel panel-info">
<div class="panel-heading">main</div>
<div class="panel-body">x</div>
</div>
</td>
<td>
<div class="panel panel-primary">
<div class="panel-heading">factorial</div>
<div class="panel-body">n = 1
<br> </div>
</div>
<div class="panel panel-info">
<div class="panel-heading">factorial</div>
<div class="panel-body">n = 2
<br> </div>
</div>
<div class="panel panel-info">
<div class="panel-heading">factorial</div>
<div class="panel-body">n = 3
<br> </div>
</div>
<div class="panel panel-info">
<div class="panel-heading">main</div>
<div class="panel-body">x</div>
</div>
</td>
<td>
<div class="panel panel-primary">
<div class="panel-heading">factorial</div>
<div class="panel-body">n = 0
<br><span class="return-value">returns 1</span></div>
</div>
<div class="panel panel-info">
<div class="panel-heading">factorial</div>
<div class="panel-body">n = 1
<br> </div>
</div>
<div class="panel panel-info">
<div class="panel-heading">factorial</div>
<div class="panel-body">n = 2
<br> </div>
</div>
<div class="panel panel-info">
<div class="panel-heading">factorial</div>
<div class="panel-body">n = 3
<br> </div>
</div>
<div class="panel panel-info">
<div class="panel-heading">main</div>
<div class="panel-body">x</div>
</div>
</td>
<td>
<div class="panel panel-primary">
<div class="panel-heading">factorial</div>
<div class="panel-body">n = 1
<br><span class="return-value">returns 1</span></div>
</div>
<div class="panel panel-info">
<div class="panel-heading">factorial</div>
<div class="panel-body">n = 2
<br> </div>
</div>
<div class="panel panel-info">
<div class="panel-heading">factorial</div>
<div class="panel-body">n = 3
<br> </div>
</div>
<div class="panel panel-info">
<div class="panel-heading">main</div>
<div class="panel-body">x</div>
</div>
</td>
<td>
<div class="panel panel-primary">
<div class="panel-heading">factorial</div>
<div class="panel-body">n = 2
<br><span class="return-value">returns 2</span></div>
</div>
<div class="panel panel-info">
<div class="panel-heading">factorial</div>
<div class="panel-body">n = 3
<br> </div>
</div>
<div class="panel panel-info">
<div class="panel-heading">main</div>
<div class="panel-body">x</div>
</div>
</td>
<td>
<div class="panel panel-primary">
<div class="panel-heading">factorial</div>
<div class="panel-body">n = 3
<br><span class="return-value">returns 6</span></div>
</div>
<div class="panel panel-info">
<div class="panel-heading">main</div>
<div class="panel-body">x</div>
</div>
</td>
<td>
<div class="panel panel-primary">
<div class="panel-heading">main</div>
<div class="panel-body">x = 6</div>
</div>
</td>
</tr>
</tbody>
</table>
</div>
<p>In the diagram, we can see how the stack grows as <code>main</code> calls <code>factorial</code> and <code>factorial</code> then calls <em>itself</em>, until <code>factorial(0)</code> does not make a recursive call. Then the call stack unwinds, each call to <code>factorial</code> returning its answer to the caller, until <code>factorial(3)</code> returns to <code>main</code>.</p>
<p>Here's an <a href="http://www.pythontutor.com/visualize.html#code=public+class+Factorial+%7B%0A++++public+static+void+main(String%5B%5D+args)+%7B%0A++++++++long+x+%3D+factorial(3)%3B%0A++++%7D%0A++++public+static+long+factorial(int+n)+%7B%0A++++++++if+(n+%3D%3D+0)+%7B%0A++++++++++++return+1%3B%0A++++++++%7D+else+%7B%0A++++++++++++return+n+*+factorial(n-1)%3B%0A++++++++%7D%0A++++%7D%0A%7D&mode=display&origin=opt-frontend.js&cumulative=false&heapPrimitives=false&textReferences=false&py=java&rawInputLstJSON=%5B%5D&curInstr=0" target="_blank"><strong>interactive visualization of <code>factorial</code></strong></a>. You can step through the computation to see the recursion in action. New stack frames grow down instead of up in this visualization.</p>
<p>You've probably seen factorial before, because it's a common example for recursive functions. Another common example is the Fibonacci series: </p><pre><code class="language-java hljs"><span class="hljs-comment handout-javadoc-comment">/**
* <span class="hljs-doctag">@param</span> n >= 0
* <span class="hljs-doctag">@return</span> the nth Fibonacci number
*/</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">int</span> <span class="hljs-title">fibonacci</span><span class="hljs-params">(<span class="hljs-keyword">int</span> n)</span> </span>{
<span class="hljs-keyword">if</span> (n == <span class="hljs-number">0</span> || n == <span class="hljs-number">1</span>) {
<span class="hljs-keyword">return</span> <span class="hljs-number">1</span>; <span class="hljs-comment">// base cases</span>
} <span class="hljs-keyword">else</span> {
<span class="hljs-keyword">return</span> fibonacci(n-<span class="hljs-number">1</span>) + fibonacci(n-<span class="hljs-number">2</span>); <span class="hljs-comment">// recursive step</span>
}
}</code></pre>
<p>Fibonacci is interesting because it has multiple base cases: n=0 and n=1. You can look at an <a href="http://www.pythontutor.com/visualize.html#code=public+class+Fibonacci+%7B%0A++++public+static+void+main(String%5B%5D+args)+%7B%0A++++++++int+x+%3D+fibonacci(3)%3B%0A++++%7D%0A++++public+static+int+fibonacci(int+n)+%7B%0A++++++++if+(n+%3D%3D+0+%7C%7C+n+%3D%3D+1)+%7B%0A++++++++++++return+1%3B%0A++++++++%7D+else+%7B%0A++++++++++++return+fibonacci(n-1)+%2B+fibonacci(n-2)%3B%0A++++++++%7D%0A++++%7D%0A%7D&mode=display&origin=opt-frontend.js&cumulative=false&heapPrimitives=false&textReferences=false&py=java&rawInputLstJSON=%5B%5D&curInstr=0" target="_blank"><strong>interactive visualization of Fibonacci</strong></a>. Notice that where factorial's stack steadily grows to a maximum depth and then shrinks back to the answer, Fibonacci's stack grows and shrinks repeatedly over the course of the computation.</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="7e97bb04683011ef86010214bd5530e3" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@Questions" data-block-type="vertical" data-graded="True" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-version="1">
<h2 class="hd hd-2 unit-title">Questions</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@Recursion">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="7e97bb04683011ef86010214bd5530e3" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@Recursion" data-block-type="html" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<script src="/assets/courseware/v1/c9cee8830885f59e75b8782f44026226/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/edx-script-v1.js"></script>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-recursion-22">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-request-token="7e97bb04683011ef86010214bd5530e3" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-recursion-22" data-block-type="problem" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_01-recursion-22" class="problems-wrapper" role="group"
aria-labelledby="01-recursion-22-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-recursion-22" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-recursion-22/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="01-recursion-22-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-recursion-22-problem-progress" tabindex="-1">
Recursive factorial
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-recursion-22-problem-progress"></div>
<div class="problem">
<div>
<p>Consider this recursive implementation of the factorial function.</p>
<pre>
public static int factorial(int n) {
if (n == 0) {
return 1; // this is called the base case
} else {
return n * factorial(n-1); // this is the recursive step
}
}
</pre>
<p>For factorial(3), how many times will the base case be executed?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_01-recursion-22_2_1">
<fieldset aria-describedby="status_01-recursion-22_2_1">
<div class="field">
<input type="radio" name="input_01-recursion-22_2_1" id="input_01-recursion-22_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="01-recursion-22_2_1-choice_0-label" for="input_01-recursion-22_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_01-recursion-22_2_1"> 0 times
</label>
</div>
<div class="field">
<input type="radio" name="input_01-recursion-22_2_1" id="input_01-recursion-22_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="01-recursion-22_2_1-choice_1-label" for="input_01-recursion-22_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_01-recursion-22_2_1"> 1 time
</label>
</div>
<div class="field">
<input type="radio" name="input_01-recursion-22_2_1" id="input_01-recursion-22_2_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="01-recursion-22_2_1-choice_2-label" for="input_01-recursion-22_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_01-recursion-22_2_1"> 2 times
</label>
</div>
<div class="field">
<input type="radio" name="input_01-recursion-22_2_1" id="input_01-recursion-22_2_1_choice_3" class="field-input input-radio" value="choice_3"/><label id="01-recursion-22_2_1-choice_3-label" for="input_01-recursion-22_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_01-recursion-22_2_1"> 3 times
</label>
</div>
<div class="field">
<input type="radio" name="input_01-recursion-22_2_1" id="input_01-recursion-22_2_1_choice_4" class="field-input input-radio" value="choice_4"/><label id="01-recursion-22_2_1-choice_4-label" for="input_01-recursion-22_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_01-recursion-22_2_1"> more than 3 times
</label>
</div>
<span id="answer_01-recursion-22_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_01-recursion-22_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_01-recursion-22_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Recursive factorial" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_01-recursion-22" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_01-recursion-22">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="01-recursion-22-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="01-recursion-22-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="01-recursion-22-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-2" data-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-recursion-23">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-request-token="7e97bb04683011ef86010214bd5530e3" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-recursion-23" data-block-type="problem" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_01-recursion-23" class="problems-wrapper" role="group"
aria-labelledby="01-recursion-23-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-recursion-23" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-recursion-23/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="01-recursion-23-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-recursion-23-problem-progress" tabindex="-1">
Recursive Fibonacci
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-recursion-23-problem-progress"></div>
<div class="problem">
<div>
<p>Consider this recursive implementation of the Fibonacci sequence.</p>
<pre>
public static int fibonacci(int n) {
if (n == 0 || n == 1) {
return 1; // base cases
} else {
return fibonacci(n-1) + fibonacci(n-2); // recursive step
}
}
</pre>
<p>For fibonacci(3), how many times will the base case be executed?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_01-recursion-23_2_1">
<fieldset aria-describedby="status_01-recursion-23_2_1">
<div class="field">
<input type="radio" name="input_01-recursion-23_2_1" id="input_01-recursion-23_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="01-recursion-23_2_1-choice_0-label" for="input_01-recursion-23_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_01-recursion-23_2_1"> 0 times
</label>
</div>
<div class="field">
<input type="radio" name="input_01-recursion-23_2_1" id="input_01-recursion-23_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="01-recursion-23_2_1-choice_1-label" for="input_01-recursion-23_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_01-recursion-23_2_1"> 1 time
</label>
</div>
<div class="field">
<input type="radio" name="input_01-recursion-23_2_1" id="input_01-recursion-23_2_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="01-recursion-23_2_1-choice_2-label" for="input_01-recursion-23_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_01-recursion-23_2_1"> 2 times
</label>
</div>
<div class="field">
<input type="radio" name="input_01-recursion-23_2_1" id="input_01-recursion-23_2_1_choice_3" class="field-input input-radio" value="choice_3"/><label id="01-recursion-23_2_1-choice_3-label" for="input_01-recursion-23_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_01-recursion-23_2_1"> 3 times
</label>
</div>
<div class="field">
<input type="radio" name="input_01-recursion-23_2_1" id="input_01-recursion-23_2_1_choice_4" class="field-input input-radio" value="choice_4"/><label id="01-recursion-23_2_1-choice_4-label" for="input_01-recursion-23_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_01-recursion-23_2_1"> more than 3 times
</label>
</div>
<span id="answer_01-recursion-23_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_01-recursion-23_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_01-recursion-23_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Recursive Fibonacci" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_01-recursion-23" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_01-recursion-23">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="01-recursion-23-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="01-recursion-23-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="01-recursion-23-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="7e97bb04683011ef86010214bd5530e3" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@Choosing_the_Right_Decomposition_for_a_Problem" data-block-type="vertical" data-graded="True" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-version="1">
<h2 class="hd hd-2 unit-title">Choosing the Right Decomposition for a Problem</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_07a081b97aed">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="7e97bb04683011ef86010214bd5530e3" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_07a081b97aed" data-block-type="html" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<h2 id="choosing_the_right_decomposition_for_a_problem">Choosing the Right Decomposition for a Problem</h2>
<div data-outline="choosing_the_right_decomposition_for_a_problem">
<p>Finding the right way to decompose a problem, such as a method implementation, is important. Good decompositions are simple, short, easy to understand, safe from bugs, and ready for change.</p>
<p>Recursion is an elegant and simple decomposition for some problems. Suppose we want to implement this specification:</p><pre><code class="language-java hljs"><span class="hljs-comment handout-javadoc-comment">/**
* <span class="hljs-doctag">@param</span> word consisting only of letters A-Z or a-z
* <span class="hljs-doctag">@return</span> all subsequences of word, separated by commas,
* where a subsequence is a string of letters found in word
* in the same order that they appear in word.
*/</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> String <span class="hljs-title">subsequences</span><span class="hljs-params">(String word)</span></span></code></pre>
<p>For example, <code>subsequences("abc")</code> might return <code>"abc,ab,bc,ac,a,b,c,"</code>. Note the trailing comma preceding the empty subsequence, which is also a valid subsequence.</p>
<p>This problem lends itself to an elegant recursive decomposition. Take the first letter of the word. We can form one set of subsequences that <em>include</em> that letter, and another set of subsequences that exclude that letter, and those two sets completely cover the set of possible subsequences.</p><pre><code class="language-java hljs"> <span class="hljs-number">1</span> <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> String <span class="hljs-title">subsequences</span><span class="hljs-params">(String word)</span> </span>{
<span class="hljs-number">2</span> <span class="hljs-keyword">if</span> (word.isEmpty()) {
<span class="hljs-number">3</span> <span class="hljs-keyword">return</span> <span class="hljs-string">""</span>; <span class="hljs-comment">// base case</span>
<span class="hljs-number">4</span> } <span class="hljs-keyword">else</span> {
<span class="hljs-number">5</span> <span class="hljs-keyword">char</span> firstLetter = word.charAt(<span class="hljs-number">0</span>);
<span class="hljs-number">6</span> String restOfWord = word.substring(<span class="hljs-number">1</span>);
<span class="hljs-number">7</span>
<span class="hljs-number">8</span> String subsequencesOfRest = subsequences(restOfWord);
<span class="hljs-number">9</span>
<span class="hljs-number">10</span> String result = <span class="hljs-string">""</span>;
<span class="hljs-number">11</span> <span class="hljs-keyword">for</span> (String subsequence : subsequencesOfRest.split(<span class="hljs-string">","</span>, -<span class="hljs-number">1</span>)) {
<span class="hljs-number">12</span> result += <span class="hljs-string">","</span> + subsequence;
<span class="hljs-number">13</span> result += <span class="hljs-string">","</span> + firstLetter + subsequence;
<span class="hljs-number">14</span> }
<span class="hljs-number">15</span> result = result.substring(<span class="hljs-number">1</span>); <span class="hljs-comment">// remove extra leading comma</span>
<span class="hljs-number">16</span> <span class="hljs-keyword">return</span> result;
<span class="hljs-number">17</span> }
<span class="hljs-number">18</span> }</code></pre>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="7e97bb04683011ef86010214bd5530e3" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@vertical_Questions_60693a7db608" data-block-type="vertical" data-graded="True" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-version="1">
<h2 class="hd hd-2 unit-title">Questions</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@Recursive_Decomposition">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="7e97bb04683011ef86010214bd5530e3" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@Recursive_Decomposition" data-block-type="html" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<script src="/assets/courseware/v1/c9cee8830885f59e75b8782f44026226/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/edx-script-v1.js"></script>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-recursive-decomposition-24">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-request-token="7e97bb04683011ef86010214bd5530e3" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-recursive-decomposition-24" data-block-type="problem" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_01-recursive-decomposition-24" class="problems-wrapper" role="group"
aria-labelledby="01-recursive-decomposition-24-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-recursive-decomposition-24" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-recursive-decomposition-24/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="2"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="01-recursive-decomposition-24-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-recursive-decomposition-24-problem-progress" tabindex="-1">
subsequences
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-recursive-decomposition-24-problem-progress"></div>
<div class="problem">
<div>
<pre>
/* 1 */ public static String subsequences(String word) {
/* 2 */ if (word.isEmpty()) {
/* 3 */ return ""; // base case
/* 4 */ } else {
/* 5 */ char firstLetter = word.charAt(0);
/* 6 */ String restOfWord = word.substring(1);
/* 7 */
/* 8 */ String subsequencesOfRest = subsequences(restOfWord);
/* 9 */
/* 10 */ String result = "";
/* 11 */ for (String subsequence : subsequencesOfRest.split(",", -1)) {
/* 12 */ result += "," + subsequence;
/* 13 */ result += "," + firstLetter + subsequence;
/* 14 */ }
/* 15 */ result = result.substring(1); // remove extra leading comma
/* 16 */ return result;
/* 17 */ }
/* 18 */ }
</pre>
<p>What does subsequences("c") return?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_01-recursive-decomposition-24_2_1">
<fieldset aria-describedby="status_01-recursive-decomposition-24_2_1">
<div class="field">
<input type="radio" name="input_01-recursive-decomposition-24_2_1" id="input_01-recursive-decomposition-24_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="01-recursive-decomposition-24_2_1-choice_0-label" for="input_01-recursive-decomposition-24_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_01-recursive-decomposition-24_2_1"> "c"
</label>
</div>
<div class="field">
<input type="radio" name="input_01-recursive-decomposition-24_2_1" id="input_01-recursive-decomposition-24_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="01-recursive-decomposition-24_2_1-choice_1-label" for="input_01-recursive-decomposition-24_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_01-recursive-decomposition-24_2_1"> ""
</label>
</div>
<div class="field">
<input type="radio" name="input_01-recursive-decomposition-24_2_1" id="input_01-recursive-decomposition-24_2_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="01-recursive-decomposition-24_2_1-choice_2-label" for="input_01-recursive-decomposition-24_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_01-recursive-decomposition-24_2_1"> ",c"
</label>
</div>
<div class="field">
<input type="radio" name="input_01-recursive-decomposition-24_2_1" id="input_01-recursive-decomposition-24_2_1_choice_3" class="field-input input-radio" value="choice_3"/><label id="01-recursive-decomposition-24_2_1-choice_3-label" for="input_01-recursive-decomposition-24_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_01-recursive-decomposition-24_2_1"> "c,"
</label>
</div>
<span id="answer_01-recursive-decomposition-24_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_01-recursive-decomposition-24_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_01-recursive-decomposition-24_solution_1"/>
</div><p>What does subsequences("gc") return?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div class="choicegroup capa_inputtype" id="inputtype_01-recursive-decomposition-24_3_1">
<fieldset aria-describedby="status_01-recursive-decomposition-24_3_1">
<div class="field">
<input type="radio" name="input_01-recursive-decomposition-24_3_1" id="input_01-recursive-decomposition-24_3_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="01-recursive-decomposition-24_3_1-choice_0-label" for="input_01-recursive-decomposition-24_3_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_01-recursive-decomposition-24_3_1"> "g,c"
</label>
</div>
<div class="field">
<input type="radio" name="input_01-recursive-decomposition-24_3_1" id="input_01-recursive-decomposition-24_3_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="01-recursive-decomposition-24_3_1-choice_1-label" for="input_01-recursive-decomposition-24_3_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_01-recursive-decomposition-24_3_1"> ",g,c,gc"
</label>
</div>
<div class="field">
<input type="radio" name="input_01-recursive-decomposition-24_3_1" id="input_01-recursive-decomposition-24_3_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="01-recursive-decomposition-24_3_1-choice_2-label" for="input_01-recursive-decomposition-24_3_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_01-recursive-decomposition-24_3_1"> ",gc,g,c"
</label>
</div>
<div class="field">
<input type="radio" name="input_01-recursive-decomposition-24_3_1" id="input_01-recursive-decomposition-24_3_1_choice_3" class="field-input input-radio" value="choice_3"/><label id="01-recursive-decomposition-24_3_1-choice_3-label" for="input_01-recursive-decomposition-24_3_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_01-recursive-decomposition-24_3_1"> "g,c,gc"
</label>
</div>
<span id="answer_01-recursive-decomposition-24_3_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_01-recursive-decomposition-24_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_01-recursive-decomposition-24_solution_2"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="subsequences" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_01-recursive-decomposition-24" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_01-recursive-decomposition-24">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="01-recursive-decomposition-24-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="01-recursive-decomposition-24-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="01-recursive-decomposition-24-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="7e97bb04683011ef86010214bd5530e3" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@Structure_of_Recursive_Implementations" data-block-type="vertical" data-graded="True" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-version="1">
<h2 class="hd hd-2 unit-title">Structure of Recursive Implementations</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_c2df64168870">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="7e97bb04683011ef86010214bd5530e3" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_c2df64168870" data-block-type="html" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<h2 id="structure_of_recursive_implementations">Structure of Recursive Implementations</h2>
<div data-outline="structure_of_recursive_implementations">
<p>A recursive implementation always has two parts:</p>
<ul>
<li>
<p><strong>base case</strong>, which is the simplest, smallest instance of the problem, that can't be decomposed any further. Base cases often correspond to emptiness — the empty string, the empty list, the empty set, the empty tree, zero, etc.</p>
</li>
<li>
<p><strong>recursive step</strong>, which <strong>decomposes</strong> a larger instance of the problem into one or more simpler or smaller instances that can be solved by recursive calls, and then <strong>recombines</strong> the results of those subproblems to produce the solution to the original problem.</p>
</li>
</ul>
<p>It's important for the recursive step to transform the problem instance into something smaller, otherwise the recursion may never end. If every recursive step shrinks the problem, and the base case lies at the bottom, then the recursion is guaranteed to be finite. </p>
<p>A recursive implementation may have more than one base case, or more than one recursive step. For example, the Fibonacci function has two base cases, n=0 and n=1.</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="7e97bb04683011ef86010214bd5530e3" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@vertical_Questions_3c298ffceaed" data-block-type="vertical" data-graded="True" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-version="1">
<h2 class="hd hd-2 unit-title">Questions</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@Recursive_Structure">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="7e97bb04683011ef86010214bd5530e3" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@Recursive_Structure" data-block-type="html" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<script src="/assets/courseware/v1/c9cee8830885f59e75b8782f44026226/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/edx-script-v1.js"></script>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-recursive-structure-25">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-request-token="7e97bb04683011ef86010214bd5530e3" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-recursive-structure-25" data-block-type="problem" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_01-recursive-structure-25" class="problems-wrapper" role="group"
aria-labelledby="01-recursive-structure-25-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-recursive-structure-25" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-recursive-structure-25/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="01-recursive-structure-25-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-recursive-structure-25-problem-progress" tabindex="-1">
Recursive structure
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-recursive-structure-25-problem-progress"></div>
<div class="problem">
<div>
<p>Recursive methods have a base case and a recursive step. What other concepts from computer science also have (the equivalent of) a base case and a recursive step?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_01-recursive-structure-25_2_1">
<fieldset aria-describedby="status_01-recursive-structure-25_2_1">
<div class="field">
<input type="checkbox" name="input_01-recursive-structure-25_2_1[]" id="input_01-recursive-structure-25_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="01-recursive-structure-25_2_1-choice_0-label" for="input_01-recursive-structure-25_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_01-recursive-structure-25_2_1"> proof by induction
</label>
</div>
<div class="field">
<input type="checkbox" name="input_01-recursive-structure-25_2_1[]" id="input_01-recursive-structure-25_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="01-recursive-structure-25_2_1-choice_1-label" for="input_01-recursive-structure-25_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_01-recursive-structure-25_2_1"> regression testing
</label>
</div>
<div class="field">
<input type="checkbox" name="input_01-recursive-structure-25_2_1[]" id="input_01-recursive-structure-25_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="01-recursive-structure-25_2_1-choice_2-label" for="input_01-recursive-structure-25_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_01-recursive-structure-25_2_1"> recessive functions
</label>
</div>
<div class="field">
<input type="checkbox" name="input_01-recursive-structure-25_2_1[]" id="input_01-recursive-structure-25_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="01-recursive-structure-25_2_1-choice_3-label" for="input_01-recursive-structure-25_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_01-recursive-structure-25_2_1"> binary trees
</label>
</div>
<span id="answer_01-recursive-structure-25_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_01-recursive-structure-25_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_01-recursive-structure-25_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Recursive structure" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_01-recursive-structure-25" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_01-recursive-structure-25">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="01-recursive-structure-25-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="01-recursive-structure-25-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="01-recursive-structure-25-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="7e97bb04683011ef86010214bd5530e3" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@Helper_Methods" data-block-type="vertical" data-graded="True" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-version="1">
<h2 class="hd hd-2 unit-title">Helper Methods</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_aff9bbf61251">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="7e97bb04683011ef86010214bd5530e3" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_aff9bbf61251" data-block-type="html" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<h2 id="helper_methods">Helper Methods</h2>
<div data-outline="helper_methods">
<p>The recursive implementation we just saw for <code>subsequences()</code> is one possible recursive decomposition of the problem. We took a solution to a subproblem — the subsequences of the remainder of the string after removing the first character — and used it to construct solutions to the original problem, by taking each subsequence and adding the first character or omitting it. This is in a sense a <em>direct</em> recursive implementation, where we are using the existing specification of the recursive method to solve the subproblems. </p>
<p>In some cases, it's useful to require a stronger (or different) specification for the recursive steps, to make the recursive decomposition simpler or more elegant. In this case, what if we built up a partial subsequence using the initial letters of the word, and used the recursive calls to <i>complete</i> that partial subsequence using the remaining letters of the word? For example, suppose the original word is "orange". We'll both select "o" to be in the partial subsequence, and recursively extend it with all subsequences of "range"; and we'll skip "o", use "" as the partial subsequence, and again recursively extend it with all subsequences of "range". </p>
<p>Using this approach, our code now looks much simpler:</p><pre><code class="language-java hljs"><span class="hljs-comment handout-javadoc-comment">/**
* Return all subsequences of word (as defined above) separated by commas,
* with partialSubsequence prepended to each one.
*/</span>
<span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">static</span> String <span class="hljs-title">subsequencesAfter</span><span class="hljs-params">(String partialSubsequence, String word)</span> </span>{
<span class="hljs-keyword">if</span> (word.isEmpty()) {
<span class="hljs-comment">// base case</span>
<span class="hljs-keyword">return</span> partialSubsequence;
} <span class="hljs-keyword">else</span> {
<span class="hljs-comment">// recursive step</span>
<span class="hljs-keyword">return</span> subsequencesAfter(partialSubsequence, word.substring(<span class="hljs-number">1</span>))
+ <span class="hljs-string">","</span>
+ subsequencesAfter(partialSubsequence + word.charAt(<span class="hljs-number">0</span>), word.substring(<span class="hljs-number">1</span>));
}
}</code></pre>
<p>This <code>subsequencesAfter</code> method is called a <strong>helper method</strong>. It satisfies a different spec from the original <code>subsequences</code>, because it has a new parameter <code>partialSubsequence</code>. This parameter fills a similar role that a local variable would in an iterative implementation. It holds temporary state during the evolution of the computation. The recursive calls steadily extend this partial subsequence, selecting or ignoring each letter in the word, until finally reaching the end of the word (the base case), at which point the partial subsequence is returned as the only result. Then the recursion backtracks and fills in other possible subsequences.</p>
<p>To finish the implementation, we need to implement the original <code>subsequences</code> spec, which gets the ball rolling by calling the helper method with an initial value for the partial subsequence parameter:</p><pre><code class="language-java hljs"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> String <span class="hljs-title">subsequences</span><span class="hljs-params">(String word)</span> </span>{
<span class="hljs-keyword">return</span> subsequencesAfter(<span class="hljs-string">""</span>, word);
}</code></pre>
<p><strong>Don't expose the helper method to your clients.</strong> Your decision to decompose the recursion this way instead of another way is entirely implementation-specific. In particular, if you discover that you need temporary variables like <code>partialSubsequence</code> in your recursion, don't change the original spec of your method, and don't force your clients to correctly initialize those parameters. That exposes your implementation to the client and reduces your ability to change it in the future. Use a private helper function for the recursion, and have your public method call it with the correct initializations, as shown above.</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="7e97bb04683011ef86010214bd5530e3" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@vertical_Questions_94385a7df5d6" data-block-type="vertical" data-graded="True" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-version="1">
<h2 class="hd hd-2 unit-title">Questions</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@Helper_Methods">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="7e97bb04683011ef86010214bd5530e3" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@Helper_Methods" data-block-type="html" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<script src="/assets/courseware/v1/c9cee8830885f59e75b8782f44026226/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/edx-script-v1.js"></script>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-helper-methods-18">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-request-token="7e97bb04683011ef86010214bd5530e3" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-helper-methods-18" data-block-type="problem" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_01-helper-methods-18" class="problems-wrapper" role="group"
aria-labelledby="01-helper-methods-18-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-helper-methods-18" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-helper-methods-18/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="2"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="01-helper-methods-18-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-helper-methods-18-problem-progress" tabindex="-1">
Unhelpful 1
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-helper-methods-18-problem-progress"></div>
<div class="problem">
<div>
<p>Louis Reasoner doesn't want to use a helper method, so he tries to implement <code>subsequences()</code> by storing <code>partialSubsequence</code> as a static variable instead of a parameter. Here is his implementation: </p>
<pre>
private static String partialSubsequence = "";
public static String subsequencesLouis(String word) {
if (word.isEmpty()) {
// base case
return partialSubsequence;
} else {
// recursive step
String withoutFirstLetter = subsequencesLouis(word.substring(1));
partialSubsequence += word.charAt(0);
String withFirstLetter = subsequencesLouis(word.substring(1));
return withoutFirstLetter + "," + withFirstLetter;
}
}
</pre>
<p>What does subsequencesLouis("c") return?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_01-helper-methods-18_2_1">
<fieldset aria-describedby="status_01-helper-methods-18_2_1">
<div class="field">
<input type="radio" name="input_01-helper-methods-18_2_1" id="input_01-helper-methods-18_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="01-helper-methods-18_2_1-choice_0-label" for="input_01-helper-methods-18_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_01-helper-methods-18_2_1"> "c"
</label>
</div>
<div class="field">
<input type="radio" name="input_01-helper-methods-18_2_1" id="input_01-helper-methods-18_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="01-helper-methods-18_2_1-choice_1-label" for="input_01-helper-methods-18_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_01-helper-methods-18_2_1"> ""
</label>
</div>
<div class="field">
<input type="radio" name="input_01-helper-methods-18_2_1" id="input_01-helper-methods-18_2_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="01-helper-methods-18_2_1-choice_2-label" for="input_01-helper-methods-18_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_01-helper-methods-18_2_1"> ",c"
</label>
</div>
<div class="field">
<input type="radio" name="input_01-helper-methods-18_2_1" id="input_01-helper-methods-18_2_1_choice_3" class="field-input input-radio" value="choice_3"/><label id="01-helper-methods-18_2_1-choice_3-label" for="input_01-helper-methods-18_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_01-helper-methods-18_2_1"> "c,"
</label>
</div>
<span id="answer_01-helper-methods-18_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_01-helper-methods-18_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<p>What does subsequencesLouis("a") return?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div class="choicegroup capa_inputtype" id="inputtype_01-helper-methods-18_3_1">
<fieldset aria-describedby="status_01-helper-methods-18_3_1">
<div class="field">
<input type="radio" name="input_01-helper-methods-18_3_1" id="input_01-helper-methods-18_3_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="01-helper-methods-18_3_1-choice_0-label" for="input_01-helper-methods-18_3_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_01-helper-methods-18_3_1"> "a"
</label>
</div>
<div class="field">
<input type="radio" name="input_01-helper-methods-18_3_1" id="input_01-helper-methods-18_3_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="01-helper-methods-18_3_1-choice_1-label" for="input_01-helper-methods-18_3_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_01-helper-methods-18_3_1"> ""
</label>
</div>
<div class="field">
<input type="radio" name="input_01-helper-methods-18_3_1" id="input_01-helper-methods-18_3_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="01-helper-methods-18_3_1-choice_2-label" for="input_01-helper-methods-18_3_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_01-helper-methods-18_3_1"> ",a"
</label>
</div>
<div class="field">
<input type="radio" name="input_01-helper-methods-18_3_1" id="input_01-helper-methods-18_3_1_choice_3" class="field-input input-radio" value="choice_3"/><label id="01-helper-methods-18_3_1-choice_3-label" for="input_01-helper-methods-18_3_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_01-helper-methods-18_3_1"> "a,"
</label>
</div>
<div class="field">
<input type="radio" name="input_01-helper-methods-18_3_1" id="input_01-helper-methods-18_3_1_choice_4" class="field-input input-radio" value="choice_4"/><label id="01-helper-methods-18_3_1-choice_4-label" for="input_01-helper-methods-18_3_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_01-helper-methods-18_3_1"> "c,ca"
</label>
</div>
<span id="answer_01-helper-methods-18_3_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_01-helper-methods-18_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_01-helper-methods-18_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Unhelpful 1" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_01-helper-methods-18" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_01-helper-methods-18">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="01-helper-methods-18-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="01-helper-methods-18-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="01-helper-methods-18-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-2" data-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-helper-methods-19">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-request-token="7e97bb04683011ef86010214bd5530e3" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-helper-methods-19" data-block-type="problem" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_01-helper-methods-19" class="problems-wrapper" role="group"
aria-labelledby="01-helper-methods-19-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-helper-methods-19" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-helper-methods-19/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="01-helper-methods-19-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-helper-methods-19-problem-progress" tabindex="-1">
Unhelpful 2
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-helper-methods-19-problem-progress"></div>
<div class="problem">
<div>
<p>Louis fixes that problem by making partialSubsequence public:</p>
<pre>
/**
* Requires: caller must set partialSubsequence to "" before calling subsequencesLouis().
*/
public static String partialSubsequence;
</pre>
<p>Alyssa P. Hacker throws up in her mouth when she sees what Louis did. Which of these statements are true about his code?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_01-helper-methods-19_2_1">
<fieldset aria-describedby="status_01-helper-methods-19_2_1">
<div class="field">
<input type="checkbox" name="input_01-helper-methods-19_2_1[]" id="input_01-helper-methods-19_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="01-helper-methods-19_2_1-choice_0-label" for="input_01-helper-methods-19_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_01-helper-methods-19_2_1"> partialSubsequence is risky -- it should be final
</label>
</div>
<div class="field">
<input type="checkbox" name="input_01-helper-methods-19_2_1[]" id="input_01-helper-methods-19_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="01-helper-methods-19_2_1-choice_1-label" for="input_01-helper-methods-19_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_01-helper-methods-19_2_1"> partialSubsequence is risky -- it is a global variable
</label>
</div>
<div class="field">
<input type="checkbox" name="input_01-helper-methods-19_2_1[]" id="input_01-helper-methods-19_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="01-helper-methods-19_2_1-choice_2-label" for="input_01-helper-methods-19_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_01-helper-methods-19_2_1"> partialSubsequence is risky -- it points to a mutable object
</label>
</div>
<span id="answer_01-helper-methods-19_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_01-helper-methods-19_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_01-helper-methods-19_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Unhelpful 2" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_01-helper-methods-19" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_01-helper-methods-19">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="01-helper-methods-19-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="01-helper-methods-19-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="01-helper-methods-19-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-3" data-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-helper-methods-20">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-request-token="7e97bb04683011ef86010214bd5530e3" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-helper-methods-20" data-block-type="problem" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_01-helper-methods-20" class="problems-wrapper" role="group"
aria-labelledby="01-helper-methods-20-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-helper-methods-20" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-helper-methods-20/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="7"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="01-helper-methods-20-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-helper-methods-20-problem-progress" tabindex="-1">
Unhelpful 3
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-helper-methods-20-problem-progress"></div>
<div class="problem">
<div>
<p>Louis gives in to Alyssa's strenuous arguments, hides his static variable again, and takes care of initializing it properly before starting the recursion:</p>
<pre>
public static String subsequences(String word) {
partialSubsequence = "";
return subsequencesLouis(word);
}
private static String partialSubsequence = "";
public static String subsequencesLouis(String word) {
if (word.isEmpty()) {
// base case
return partialSubsequence;
} else {
// recursive step
String withoutFirstLetter = subsequencesLouis(word.substring(1));
partialSubsequence += word.charAt(0);
String withFirstLetter = subsequencesLouis(word.substring(1));
return withoutFirstLetter + "," + withFirstLetter;
}
}
</pre>
<p>Unfortunately a static variable is simply a bad idea in recursion. Louis's solution is still broken. To illustrate, let's trace through the call subsequences("xy"). It will produce these recursive calls to subsequencesLouis():</p>
<pre>
subsequencesLouis("xy")
subsequencesLouis("y")
subsequencesLouis("")
subsequencesLouis("")
subsequencesLouis("y")
subsequencesLouis("")
subsequencesLouis("")
</pre>
<p>When each of these calls starts, what is the value of the static variable partialSubsequence?</p>
<p>1. subsequencesLouis("xy")</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="inputtype option-input ">
<select name="input_01-helper-methods-20_2_1" id="input_01-helper-methods-20_2_1" aria-describedby="status_01-helper-methods-20_2_1">
<option value="option_01-helper-methods-20_2_1_dummy_default">Select an option</option>
<option value="empty string"> empty string</option>
<option value="x"> x</option>
<option value="y"> y</option>
<option value="xy"> xy</option>
<option value="yx"> yx</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_01-helper-methods-20_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
<p class="answer" id="answer_01-helper-methods-20_2_1"/>
</div></div>
<p>2. subsequencesLouis("y")</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div class="inputtype option-input ">
<select name="input_01-helper-methods-20_3_1" id="input_01-helper-methods-20_3_1" aria-describedby="status_01-helper-methods-20_3_1">
<option value="option_01-helper-methods-20_3_1_dummy_default">Select an option</option>
<option value="empty string"> empty string</option>
<option value="x"> x</option>
<option value="y"> y</option>
<option value="xy"> xy</option>
<option value="yx"> yx</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_01-helper-methods-20_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
<p class="answer" id="answer_01-helper-methods-20_3_1"/>
</div></div>
<p>3. subsequencesLouis("")</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 3" role="group"><div class="inputtype option-input ">
<select name="input_01-helper-methods-20_4_1" id="input_01-helper-methods-20_4_1" aria-describedby="status_01-helper-methods-20_4_1">
<option value="option_01-helper-methods-20_4_1_dummy_default">Select an option</option>
<option value="empty string"> empty string</option>
<option value="x"> x</option>
<option value="y"> y</option>
<option value="xy"> xy</option>
<option value="yx"> yx</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_01-helper-methods-20_4_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
<p class="answer" id="answer_01-helper-methods-20_4_1"/>
</div></div>
<p>4. subsequencesLouis("")</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 4" role="group"><div class="inputtype option-input ">
<select name="input_01-helper-methods-20_5_1" id="input_01-helper-methods-20_5_1" aria-describedby="status_01-helper-methods-20_5_1">
<option value="option_01-helper-methods-20_5_1_dummy_default">Select an option</option>
<option value="empty string"> empty string</option>
<option value="x"> x</option>
<option value="y"> y</option>
<option value="xy"> xy</option>
<option value="yx"> yx</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_01-helper-methods-20_5_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
<p class="answer" id="answer_01-helper-methods-20_5_1"/>
</div></div>
<p>5. subsequencesLouis("y")</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 5" role="group"><div class="inputtype option-input ">
<select name="input_01-helper-methods-20_6_1" id="input_01-helper-methods-20_6_1" aria-describedby="status_01-helper-methods-20_6_1">
<option value="option_01-helper-methods-20_6_1_dummy_default">Select an option</option>
<option value="empty string"> empty string</option>
<option value="x"> x</option>
<option value="y"> y</option>
<option value="xy"> xy</option>
<option value="yx"> yx</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_01-helper-methods-20_6_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
<p class="answer" id="answer_01-helper-methods-20_6_1"/>
</div></div>
<p>6. subsequencesLouis("")</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 6" role="group"><div class="inputtype option-input ">
<select name="input_01-helper-methods-20_7_1" id="input_01-helper-methods-20_7_1" aria-describedby="status_01-helper-methods-20_7_1">
<option value="option_01-helper-methods-20_7_1_dummy_default">Select an option</option>
<option value="empty string"> empty string</option>
<option value="x"> x</option>
<option value="y"> y</option>
<option value="xy"> xy</option>
<option value="yx"> yx</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_01-helper-methods-20_7_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
<p class="answer" id="answer_01-helper-methods-20_7_1"/>
</div></div>
<p>7. subsequencesLouis("")</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 7" role="group"><div class="inputtype option-input ">
<select name="input_01-helper-methods-20_8_1" id="input_01-helper-methods-20_8_1" aria-describedby="status_01-helper-methods-20_8_1">
<option value="option_01-helper-methods-20_8_1_dummy_default">Select an option</option>
<option value="empty string"> empty string</option>
<option value="x"> x</option>
<option value="y"> y</option>
<option value="xy"> xy</option>
<option value="yx"> yx</option>
<option value="yxy"> yxy</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_01-helper-methods-20_8_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
<p class="answer" id="answer_01-helper-methods-20_8_1"/>
</div></div>
<div class="solution-span">
<span id="solution_01-helper-methods-20_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Unhelpful 3" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_01-helper-methods-20" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_01-helper-methods-20">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="01-helper-methods-20-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="01-helper-methods-20-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="01-helper-methods-20-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="7e97bb04683011ef86010214bd5530e3" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@Choosing_the_Right_Recursive_Subproblem" data-block-type="vertical" data-graded="True" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-version="1">
<h2 class="hd hd-2 unit-title">Choosing the Right Recursive Subproblem</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_d368c68bc069">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="7e97bb04683011ef86010214bd5530e3" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_d368c68bc069" data-block-type="html" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<h2 id="choosing_the_right_recursive_subproblem">Choosing the Right Recursive Subproblem</h2>
<div data-outline="choosing_the_right_recursive_subproblem">
<p>Let's look at another example. Suppose we want to convert an integer to a string representation with a given base, following this spec:</p><pre><code class="language-java hljs"><span class="hljs-comment handout-javadoc-comment">/**
* <span class="hljs-doctag">@param</span> n integer to convert to string
* <span class="hljs-doctag">@param</span> base base for the representation. Requires 2<=base<=10.
* <span class="hljs-doctag">@return</span> n represented as a string of digits in the specified base, with
* a minus sign if n<0.
*/</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> String <span class="hljs-title">stringValue</span><span class="hljs-params">(<span class="hljs-keyword">int</span> n, <span class="hljs-keyword">int</span> base)</span></span></code></pre>
<p>For example, <code>stringValue(16, 10)</code> should return <code>"16"</code>, and <code>stringValue(16, 2)</code> should return <code>"10000"</code>.</p>
<p>Let's develop a recursive implementation of this method. One recursive step here is straightforward: we can handle negative integers simply by recursively calling for the representation of the corresponding positive integer:</p><pre><code class="hljs cpp"><span class="hljs-keyword">if</span> (n < <span class="hljs-number">0</span>) <span class="hljs-keyword">return</span> <span class="hljs-string">"-"</span> + stringValue(-n, base);</code></pre>
<p>This shows that the recursive subproblem can be smaller or simpler in more subtle ways than just the value of a numeric parameter or the size of a string or list parameter. We have still effectively reduced the problem by reducing it to positive integers. </p>
<p>The next question is, given that we have a positive n, say n=829 in base 10, how should we decompose it into a recursive subproblem? Thinking about the number as we would write it down on paper, we could either start with 8 (the leftmost or highest-order digit), or 9 (the rightmost, lower-order digit). Starting at the left end seems natural, because that's the direction we write, but it's harder in this case, because we would need to first find the number of digits in the number to figure out how to extract the leftmost digit. Instead, a better way to decompose n is to take its remainder modulo base (which gives the <em>rightmost</em> digit) and also divide by base (which gives the subproblem, the remaining higher-order digits):</p><pre><code class="hljs cs"><span class="hljs-keyword">return</span> stringValue(n/<span class="hljs-keyword">base</span>, <span class="hljs-keyword">base</span>) + <span class="hljs-string">"0123456789"</span>.charAt(n%<span class="hljs-keyword">base</span>);</code></pre>
<p><strong>Think about several ways to break down the problem, and try to write the recursive steps.</strong> You want to find the one that produces the simplest, most natural recursive step.</p>
<p>It remains to figure out what the base case is, and include an if statement that distinguishes the base case from this recursive step.</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="7e97bb04683011ef86010214bd5530e3" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@vertical_Questions_de88e9f97099" data-block-type="vertical" data-graded="True" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-version="1">
<h2 class="hd hd-2 unit-title">Questions</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@Choosing_the_Subproblem">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="7e97bb04683011ef86010214bd5530e3" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@Choosing_the_Subproblem" data-block-type="html" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<script src="/assets/courseware/v1/c9cee8830885f59e75b8782f44026226/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/edx-script-v1.js"></script>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-choosing-the-subproblem-16">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-request-token="7e97bb04683011ef86010214bd5530e3" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-choosing-the-subproblem-16" data-block-type="problem" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_01-choosing-the-subproblem-16" class="problems-wrapper" role="group"
aria-labelledby="01-choosing-the-subproblem-16-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-choosing-the-subproblem-16" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-choosing-the-subproblem-16/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="01-choosing-the-subproblem-16-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-choosing-the-subproblem-16-problem-progress" tabindex="-1">
Implementing stringValue
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-choosing-the-subproblem-16-problem-progress"></div>
<div class="problem">
<div>
<p>Here is the recursive implementation of <code>stringValue()</code> from the reading, with the recursive steps brought together but with the base case still missing:</p>
<pre>
/**
* @param n integer to convert to string
* @param base base for the representation. Requires 2&lt;=base&lt;=10.
* @return n represented as a string of digits in the specified base, with
* a minus sign if n&lt;0. No unnecessary leading zeros are included.
*/
public static String stringValue(int n, int base) {
if (n &lt; 0) { return "-" + stringValue(-n, base); }
else if (CONDITION) { BASE CASE }
else { return stringValue(n/base, base) + "0123456789".charAt(n%base); }
}
</pre>
<p>Which of the following lines can be substituted <code>else if (CONDITIO) { BASE CASE }</code> to make the code correct?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_01-choosing-the-subproblem-16_2_1">
<fieldset aria-describedby="status_01-choosing-the-subproblem-16_2_1">
<div class="field">
<input value="choice_0" class="field-input input-checkbox" id="input_01-choosing-the-subproblem-16_2_1_choice_0" name="input_01-choosing-the-subproblem-16_2_1[]" type="checkbox"/><label class="response-label field-label label-inline" id="01-choosing-the-subproblem-16_2_1-choice_0-label" aria-describedby="status_01-choosing-the-subproblem-16_2_1" for="input_01-choosing-the-subproblem-16_2_1_choice_0"> else if (n == 0) { return "0"; }
</label>
</div>
<div class="field">
<input value="choice_1" class="field-input input-checkbox" id="input_01-choosing-the-subproblem-16_2_1_choice_1" name="input_01-choosing-the-subproblem-16_2_1[]" type="checkbox"/><label class="response-label field-label label-inline" id="01-choosing-the-subproblem-16_2_1-choice_1-label" aria-describedby="status_01-choosing-the-subproblem-16_2_1" for="input_01-choosing-the-subproblem-16_2_1_choice_1"> else if (n &lt; base) { return "" + n; }
</label>
</div>
<div class="field">
<input value="choice_2" class="field-input input-checkbox" id="input_01-choosing-the-subproblem-16_2_1_choice_2" name="input_01-choosing-the-subproblem-16_2_1[]" type="checkbox"/><label class="response-label field-label label-inline" id="01-choosing-the-subproblem-16_2_1-choice_2-label" aria-describedby="status_01-choosing-the-subproblem-16_2_1" for="input_01-choosing-the-subproblem-16_2_1_choice_2"> else if (n == 0) { return ""; }
</label>
</div>
<div class="field">
<input value="choice_3" class="field-input input-checkbox" id="input_01-choosing-the-subproblem-16_2_1_choice_3" name="input_01-choosing-the-subproblem-16_2_1[]" type="checkbox"/><label class="response-label field-label label-inline" id="01-choosing-the-subproblem-16_2_1-choice_3-label" aria-describedby="status_01-choosing-the-subproblem-16_2_1" for="input_01-choosing-the-subproblem-16_2_1_choice_3"> else if (n &lt; base) { return "0123456789".substring(n,n+1); }
</label>
</div>
<span id="answer_01-choosing-the-subproblem-16_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_01-choosing-the-subproblem-16_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_01-choosing-the-subproblem-16_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Implementing stringValue" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_01-choosing-the-subproblem-16" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_01-choosing-the-subproblem-16">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="01-choosing-the-subproblem-16-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="01-choosing-the-subproblem-16-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="01-choosing-the-subproblem-16-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-2" data-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-choosing-the-subproblem-17">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-request-token="7e97bb04683011ef86010214bd5530e3" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-choosing-the-subproblem-17" data-block-type="problem" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_01-choosing-the-subproblem-17" class="problems-wrapper" role="group"
aria-labelledby="01-choosing-the-subproblem-17-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-choosing-the-subproblem-17" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-choosing-the-subproblem-17/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="01-choosing-the-subproblem-17-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-choosing-the-subproblem-17-problem-progress" tabindex="-1">
Calling stringValue
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-choosing-the-subproblem-17-problem-progress"></div>
<div class="problem">
<div>
<p>Assuming the code is completed with one of the base cases identified in the previous problem, what does stringValue(170, 16) do?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_01-choosing-the-subproblem-17_2_1">
<fieldset aria-describedby="status_01-choosing-the-subproblem-17_2_1">
<div class="field">
<input type="checkbox" name="input_01-choosing-the-subproblem-17_2_1[]" id="input_01-choosing-the-subproblem-17_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="01-choosing-the-subproblem-17_2_1-choice_0-label" for="input_01-choosing-the-subproblem-17_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_01-choosing-the-subproblem-17_2_1"> returns "AA"
</label>
</div>
<div class="field">
<input type="checkbox" name="input_01-choosing-the-subproblem-17_2_1[]" id="input_01-choosing-the-subproblem-17_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="01-choosing-the-subproblem-17_2_1-choice_1-label" for="input_01-choosing-the-subproblem-17_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_01-choosing-the-subproblem-17_2_1"> returns "170"
</label>
</div>
<div class="field">
<input type="checkbox" name="input_01-choosing-the-subproblem-17_2_1[]" id="input_01-choosing-the-subproblem-17_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="01-choosing-the-subproblem-17_2_1-choice_2-label" for="input_01-choosing-the-subproblem-17_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_01-choosing-the-subproblem-17_2_1"> returns "1010"
</label>
</div>
<div class="field">
<input type="checkbox" name="input_01-choosing-the-subproblem-17_2_1[]" id="input_01-choosing-the-subproblem-17_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="01-choosing-the-subproblem-17_2_1-choice_3-label" for="input_01-choosing-the-subproblem-17_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_01-choosing-the-subproblem-17_2_1"> throws StringIndexOutOfBoundsException
</label>
</div>
<div class="field">
<input type="checkbox" name="input_01-choosing-the-subproblem-17_2_1[]" id="input_01-choosing-the-subproblem-17_2_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="01-choosing-the-subproblem-17_2_1-choice_4-label" for="input_01-choosing-the-subproblem-17_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_01-choosing-the-subproblem-17_2_1"> doesn't compile, static error
</label>
</div>
<div class="field">
<input type="checkbox" name="input_01-choosing-the-subproblem-17_2_1[]" id="input_01-choosing-the-subproblem-17_2_1_choice_5" class="field-input input-checkbox" value="choice_5"/><label id="01-choosing-the-subproblem-17_2_1-choice_5-label" for="input_01-choosing-the-subproblem-17_2_1_choice_5" class="response-label field-label label-inline" aria-describedby="status_01-choosing-the-subproblem-17_2_1"> StackOverflowError
</label>
</div>
<div class="field">
<input type="checkbox" name="input_01-choosing-the-subproblem-17_2_1[]" id="input_01-choosing-the-subproblem-17_2_1_choice_6" class="field-input input-checkbox" value="choice_6"/><label id="01-choosing-the-subproblem-17_2_1-choice_6-label" for="input_01-choosing-the-subproblem-17_2_1_choice_6" class="response-label field-label label-inline" aria-describedby="status_01-choosing-the-subproblem-17_2_1"> infinite loop
</label>
</div>
<span id="answer_01-choosing-the-subproblem-17_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_01-choosing-the-subproblem-17_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_01-choosing-the-subproblem-17_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Calling stringValue" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_01-choosing-the-subproblem-17" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_01-choosing-the-subproblem-17">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="01-choosing-the-subproblem-17-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="01-choosing-the-subproblem-17-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="01-choosing-the-subproblem-17-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="7e97bb04683011ef86010214bd5530e3" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@Recursive_Problems_vs._Recursive_Data" data-block-type="vertical" data-graded="True" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-version="1">
<h2 class="hd hd-2 unit-title">Recursive Problems vs. Recursive Data</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_5f29e710b009">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="7e97bb04683011ef86010214bd5530e3" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_5f29e710b009" data-block-type="html" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<h2 id="recursive_problems_vs_recursive_data">Recursive Problems vs. Recursive Data</h2>
<div data-outline="recursive_problems_vs_recursive_data">
<p>The examples we've seen so far have been cases where the problem structure lends itself naturally to a recursive definition. Factorial is easy to define in terms of smaller subproblems. Having a <em>recursive problem</em> like this is one cue that you should pull a recursive solution out of your toolbox. </p>
<p>Another cue is when the data you are operating on is inherently recursive in structure. We'll see many examples of recursive data a few classes from now, but for now let's look at the recursive data found in every laptop computer: its filesystem. A filesystem consists of named <em>files</em>. Some files are <em>folders</em>, which can contain other files. So a filesystem is recursive: folders contain other folders which contain other folders, until finally at the bottom of the recursion are plain (non-folder) files.</p>
<p>The Java library represents the file system using <a href="http://docs.oracle.com/javase/8/docs/api/index.html?java/io/File.html"><code>java.io.File</code></a>. This is a recursive data type, in the sense that <code>f.getParentFile()</code> returns the parent folder of a file <code>f</code>, which is a <code>File</code> object as well, and <code>f.listFiles()</code> returns the files contained by <code>f</code>, which is an array of other <code>File</code> objects.</p>
<p>For recursive data, it's natural to write recursive implementations:</p><pre><code class="language-java hljs"><span class="hljs-comment handout-javadoc-comment">/**
* <span class="hljs-doctag">@param</span> f a file in the filesystem
* <span class="hljs-doctag">@return</span> the full pathname of f from the root of the filesystem
*/</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> String <span class="hljs-title">fullPathname</span><span class="hljs-params">(File f)</span> </span>{
<span class="hljs-keyword">if</span> (f.getParentFile() == <span class="hljs-keyword">null</span>) {
<span class="hljs-comment">// base case: f is at the root of the filesystem</span>
<span class="hljs-keyword">return</span> f.getName();
} <span class="hljs-keyword">else</span> {
<span class="hljs-comment">// recursive step</span>
<span class="hljs-keyword">return</span> fullPathname(f.getParentFile()) + <span class="hljs-string">"/"</span> + f.getName();
}
}</code></pre>
<p>Recent versions of Java have added a new API, <a href="http://docs.oracle.com/javase/8/docs/api/index.html?java/nio/file/Files.html"><code>java.nio.Files</code></a> and <a href="http://docs.oracle.com/javase/8/docs/api/index.html?java/nio/file/Path.html"><code>java.nio.Path</code></a>, which offer a cleaner separation between the filesystem and the pathnames used to name files in it. But the data structure is still fundamentally recursive.</p>
</div>
<h2 id="reentrant_code">Reentrant Code</h2>
<div data-outline="reentrant_code">
<p>Recursion — a method calling itself — is a special case of a general phenomenon in programming called <strong>reentrancy</strong>. Reentrant code can be safely re-entered, meaning that it can be called again <em>even while a call to it is underway.</em> Reentrant code keeps its state entirely in parameters and local variables, and doesn't use static variables or global variables, and doesn't share aliases to mutable objects with other parts of the program, or other calls to itself.</p>
<p>Direct recursion is one way that reentrancy can happen. We've seen many examples of that during this reading. The <code>factorial()</code> method is designed so that <code>factorial(n-1)</code> can be called even though <code>factorial(n)</code> hasn't yet finished working.</p>
<p>Mutual recursion between two or more functions is another way this can happen — A calls B, which calls A again. Direct mutual recursion is virtually always intentional and designed by the programmer. But unexpected mutual recursion can lead to bugs.</p>
<p>When we talk about concurrency later in the course, reentrancy will come up again, since in a concurrent program, a method may be called at the same time by different parts of the program that are running concurrently.</p>
<p>It's good to design your code to be reentrant as much as possible. Reentrant code is safer from bugs and can be used in more situations, like concurrency, callbacks, or mutual recursion.</p>
</div>
<h2 id="when_to_use_recursion_rather_than_iteration">When to Use Recursion Rather Than Iteration</h2>
<div data-outline="when_to_use_recursion_rather_than_iteration">
<p>We've seen two common reasons for using recursion:</p>
<ul>
<li>The problem is naturally recursive (e.g. Fibonacci)</li>
<li>The data is naturally recursive (e.g. filesystem)</li>
</ul>
<p>Another reason to use recursion is to take more advantage of immutability. In an ideal recursive implementation, all variables are final, all data is immutable, and the recursive methods are all pure functions in the sense that they do not mutate anything. The behavior of a method can be understood simply as a relationship between its parameters and its return value, with no side effects on any other part of the program. This kind of paradigm is called <em>functional programming</em>, and it is far easier to reason about than <em>imperative programming</em> with loops and variables.</p>
<p>In iterative implementations, by contrast, you inevitably have non-final variables or mutable objects that are modified during the course of the iteration. Reasoning about the program then requires thinking about snapshots of the program state at various points in time, rather than thinking about pure input/output behavior. </p>
<p>One downside of recursion is that it may take more space than an iterative solution. Building up a stack of recursive calls consumes memory temporarily, and the stack is limited in size, which may become a limit on the size of the problem that your recursive implementation can solve.</p>
</div>
<h2 id="common_mistakes_in_recursive_implementations">Common Mistakes in Recursive Implementations</h2>
<div data-outline="common_mistakes_in_recursive_implementations">
<p>Here are two common ways that a recursive implementation can go wrong:</p>
<ul>
<li>The base case is missing entirely, or the problem needs more than one base case but not all the base cases are covered.</li>
<li>The recursive step doesn't reduce to a smaller subproblem, so the recursion doesn't converge.</li>
</ul>
<p>Look for these when you're debugging.</p>
<p>On the bright side, what would be an infinite loop in an iterative implementation usually becomes a <code>StackOverflowError</code> in a recursive implementation. A buggy recursive program fails faster.</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="7e97bb04683011ef86010214bd5530e3" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@vertical_Questions_fc0f259c03cf" data-block-type="vertical" data-graded="True" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-version="1">
<h2 class="hd hd-2 unit-title">Questions</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@Recursion_Again">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="7e97bb04683011ef86010214bd5530e3" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@Recursion_Again" data-block-type="html" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<script src="/assets/courseware/v1/c9cee8830885f59e75b8782f44026226/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/edx-script-v1.js"></script>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-recursion-again-21">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-request-token="7e97bb04683011ef86010214bd5530e3" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-recursion-again-21" data-block-type="problem" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_01-recursion-again-21" class="problems-wrapper" role="group"
aria-labelledby="01-recursion-again-21-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-recursion-again-21" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-recursion-again-21/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="01-recursion-again-21-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-recursion-again-21-problem-progress" tabindex="-1">
subsequences again
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@01-recursion-again-21-problem-progress"></div>
<div class="problem">
<div>
<p>Recall this implementation of subsequences() from the start of the reading:</p>
<pre>
public static String subsequences(String word) {
if (word.isEmpty()) {
return ""; // base case
} else {
char firstLetter = word.charAt(0);
String restOfWord = word.substring(1);
String subsequencesOfRest = subsequences(restOfWord);
String result = "";
for (String subsequence : subsequencesOfRest.split(",", -1)) {
result += "," + subsequence;
result += "," + firstLetter + subsequence;
}
if (result.startsWith(",")) result = result.substring(1);
return result;
}
}
</pre>
<p>For subsequences("123456"), how deep does its recursive call stack get? How many recursive calls to subsequences() can be active at the same time?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div id="formulaequationinput_01-recursion-again-21_2_1" class="inputtype formulaequationinput">
<div class="unanswered">
<input type="text" name="input_01-recursion-again-21_2_1" id="input_01-recursion-again-21_2_1" data-input-id="01-recursion-again-21_2_1" value="" aria-describedby="status_01-recursion-again-21_2_1" size="20"/>
<span class="trailing_text" id="trailing_text_01-recursion-again-21_2_1"/>
<span class="status unanswered" id="status_01-recursion-again-21_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_01-recursion-again-21_2_1" class="answer"/>
<div id="input_01-recursion-again-21_2_1_preview" class="equation">
\(\)
<img src="/static/images/spinner.bc34f953403f.gif" class="loading" alt="Loading"/>
</div>
</div>
<div class="script_placeholder" data-src="/static/js/capa/src/formula_equation_preview.b1967ab28c31.js"/>
</div></div>
<div class="solution-span">
<span id="solution_01-recursion-again-21_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="subsequences again" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_01-recursion-again-21" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_01-recursion-again-21">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="01-recursion-again-21-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="01-recursion-again-21-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="01-recursion-again-21-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="7e97bb04683011ef86010214bd5530e3" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@Reading_1_Summary" data-block-type="vertical" data-graded="True" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-version="1">
<h2 class="hd hd-2 unit-title">Reading 1 Summary</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_bbef140e5cb4">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-request-token="7e97bb04683011ef86010214bd5530e3" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_bbef140e5cb4" data-block-type="html" data-graded="True" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-version="1">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<h2 id="summary">Summary</h2>
<div data-outline="summary">
<p>We saw these ideas:</p>
<ul>
<li>recursive problems and recursive data</li>
<li>comparing alternative decompositions of a recursive problem</li>
<li>using helper methods to strengthen a recursive step</li>
<li>recursion vs. iteration</li>
</ul>
<p>The topics of today's reading connect to our three key properties of good software as follows:</p>
<ul>
<li>
<p><strong>Safe from bugs.</strong> Recursive code is simpler and often uses immutable variables and immutable objects. </p>
</li>
<li>
<p><strong>Easy to understand.</strong> Recursive implementations for naturally recursive problems and recursive data are often shorter and easier to understand than iterative solutions.</p>
</li>
<li>
<p><strong>Ready for change.</strong> Recursive code is also naturally reentrant, which makes it safer from bugs and ready to use in more situations. </p>
</li>
</ul>
</div>
<div class="license">This reading was collaboratively authored with contributions from: Saman Amarasinghe, Adam Chlipala, Srini Devadas, Michael Ernst, Max Goldman, John Guttag, Daniel Jackson, Rob Miller, Martin Rinard, and Armando Solar-Lezama. This work is licensed under <a rel="license" href="http://creativecommons.org/licenses/by-sa/4.0/">CC BY-SA 4.0</a>.</div>
</div>
</div>
</div>
</div>