0 added
0 removed
Original
2026-01-01
Modified
2026-02-21
1
<h2>Lesson notes</h2>
1
<h2>Lesson notes</h2>
2
<h3>Thinking about functions</h3>
2
<h3>Thinking about functions</h3>
3
<ul><li>You can think of functions as black boxes: a box takes a thing, does something, then spits some other thing out<ul><li>Some functions don't take anything (don't accept arguments), some don't do anything (their bodies are empty), some don't return any values.</li>
3
<ul><li>You can think of functions as black boxes: a box takes a thing, does something, then spits some other thing out<ul><li>Some functions don't take anything (don't accept arguments), some don't do anything (their bodies are empty), some don't return any values.</li>
4
<li>Our surfaceAreaCalculator takes one argument (radius), calculates the surface area and returns the result of that calculation.</li>
4
<li>Our surfaceAreaCalculator takes one argument (radius), calculates the surface area and returns the result of that calculation.</li>
5
</ul></li>
5
</ul></li>
6
<li>Functions can call other functions</li>
6
<li>Functions can call other functions</li>
7
<li>surfaceAreaCalculator can call the square function to get radius squared instead of manually multiplying radius by radius</li>
7
<li>surfaceAreaCalculator can call the square function to get radius squared instead of manually multiplying radius by radius</li>
8
<li>We create functions to make our lives easier:<ul><li>the code is easier to understand</li>
8
<li>We create functions to make our lives easier:<ul><li>the code is easier to understand</li>
9
<li>functions can be reused many times</li>
9
<li>functions can be reused many times</li>
10
</ul></li>
10
</ul></li>
11
</ul><p>Two functions together:</p>
11
</ul><p>Two functions together:</p>
12
<h3>Functions calling themselves</h3>
12
<h3>Functions calling themselves</h3>
13
<ul><li>Functions can call themselves<ul><li><strong>Function definitions</strong>are descriptions of the boxes</li>
13
<ul><li>Functions can call themselves<ul><li><strong>Function definitions</strong>are descriptions of the boxes</li>
14
<li>A real box is created when<strong>function is called</strong></li>
14
<li>A real box is created when<strong>function is called</strong></li>
15
<li>If a function calls itself, a new identical box is created</li>
15
<li>If a function calls itself, a new identical box is created</li>
16
</ul></li>
16
</ul></li>
17
<li>Number of ways to arrange n objects is n! (<a>permutations</a>)</li>
17
<li>Number of ways to arrange n objects is n! (<a>permutations</a>)</li>
18
<li>n! is defined like so: if n = 1, then<strong>n! = 1</strong>; if n > 0, then<strong>n! = n * (n-1)!</strong></li>
18
<li>n! is defined like so: if n = 1, then<strong>n! = 1</strong>; if n > 0, then<strong>n! = n * (n-1)!</strong></li>
19
</ul><h3>Recursion requirements</h3>
19
</ul><h3>Recursion requirements</h3>
20
<ol><li>A simple base case or a terminating scenario. When to stop, basically. In our example it was 1: we stop factorial calculation when we get to 1.</li>
20
<ol><li>A simple base case or a terminating scenario. When to stop, basically. In our example it was 1: we stop factorial calculation when we get to 1.</li>
21
<li>A rule to move along the recursion, to go deeper. In our case, it was n * factorial(n-1).</li>
21
<li>A rule to move along the recursion, to go deeper. In our case, it was n * factorial(n-1).</li>
22
</ol><h3>Waiting for the multiplications</h3>
22
</ol><h3>Waiting for the multiplications</h3>
23
<p>Nothing gets multiplied until we go all the way down, to the base case of factorial(1). Then we start going back up, one step at a time.</p>
23
<p>Nothing gets multiplied until we go all the way down, to the base case of factorial(1). Then we start going back up, one step at a time.</p>
24
<p>factorial(3); 3 * factorial(2); 3 * 2 * factorial(1); 3 * 2 * 1; 3 * 2; 6;</p>
24
<p>factorial(3); 3 * factorial(2); 3 * 2 * factorial(1); 3 * 2 * 1; 3 * 2; 6;</p>
25
<h3>Sidenote</h3>
25
<h3>Sidenote</h3>
26
<p>Note that 0! is 1, and the proper base case for n! is 0! In this lesson we omitted this case to make one less call and one less box to think about, since 1 * 1 is 1 anyway.</p>
26
<p>Note that 0! is 1, and the proper base case for n! is 0! In this lesson we omitted this case to make one less call and one less box to think about, since 1 * 1 is 1 anyway.</p>
27
<h3>Just for fun</h3>
27
<h3>Just for fun</h3>
28
<ol><li>There is a common joke among programmers: "<em>In order to understand recursion, you have to understand recursion</em>". Google seems to love this kind of joke. Try googling "recursion" and check out the suggestion at the top of the results page ;-)</li>
28
<ol><li>There is a common joke among programmers: "<em>In order to understand recursion, you have to understand recursion</em>". Google seems to love this kind of joke. Try googling "recursion" and check out the suggestion at the top of the results page ;-)</li>
29
<li>In order to understand recursion you must first understand recursion.</li>
29
<li>In order to understand recursion you must first understand recursion.</li>
30
</ol><h2>Recommended watching</h2>
30
</ol><h2>Recommended watching</h2>
31
<ul><li><a>What on Earth is Recursion? - Computerphile</a></li>
31
<ul><li><a>What on Earth is Recursion? - Computerphile</a></li>
32
<li><a>Recursion (Part 7 of Functional Programming in JavaScript) from Fun Fun Function</a></li>
32
<li><a>Recursion (Part 7 of Functional Programming in JavaScript) from Fun Fun Function</a></li>
33
</ul><h2>Optional reading</h2>
33
</ul><h2>Optional reading</h2>
34
<ul><li><a>Properties of recursive algorithms</a></li>
34
<ul><li><a>Properties of recursive algorithms</a></li>
35
</ul><h2>Optional watching</h2>
35
</ul><h2>Optional watching</h2>
36
<ul><li><a>Fibonacci Programming - Computerphile</a></li>
36
<ul><li><a>Fibonacci Programming - Computerphile</a></li>
37
</ul><h2>Lesson transcript</h2>
37
</ul><h2>Lesson transcript</h2>
38
<p>We have a function surfaceAreaCalculator that accepts one argument - a radius - and returns a surface area of a corresponding sphere using a formula 4 * pi * r^2. Remember, we can think about functions as boxes: put a thing in the box, the box does something and spits out the result.</p>
38
<p>We have a function surfaceAreaCalculator that accepts one argument - a radius - and returns a surface area of a corresponding sphere using a formula 4 * pi * r^2. Remember, we can think about functions as boxes: put a thing in the box, the box does something and spits out the result.</p>
39
<p>Some boxes don't accept anything, some - don't spit out anything, and some don't even do anything, but for now we're interested in boxes like surfaceAreaCalculator - accept something, calculate something, return the result.</p>
39
<p>Some boxes don't accept anything, some - don't spit out anything, and some don't even do anything, but for now we're interested in boxes like surfaceAreaCalculator - accept something, calculate something, return the result.</p>
40
<p>We built this function in order to simplify our work. We have to calculate surface areas of different planets, and having this handy function means we don't have to remember and write down the formula over and over again.</p>
40
<p>We built this function in order to simplify our work. We have to calculate surface areas of different planets, and having this handy function means we don't have to remember and write down the formula over and over again.</p>
41
<p>Another reason is that now code is easier to understand. Compare this:</p>
41
<p>Another reason is that now code is easier to understand. Compare this:</p>
42
<p>to this:</p>
42
<p>to this:</p>
43
<p>First one is much nicer and simpler, especially to someone who is new to this code. First one answers the "what" question, the second one answers the "how" question.</p>
43
<p>First one is much nicer and simpler, especially to someone who is new to this code. First one answers the "what" question, the second one answers the "how" question.</p>
44
<p>We can improve on this and make another function to calculate squares. Let's first take a look at how we might use it:</p>
44
<p>We can improve on this and make another function to calculate squares. Let's first take a look at how we might use it:</p>
45
<p>Instead of multiplying radius by radius, we call a square function and pass the radius. Obviously, the square function is nothing but "accept a number, return its square":</p>
45
<p>Instead of multiplying radius by radius, we call a square function and pass the radius. Obviously, the square function is nothing but "accept a number, return its square":</p>
46
<p>Let's trace the steps and see what happens when we run our program. We create a constant surfaceOfMars and tell it to store whatever value surfaceAreaCalculator function returns when it's called with 3390 as an argument.</p>
46
<p>Let's trace the steps and see what happens when we run our program. We create a constant surfaceOfMars and tell it to store whatever value surfaceAreaCalculator function returns when it's called with 3390 as an argument.</p>
47
<p>3390 is known as radius inside the function. The function wants to multiply numbers and return, but it needs to know the last number, it has to call the square function and pass it the radius. square accepts one argument - it's the number 3390, in this case, and inside the square function it is known as n.</p>
47
<p>3390 is known as radius inside the function. The function wants to multiply numbers and return, but it needs to know the last number, it has to call the square function and pass it the radius. square accepts one argument - it's the number 3390, in this case, and inside the square function it is known as n.</p>
48
<p>square wants to multiply n by n and return. Nothing stops it, so it does. We are back inside the surfaceAreaCalculator - it was literally waiting for the square function to finish. And now we have the result of calling square. It substitutes the call, so now it's possible to finish the multiplication and return.</p>
48
<p>square wants to multiply n by n and return. Nothing stops it, so it does. We are back inside the surfaceAreaCalculator - it was literally waiting for the square function to finish. And now we have the result of calling square. It substitutes the call, so now it's possible to finish the multiplication and return.</p>
49
<p>The answer is returned and stored in the surfaceOfMars.</p>
49
<p>The answer is returned and stored in the surfaceOfMars.</p>
50
<p>So, functions can call other functions. And a function doesn't know and doesn't care if it was called from inside another function. Maybe it was called from inside a function from inside another function from inside yet another function! It doesn't really matter as long as the computation comes back and finishes.</p>
50
<p>So, functions can call other functions. And a function doesn't know and doesn't care if it was called from inside another function. Maybe it was called from inside a function from inside another function from inside yet another function! It doesn't really matter as long as the computation comes back and finishes.</p>
51
<p>Let's try something else with functions calling functions. Say, you have three books on your shelf, and you want to know how many different ways to arrange them exists.</p>
51
<p>Let's try something else with functions calling functions. Say, you have three books on your shelf, and you want to know how many different ways to arrange them exists.</p>
52
<p>It turns out there are six ways to arrange 3 books. Four books - 24 ways. 13 books - almost as many ways as people on the planet. 25 books? More ways to arrange them than atoms in the universe.</p>
52
<p>It turns out there are six ways to arrange 3 books. Four books - 24 ways. 13 books - almost as many ways as people on the planet. 25 books? More ways to arrange them than atoms in the universe.</p>
53
<p>In general, there are n! ways to arrange n books. Factorial means multiply all the numbers from 1 to n. So, 3! is 1 * 2 * 3. Let's write a factorial function:</p>
53
<p>In general, there are n! ways to arrange n books. Factorial means multiply all the numbers from 1 to n. So, 3! is 1 * 2 * 3. Let's write a factorial function:</p>
54
<p>Oh wait. We don't know what n is, that's the point. Hmm... How do they do it in math?</p>
54
<p>Oh wait. We don't know what n is, that's the point. Hmm... How do they do it in math?</p>
55
<p>Oh, okay, so, they have two options: if n is 1, then factorial is 1, this is simple. But if n is not 1, then factorial is n * (n-1)!</p>
55
<p>Oh, okay, so, they have two options: if n is 1, then factorial is 1, this is simple. But if n is not 1, then factorial is n * (n-1)!</p>
56
<p>Let's try this:</p>
56
<p>Let's try this:</p>
57
<p>This might seem weird. We are calling a function from this function, but... it's the same function!</p>
57
<p>This might seem weird. We are calling a function from this function, but... it's the same function!</p>
58
<p>Is there something wrong? No, not really! The thing is, a function itself is not a box, it's a description of the box. When you call a function a box is created, and after it's done working it's destroyed. So, if you call the same function from itself, there's just another box created.</p>
58
<p>Is there something wrong? No, not really! The thing is, a function itself is not a box, it's a description of the box. When you call a function a box is created, and after it's done working it's destroyed. So, if you call the same function from itself, there's just another box created.</p>
59
<p>Let's trace it: we call factorial(3). 3 is not 1, so first condition is ignored. The function wants to multiply numbers and return the answer, but it can't - it needs to know the second number, so it calls factorial(3-1) or factorial(2).</p>
59
<p>Let's trace it: we call factorial(3). 3 is not 1, so first condition is ignored. The function wants to multiply numbers and return the answer, but it can't - it needs to know the second number, so it calls factorial(3-1) or factorial(2).</p>
60
<p>A new identical factorial box is created, it accepts number 2, it's not 1, so it tries to multiply and return, but it can't - it needs to know the second number, so it calls factorial(1).</p>
60
<p>A new identical factorial box is created, it accepts number 2, it's not 1, so it tries to multiply and return, but it can't - it needs to know the second number, so it calls factorial(1).</p>
61
<p>A new identical factorial box is created, it accepts number 1, and this box can return immediately - it returns 1.</p>
61
<p>A new identical factorial box is created, it accepts number 1, and this box can return immediately - it returns 1.</p>
62
<p>1 comes back to the previous box, gets multiplied by 2 and the answer - 2 returns to the previous box, gets multiplied by 3 and the answer - 6 returns to the outside world and stored in the answer constant.</p>
62
<p>1 comes back to the previous box, gets multiplied by 2 and the answer - 2 returns to the previous box, gets multiplied by 3 and the answer - 6 returns to the outside world and stored in the answer constant.</p>
63
<p>Phew!</p>
63
<p>Phew!</p>
64
<p>This is called recursion: when something is described in terms of itself. When it comes to math or programming, recursion requires two things:</p>
64
<p>This is called recursion: when something is described in terms of itself. When it comes to math or programming, recursion requires two things:</p>
65
<ol><li>A simple base case or a terminating scenario. When to stop, basically. In our example it was 1: we stop factorial calculation when we get to 1.</li>
65
<ol><li>A simple base case or a terminating scenario. When to stop, basically. In our example it was 1: we stop factorial calculation when we get to 1.</li>
66
<li>A rule to move along the recursion, to go deeper. In our case, that was n * factorial(n-1).</li>
66
<li>A rule to move along the recursion, to go deeper. In our case, that was n * factorial(n-1).</li>
67
</ol><p>Let's trace the steps once more, but from a different point of view. This is what happens step by step:</p>
67
</ol><p>Let's trace the steps once more, but from a different point of view. This is what happens step by step:</p>
68
<p>factorial(3); 3 * factorial(2); 3 * 2 * factorial(1); 3 * 2 * 1; 3 * 2; 6;</p>
68
<p>factorial(3); 3 * factorial(2); 3 * 2 * factorial(1); 3 * 2 * 1; 3 * 2; 6;</p>
69
<p>Nothing gets multiplied until we go all the way down, to the base case of factorial(1). And then we start going back up, one step at a time, one multiplication at a time.</p>
69
<p>Nothing gets multiplied until we go all the way down, to the base case of factorial(1). And then we start going back up, one step at a time, one multiplication at a time.</p>
70
<p>Recursion is used widely, especially in functional programming - one of the styles of programming. And not only for math calculations, for all sorts of things! You'll see recursion all the time in this course and next ones, because it's extremely powerful and, I have to say, it's really cool.</p>
70
<p>Recursion is used widely, especially in functional programming - one of the styles of programming. And not only for math calculations, for all sorts of things! You'll see recursion all the time in this course and next ones, because it's extremely powerful and, I have to say, it's really cool.</p>
71
<p>It's your turn. Continue to the quiz and the exercise, and create your own recursive function. It might be a bit tricky, just remember: you need to describe two things - when to stop and how to go deeper. Good luck!</p>
71
<p>It's your turn. Continue to the quiz and the exercise, and create your own recursive function. It might be a bit tricky, just remember: you need to describe two things - when to stop and how to go deeper. Good luck!</p>