Recursion and recursive functions / Intro to JavaScript ES6 programming, lesson 7


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. 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, return the result. 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. Another reason is that now code is easier
to understand. Compare this… to this…
First one is much nicer and simpler, especially to someone who is new to this code. First
one answers the “what” question, second one answers the “how” question. We can improve on this and make another function
to calculate squares. Let’s first take a look at how we might use it: 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”. 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. 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`. `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. The answer is returned and stored in the `surfaceOfMars`. 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. 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. 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. 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: Oh wait. We don’t know what `n` is, that’s
the point. Hmm… How do they do it in math? 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)! Let’s try this: This might seem weird. We are calling a function
from this function, but… it’s the same function! 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. 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 result, but it can’t — it needs to know the second number, so it calls `factorial(3-1)`
or `factorial(2)`. 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)`. A new identical `factorial` box is created,
it accepts number 1, and this box can return immediately — it returns 1. 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 it’s stored in the `answer` constant. Phew! This is called recursion: when something is
described in terms of itself. When it comes to math or programming, recursion requires
two things: 1. 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. 2. A rule to move along the recursion, to
go deeper. In our case, that was `n * factorial(n-1)`. Let’s trace the steps once more, but from
a different point of view. This is what happens step by step: 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. 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. 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!

16 Comments

Add a Comment

Your email address will not be published. Required fields are marked *