Objective: By the end of this checkpoint, you will have better understanding of Closures and Recursion.
The ability to treat functions as values, combined with the fact that local bindings are re-created every time a function is called, brings up an interesting question. What happen to local bindings when the function call that created them are no longer active?
The following code shows an example of this scenario. It defines a function, wrapValue, that creates a local binding. It then returns a function that accesses and returns this local binding.
This is allowed and works as you’d hope — both instances of the binding can still be accessed. This situation is a good demonstration of the fact that local bindings are created anew for every call, and different calls can’t trample on one another’s local bindings.
This feature of being able to reference a specific instance of a local binding in an enclosing scope is called closure. A function that references bindings from local scopes around it is called a closure. This behavior not only frees you from having to worry about lifetimes of bindings but also makes it possible to use function values in some creative ways.
With a slight change, we can turn the previous example into a way to create functions that multiply by an arbitrary amount.
The explicit local binding from the wrapValue example isn’t really needed since a parameter is itself a local binding.
Thinking about programs like this takes some practice. A good mental model is to think of function values as containing both the code in their body and the environment in which they are created. When called, the function body sees the environment in which it was created, not the environment in which it is called.
In the previous example, the multiplier function is called and creates an environment in which its factor parameter is bound to 2. The function value it returns, which is stored in the twice variable, remembers this environment. So when that is called, it multiplies its argument by 2.
It is perfectly okay for a function to call itself, as long as it doesn’t do it so often that it overflows the stack. A function that calls itself is called a recursive function, or Recursion. Recursion allows some functions to be written in a different style. Take, for example, this alternative implementation of power:
This is rather close to the way Mathematicians define exponentiation and arguably describes the concept more clearly than the looping variant. The function calls itself multiple times with ever smaller exponents to achieve the repeated multiplication.
The dilemma of speed versus elegance is an interesting one. You can see it as a kind of continuum between human-friendliness and machine-friendliness. Almost any program can be made faster by making it bigger and more convoluted.
The programmer has to decide on an appropriate balance.
In the case of the power function, the inelegant (looping) version is still fairly simple and easy to read. It doesn’t make much sense to replace it with the recursive version. Often, though, a program deals with such complex concepts that giving up some efficiency in order to make the program more straightforward is helpful.
Worrying about efficiency can be a distraction. It’s yet another factor that complicates program design, and when you’re doing something that’s already difficult, that extra thing to worry about can be paralyzing. Therefore, always start by writing something that’s correct and easy to understand.
If you’re worried that it’s too slow — which it usually isn’t since most code simply isn’t executed often enough to take any significant amount of time — you can measure afterward and improve it if necessary.
Recursion is not always just an inefficient alternative to looping. Some problems really are easier to solve with recursion than with loops. Most often these are problems that require exploring or processing several “branches”, each of which might branch out again into even more branches.
Consider this puzzle: by starting from the number 1 and repeatedly either adding 5 or multiplying by 3, an infinite set of numbers can be produced. How would you write a function that, given a number, tries to find a sequence of such additions and multiplications that produces that number?
For instance, the number 13 could be reached by first multiplying by 3 and then adding 5 twice, whereas the number 15 cannot be reached at all.
Here is a recursive solution:
Note that this program doesn’t necessarily find the shortest sequence of operations.
It is satisfied when it finds any sequence at all. It is okay if you don’t see how it works right away. Let’s work through it:
The inner find function does the actual recursing. It takes two arguments: the current number and a string that records how we reached this number. If it finds a solution, it returns a string that shows how to get to the target. If no solution can be found starting from this number, it returns
To do this, the function performs one of three actions. If the current number is the target number, the current history is a way to reach that target, so it is returned. If the current number is greater than the target, there’s no sense in further exploring this branch because both adding and multiplying will only make the number bigger, so it returns
null. Finally, if we’re still below the target number, the function tries both possible paths that start from the current number by calling itself twice: once for addition and once for multiplication. If the first call returns something that is not
null, it is returned. Otherwise, the second call is returned, regardless of whether it produces a
To better understand how this function produces the effect we’re looking for, let’s look at all the calls to find out how they are made when searching for a solution for the number 13.
The indentation indicates the depth of the call stack. The first time
find is called, it starts by calling itself to explore the solution that starts with (1 + 5).
That call will further recurse to explore every continued solution that yields a number less than or equal to the target number. Since it doesn’t find one that hits the target, it returns
null back to the first call. There, the
|| operator causes the call that explores (1 * 3) to happen. This search has more luck — its first recursive call, through yet another recursive call, hits upon the target number. That innermost call returns a
string, and each of the
|| operators in the intermediate calls pass that
string along, ultimately returning the solution.
There are two more natural ways for functions to be introduced into programs. The first is that you find yourself writing similar code multiple times. You’d prefer not to do that. Having more code means more places for mistakes to hide and more material to read for people trying to understand the program.
So you take the repeated functionality, find a good name for it, and put it into a function.
The second way is that you discover you need some functionality that you haven’t written yet and that sounds like it deserves its own function. You’ll start by naming the function and then you’ll write its body. You might even start writing code that uses the function before you actually define the function itself.
How difficult it is to find a good name for a function is a good indication of how clear a concept it is that you’re trying to wrap.
Let’s go through an example.
We want to write a program that prints two numbers: the numbers of cows and chickens on a farm, with the words Cows and Chickens after them and zeros padded before both numbers so that they are always three digits long. For instance,
007 Cows and
This asks for a function of two arguments — the number of cows and the number of chickens. Let’s get coding.
.length after a string expression will give us the length of that string. Thus, the
while loops keep adding zeros in front of the number strings until they are at least three characters long.
Mission accomplished! But just as we are about to send the farmer the code (along with a hefty invoice), she calls and tells us she’s also started keeping pigs. Could we please extend the software to also print pigs? We sure can. But just as we’re in the process of copying and pasting those four lines of code one more time, we stop and reconsider. There has to be a better way.
Here’s a first attempt:
It works! But that name, printZeroPaddedWithLabel, is a little awkward.
It conflates three things — printing, zero-padding, and adding a label—into a single function. Instead of elevating the repeated part of our program, let’s try to pick out a single concept.
A function with a nice, obvious name like
zeroPad makes it easier for someone who reads the code to figure out what it does. And such a function is useful in more situations than just this specific program. For example, you could use it to help print nicely aligned tables of numbers. How smart and versatile should our function be? We could write anything, from a terribly simple function that can only pad a number to be three characters wide to a complicated generalized number-formatting system that handles fractional numbers, negative numbers, alignment of decimal dots, padding with different characters, and so on.
A useful principle is to not add cleverness unless you are absolutely sure you’re going to need it. It can be tempting to write general “frameworks” for every bit of functionality you come across. Resist that urge. You won’t get any real work done — you’ll just be writing code that you’ll never use.
Functions can be roughly divided into those that are called for their side effects and those that are called for their return value. (Though it is definitely also possible to have both side effects and return a value.) The first helper function in the farm example,
printZeroPaddedWithLabel, is called for its side effect: it prints a line. The second version,
zeroPad, is called for its return value. It is no coincidence that the second is useful in more situations than the first. Functions that create values are easier to combine in new ways than functions that directly perform side effects.
A pure function is a specific kind of value-producing function that not only has no side effects but also doesn’t rely on side effects from other code. For example, it doesn’t read global bindings whose values might change. A pure function has the advantage of, when called with the same arguments, always producing the same value (and doesn’t do anything else). A call to such a function can be substituted by its return value without changing the meaning of the code. When you are not sure that a pure function is working correctly, you can test it by simply calling it and know that if it works in that context, it will work in any context. Nonpure functions tend to require more scaffolding to test. Still, there’s no need to feel bad when writing functions that are not pure or to wage a holy war to purge them from your code. Side effects are often useful.
This lesson taught you how to write your own functions. The function keyword, when used as an expression, can create a function value. When used as a statement, it can be used to declare a binding and give it a function as its value. Arrow functions are yet another way to create functions.
A key aspect of understanding functions is understanding scopes. Each block creates a new scope. Parameters and bindings declared in a given scope are local and not visible from the outside. Bindings declared with
var behave differently — they end up in the nearest function scope or the global scope.
Separating the tasks your program performs into different functions is helpful. You won’t have to repeat yourself as much and functions can help organize a program by grouping code into pieces that do specific things.