-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathREADME-L0.html
More file actions
524 lines (432 loc) · 20.4 KB
/
README-L0.html
File metadata and controls
524 lines (432 loc) · 20.4 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta name="generated-by" content="Markdown PRO, http://markdownpro.com"/>
<title></title>
<style type="text/css">
html,body{margin:0;padding:0;}
body {padding: 20px}
h1,h2,h3,h4,h5,h6,p,blockquote,pre,a,abbr,acronym,address,cite,code,del,dfn,em,img,q,s,samp,small,strike,strong,sub,sup,tt,var,dd,dl,dt,li,ol,ul,fieldset,form,label,legend,button,table,caption,tbody,tfoot,thead,tr,th,td{margin:0;padding:0;border:0;font-weight:normal;font-style:normal;font-size:100%;line-height:1;font-family:inherit;}
table{border-collapse:collapse;border-spacing:0;}
ol,ul{list-style:none;}
q:before,q:after,blockquote:before,blockquote:after{content:"";}
html{overflow-y:scroll;font-size:100%;-webkit-text-size-adjust:100%;-ms-text-size-adjust:100%;}
a:focus{outline:thin dotted;}
a:hover,a:active{outline:0;}
article,aside,details,figcaption,figure,footer,header,hgroup,nav,section{display:block;}
audio,canvas,video{display:inline-block;*display:inline;*zoom:1;}
audio:not([controls]){display:none;}
sub,sup{font-size:75%;line-height:0;position:relative;vertical-align:baseline;}
sup{top:-0.5em;}
sub{bottom:-0.25em;}
img{border:0;-ms-interpolation-mode:bicubic;}
button,input,select,textarea{font-size:100%;margin:0;vertical-align:baseline;*vertical-align:middle;}
button,input{line-height:normal;*overflow:visible;}
button::-moz-focus-inner,input::-moz-focus-inner{border:0;padding:0;}
button,input[type="button"],input[type="reset"],input[type="submit"]{cursor:pointer;-webkit-appearance:button;}
input[type="search"]{-webkit-appearance:textfield;-webkit-box-sizing:content-box;-moz-box-sizing:content-box;box-sizing:content-box;}
input[type="search"]::-webkit-search-decoration{-webkit-appearance:none;}
textarea{overflow:auto;vertical-align:top;}
html,body{background-color:#ffffff;}
body{margin:0;font-family:"Helvetica Neue",Helvetica,Arial,sans-serif;font-size:13px;font-weight:normal;line-height:18px;color:#404040;}
.container{width:940px;margin-left:auto;margin-right:auto;zoom:1;}.container:before,.container:after{display:table;content:"";zoom:1;*display:inline;}
.container:after{clear:both;}
.container-fluid{position:relative;min-width:940px;padding-left:20px;padding-right:20px;zoom:1;}.container-fluid:before,.container-fluid:after{display:table;content:"";zoom:1;*display:inline;}
.container-fluid:after{clear:both;}
.container-fluid>.sidebar{float:left;width:220px;}
.container-fluid>.content{margin-left:240px;}
a{color:#0069d6;text-decoration:none;line-height:inherit;font-weight:inherit;}a:hover{color:#00438a;text-decoration:underline;}
.pull-right{float:right;}
.pull-left{float:left;}
.hide{display:none;}
.show{display:block;}
.row{zoom:1;margin-left:-20px;}.row:before,.row:after{display:table;content:"";zoom:1;*display:inline;}
.row:after{clear:both;}
p{font-size:13px;font-weight:normal;line-height:18px;margin-bottom:9px;}p small{font-size:11px;color:#bfbfbf;}
h1,h2,h3,h4,h5,h6{font-weight:bold;color:#404040;}h1 small,h2 small,h3 small,h4 small,h5 small,h6 small{color:#bfbfbf;}
h1{margin-bottom:18px;font-size:30px;line-height:36px;}h1 small{font-size:18px;}
h2{font-size:24px;line-height:36px;}h2 small{font-size:14px;}
h3,h4,h5,h6{line-height:36px;}
h3{font-size:18px;}h3 small{font-size:14px;}
h4{font-size:16px;}h4 small{font-size:12px;}
h5{font-size:14px;}
h6{font-size:13px;color:#bfbfbf;text-transform:uppercase;}
ul,ol{margin:0 0 18px 25px;}
ul ul,ul ol,ol ol,ol ul{margin-bottom:0;}
ul{list-style:disc;}
ol{list-style:decimal;}
li{line-height:18px;color:#808080;}
ul.unstyled{list-style:none;margin-left:0;}
dl{margin-bottom:18px;}dl dt,dl dd{line-height:18px;}
dl dt{font-weight:bold;}
dl dd{margin-left:9px;}
hr{margin:20px 0 19px;border:0;border-bottom:1px solid #eee;}
strong{font-style:inherit;font-weight:bold;}
em{font-style:italic;font-weight:inherit;line-height:inherit;}
.muted{color:#bfbfbf;}
blockquote{margin-bottom:18px;border-left:5px solid #eee;padding-left:15px;}blockquote p{font-size:14px;font-weight:300;line-height:18px;margin-bottom:0;}
blockquote small{display:block;font-size:12px;font-weight:300;line-height:18px;color:#bfbfbf;}blockquote small:before{content:'\2014 \00A0';}
address{display:block;line-height:18px;margin-bottom:18px;}
code,pre{padding:0 3px 2px;font-family:Monaco, Andale Mono, Courier New, monospace;font-size:12px;-webkit-border-radius:3px;-moz-border-radius:3px;border-radius:3px;}
code{padding:1px 3px;}
pre{background-color:#f5f5f5;display:block;padding:8.5px;margin:0 0 18px;line-height:18px;font-size:12px;border:1px solid #ccc;border:1px solid rgba(0, 0, 0, 0.15);-webkit-border-radius:3px;-moz-border-radius:3px;border-radius:3px;white-space:pre;white-space:pre-wrap;word-wrap:break-word;}
form{margin-bottom:18px;}
fieldset{margin-bottom:18px;padding-top:18px;}fieldset legend{display:block;padding-left:150px;font-size:19.5px;line-height:1;color:#404040;*padding:0 0 5px 145px;*line-height:1.5;}
form .clearfix{margin-bottom:18px;zoom:1;}form .clearfix:before,form .clearfix:after{display:table;content:"";zoom:1;*display:inline;}
form .clearfix:after{clear:both;}
label,input,select,textarea{font-family:"Helvetica Neue",Helvetica,Arial,sans-serif;font-size:13px;font-weight:normal;line-height:normal;}
label{padding-top:6px;font-size:13px;line-height:18px;float:left;width:130px;text-align:right;color:#404040;}
form .input{margin-left:150px;}
input[type=checkbox],input[type=radio]{cursor:pointer;}
input,textarea,select,.uneditable-input{display:inline-block;width:210px;height:18px;padding:4px;font-size:13px;line-height:18px;color:#808080;border:1px solid #ccc;-webkit-border-radius:3px;-moz-border-radius:3px;border-radius:3px;}
input[type=checkbox],input[type=radio]{width:auto;height:auto;padding:0;margin:3px 0;*margin-top:0;line-height:normal;border:none;}
input[type=file]{background-color:#ffffff;padding:initial;border:initial;line-height:initial;-webkit-box-shadow:none;-moz-box-shadow:none;box-shadow:none;}
input[type=button],input[type=reset],input[type=submit]{width:auto;height:auto;}
select,input[type=file]{height:27px;line-height:27px;*margin-top:4px;}
select[multiple]{height:inherit;}
textarea{height:auto;}
.uneditable-input{background-color:#ffffff;display:block;border-color:#eee;-webkit-box-shadow:inset 0 1px 2px rgba(0, 0, 0, 0.025);-moz-box-shadow:inset 0 1px 2px rgba(0, 0, 0, 0.025);box-shadow:inset 0 1px 2px rgba(0, 0, 0, 0.025);cursor:not-allowed;}
:-moz-placeholder{color:#bfbfbf;}
::-webkit-input-placeholder{color:#bfbfbf;}
input,textarea{-webkit-transition:border linear 0.2s,box-shadow linear 0.2s;-moz-transition:border linear 0.2s,box-shadow linear 0.2s;-ms-transition:border linear 0.2s,box-shadow linear 0.2s;-o-transition:border linear 0.2s,box-shadow linear 0.2s;transition:border linear 0.2s,box-shadow linear 0.2s;-webkit-box-shadow:inset 0 1px 3px rgba(0, 0, 0, 0.1);-moz-box-shadow:inset 0 1px 3px rgba(0, 0, 0, 0.1);box-shadow:inset 0 1px 3px rgba(0, 0, 0, 0.1);}
input:focus,textarea:focus{outline:0;border-color:rgba(82, 168, 236, 0.8);-webkit-box-shadow:inset 0 1px 3px rgba(0, 0, 0, 0.1),0 0 8px rgba(82, 168, 236, 0.6);-moz-box-shadow:inset 0 1px 3px rgba(0, 0, 0, 0.1),0 0 8px rgba(82, 168, 236, 0.6);box-shadow:inset 0 1px 3px rgba(0, 0, 0, 0.1),0 0 8px rgba(82, 168, 236, 0.6);}
input[type=file]:focus,input[type=checkbox]:focus,select:focus{-webkit-box-shadow:none;-moz-box-shadow:none;box-shadow:none;outline:1px dotted #666;}
form div.clearfix.error{background:#fae5e3;padding:10px 0;margin:-10px 0 10px;-webkit-border-radius:4px;-moz-border-radius:4px;border-radius:4px;}form div.clearfix.error>label,form div.clearfix.error span.help-inline,form div.clearfix.error span.help-block{color:#9d261d;}
form div.clearfix.error input,form div.clearfix.error textarea{border-color:#c87872;-webkit-box-shadow:0 0 3px rgba(171, 41, 32, 0.25);-moz-box-shadow:0 0 3px rgba(171, 41, 32, 0.25);box-shadow:0 0 3px rgba(171, 41, 32, 0.25);}form div.clearfix.error input:focus,form div.clearfix.error textarea:focus{border-color:#b9554d;-webkit-box-shadow:0 0 6px rgba(171, 41, 32, 0.5);-moz-box-shadow:0 0 6px rgba(171, 41, 32, 0.5);box-shadow:0 0 6px rgba(171, 41, 32, 0.5);}
form div.clearfix.error .input-prepend span.add-on,form div.clearfix.error .input-append span.add-on{background:#f4c8c5;border-color:#c87872;color:#b9554d;}
table{width:100%;margin-bottom:18px;padding:0;border-collapse:separate;*border-collapse:collapse;font-size:13px;border:1px solid #ddd;-webkit-border-radius:4px;-moz-border-radius:4px;border-radius:4px;}table th,table td{padding:10px 10px 9px;line-height:18px;text-align:left;}
table th{padding-top:9px;font-weight:bold;vertical-align:middle;border-bottom:1px solid #ddd;}
table td{vertical-align:top;}
table th+th,table td+td{border-left:1px solid #ddd;}
table tr+tr td{border-top:1px solid #ddd;}
table tbody tr:first-child td:first-child{-webkit-border-radius:4px 0 0 0;-moz-border-radius:4px 0 0 0;border-radius:4px 0 0 0;}
table tbody tr:first-child td:last-child{-webkit-border-radius:0 4px 0 0;-moz-border-radius:0 4px 0 0;border-radius:0 4px 0 0;}
table tbody tr:last-child td:first-child{-webkit-border-radius:0 0 0 4px;-moz-border-radius:0 0 0 4px;border-radius:0 0 0 4px;}
table tbody tr:last-child td:last-child{-webkit-border-radius:0 0 4px 0;-moz-border-radius:0 0 4px 0;border-radius:0 0 4px 0;}
.zebra-striped tbody tr:nth-child(odd) td{background-color:#f9f9f9;}
.zebra-striped tbody tr:hover td{background-color:#f5f5f5;}
.zebra-striped .header{cursor:pointer;}.zebra-striped .header:after{content:"";float:right;margin-top:7px;border-width:0 4px 4px;border-style:solid;border-color:#000 transparent;visibility:hidden;}
.zebra-striped .header:hover:after{visibility:visible;}
footer{margin-top:17px;padding-top:17px;border-top:1px solid #eee;}
.page-header{margin-bottom:17px;border-bottom:1px solid #ddd;-webkit-box-shadow:0 1px 0 rgba(255, 255, 255, 0.5);-moz-box-shadow:0 1px 0 rgba(255, 255, 255, 0.5);box-shadow:0 1px 0 rgba(255, 255, 255, 0.5);}.page-header h1{margin-bottom:8px;}
.close{float:right;color:#000000;font-size:20px;font-weight:bold;line-height:13.5px;text-shadow:0 1px 0 #ffffff;filter:alpha(opacity=20);-khtml-opacity:0.2;-moz-opacity:0.2;opacity:0.2;}.close:hover{color:#000000;text-decoration:none;filter:alpha(opacity=40);-khtml-opacity:0.4;-moz-opacity:0.4;opacity:0.4;}
pre {
padding: 0;
margin: 10px 0px 10px;
overflow: auto; /*--If the Code exceeds the width, a scrolling is available--*/
overflow-Y: hidden; /*--Hides vertical scroll created by IE--*/
}
pre code {
margin: 5px; /*--Left Margin--*/
padding: 0px;
display: block;
line-height: 18px;
}
.center { text-align:center}
.left {text-align:left}
.right {text-align:right}
</style><style type="text/css">
body {
font-family: "Geneva", Arial, sans-serif;
font-size: 13px;
margin: 10px;
}
a, a:visited {
color: #09c;
}
a:hover {
color: #336699;
text-decoration: none;
}
h1 {
margin: 0px 0px 10px;
font-weight: bold;
}
h2 {
border-bottom: 2px dotted #ccc;
margin: 5px 0px 15px;
}
h6 {
color: #09c;
}
blockquote {
font-family: "Georgia", Courier New, courier, sans-serif;
background: #efefef;
padding: 5px 10px;
border: solid 1px #ddd;
margin: 15px;
-webkit-border-radius:6px;
-moz-border-radius:6px;
border-radius:6px;
color: #333;
}
ul, ol {
margin-bottom: 15px;
}
li {
padding: 3px;
}
code {
background-color: #f1f1f1;
color: #336699;
}
pre {
background-color: #f1f1f1;
}
pre > code {
margin: 0px;
padding: 5px;
border: 0px;
background-color: #f1f1f1;
}
</style></head>
<body>
<h1 id="toc_0">Recursion — Introduction</h1>
<h6 id="toc_1">Overview</h6>
<p>A recursive function is defined as a function that calls itself. Any iterative solution can be converted into a
recursive one. Sometimes recursion makes solving problems easier than with iterations. They don't come naturally,
however, like loops usually do. </p>
<p>Recursion is useful when the computation or action is one that solves a small piece of the overall problem, and
repeats that same computation or action until the problem is solved. Recursive functions need a way to know
when the computation is complete. To do so, all recursive functions must have a <code>base case</code>. A base case is
simply a condition that eventually executes and signals the end of the computation (or task).</p>
<p>A general outline of a recursive function looks like this:</p>
<pre><code>function(...)
1. Base Case
2. Work towards base case
3. Call function
4. Return result (if applicable)
</code></pre>
<p>There are two main kinds of recursion approaches. </p>
<ol>
<li>Pure Recursion</li>
<li>Using a Helper Function</li>
</ol>
<h5 id="toc_2">Pure Recursion</h5>
<p>Pure recursion is when a recursive function advances by calling itself. Suppose we want to count the number of items
in an array. Using the iterative approach, we might write:</p>
<p>```javascript 1.8
function getLength(input) {
let length = 0;
for (let i=0; i<input.length; i++) {
length += 1;
}
return length;
}</p>
<pre><code>
Using pure recursion, we might write this function using the code below. NOTE: In Javascript, Array.prototype.slice(1)
removes the first element and returns the rest of the array. In this way, we get a behavior similar to iterating to
the next element of the array using iteration.
```javascript 1.8
function getLengthPure(input) {
if (!input || !input.length) {
return 0;
}
return 1 + getLengthPure(input.slice(1));
}
</code></pre>
<p>In the example above:</p>
<ol>
<li><code>if</code> condition is the Base Case</li>
<li><code>(input.slice(1))</code> works towards the base case</li>
<li><code>getLengthPure(...)</code> is the recursive call</li>
<li><code>return 1 + ...</code> returns the answer</li>
</ol>
<p>The <code>return 0</code> statement terminates the recursion by returning a base value withou calling itself again.talk about it</p>
<h5 id="toc_3">Helper Function Approach</h5>
<p>We can also achieve recursion by creating a helper function. This helper function may be an inner function or another
function somewhere else. Below is an example:</p>
<p>```javascript 1.8
function countFrom1ToN(n) {
n = Math.abs(n); // Make sure n is positive</p>
<p>function countFrom1ToNRecurse(n) {
if (!n) {
return 1;
}</p>
<pre><code>countFrom1ToNRecurse(n-1);
console.log(n);
</code></pre>
<p>}</p>
<p>countFrom1ToNRecurse(n);
}</p>
<pre><code>
In this case, the format of the recursive call is the same, but the parent function does some preliminary work first
and may even create some closures to be used by the helper function.
##### Callstack
A stack is a First-In-Last-Out (FILO) structure. The CPU maintains a special stack that tracks which function call
is active and which one to return back to when its done. This is called a Call Stack. The most current function
is at the top of the stack, and the programs entry point (the first function called) is at the bottom of the call
stack.
Each function call takes up some space on the call stack. At the very least, each call will have the following
information (for more information, Google for _Activation Record_):
```text
Function: Return Address
Parameters
...
</code></pre>
<p>Each time a recursive function calls itself the new function call will have different data than the previous. When
the base case is reached, it begins <em>unwinding</em> the call stack which begins the process of working towards the goal,
vs working toward the base case.</p>
<p>Suppose the following recursive function:</p>
<p>```javascript 1.8
function log<em>1Ton(n) {
if (!n) {
return 0;
}
else {
log</em>1Ton(n - 1);
console.log(n);
}
}</p>
<pre><code>
Let us observe the call stack using the number 5 as n:
```text
Action Stack Action
------ ------------
function(5) push 5 Entry
function(n-1) push 4
function(n-1) push 3
function(n-1) push 2
function(n-1) push 1
function(n-1) push 0 Base Case
return pop 0
log(1) 1
return pop 1
log(2) 2
return pop 2
log(3) 3
return pop 3
log(4) 4
return pop 4
log(5) 5
return pop 5
...
</code></pre>
<p>As you can see, each function call keeps the value of its arguments and works with that value in the order of the
call stack. What if we wanted to log n to 1 (in reverse order)? We would make a small modification to the
above recursive function and log to the console before the recursive call:</p>
<p>```javascript 1.8
function log<em>1Ton(n) {
if (!n) {
return 0;
}
else {
console.log(n);
log</em>1Ton(n - 1);
}
}</p>
<pre><code>
```text
Action Stack Action
------ ------------
function(5) push 5 Entry
log(5) 5
function(n-1) push 4
log(4) 4
function(n-1) push 3
log(3) 3
function(n-1) push 2
log(2) 2
function(n-1) push 1
log(1) 1
function(n-1) push 0 Base Case
return pop 0
return pop 1
return pop 2
return pop 3
return pop 4
return pop 5
...
</code></pre>
<p>Lets walk through the call stack of the first example using the following array: [1, 2, 3]:</p>
<p>```javascript 1.8
function getLengthPure(input) {
if (!input || !input.length) {
return 0;
}
return 1 + getLengthPure(input.slice(1));
}</p>
<pre><code>
```text
Action Stack Action Return Variable
------ ------------ ---------------
function([1,2,3]) push [1,2,3]
function([2,3]) push [2,3]
function([3]) push [3]
function([]) push [] Base Case
return 0 pop [] 0
1 + 0 [3]
return pop [3] 1
1 + 1 [2,3]
return pop [2,3] 2
1 + 2 [1,2,3]
return pop [1,2,3] 3
...
</code></pre>
<h5 id="toc_4">Variations</h5>
<p>Sometimes it might be the case that we need an accumulation variable. We can pass that in also to be used with each
unit of computation. Imagine we want to calculate the sum of all values in an array:</p>
<p>```javascript 1.8
function calculateSum(input, n, sum) {
if (n < 0) {
return sum;
}</p>
<p>sum += input[n];
return calculateSum(input, n-1, sum);
}</p>
<pre><code>
We can eliminate the `sum` argument thus:
```javascript 1.8
function calculateSum(input, n) {
if (n < 0) {
return 0;
}
return input[n] + calculateSum(input, n-1);
}
</code></pre>
<h5 id="toc_5">If/Else Decisions</h5>
<p>Suppose we want to write a function that calculates only the sum of all even numbers in an array. We'd
need to have a way to recurse with if/else conditions. This is made really easy with the helper function
approach The following code demonstrates:</p>
<p>```javascript 1.8
function calculateEvens(input) {
let sum = 0;</p>
<p>function calculateEvensRecurse(input) {
if (!input || !input.length) {
return 0;
}</p>
<pre><code>if (input[0] % 2 == 0) {
sum += input[0];
}
calculateEvensRecurse(input.slice(1));
</code></pre>
<p>}</p>
<p>calculateEvensRecurse(input);
return sum;
}</p>
<pre><code>
In this case, we didn't even bother to return a value. We just modified a closure and eventually returned
it.
###### Edge Cases
* Multiple base cases
* Available memory (too many calls can lead to out or memory errors)
* gg
###### NOTES
* Solve the exercises using the Helper Function approach
* Visualize the call stack if needed
* Don't expect perfection. It is hard to write a recursive function at first
###### This Exercise
Open [recursion-L0.js](ES6/src/recursion-L0.js) and follow the prompts below to complete the exercise. Use
the [testRunner0.html](ES6/testRunner0.html) file to run the tests and view your progress.
###### Objective
* Practice the recursion prompts.
###### Critical Whiteboard Skills
* Know your inputs
* Know your outputs
* Know your base case
* Every recursive decision must work towards the base case or it won't solve the problem
* Figure out what the repeating unit of work is
</code></pre>
</body>
</html>