Note that the condition in the iter
function does not inclide an else
branch. So, if the (counter === 1)
condition
is not met, then the execution just continues to the next line and does return iter(counter-1, counter * acc)
.
const iter = (counter, acc) => {
if (counter === 1) {
return acc;
}
return iter(counter-1, counter * acc);
}
It works because when a return
instruction is executed, the function instance spits out the value and disappears.
Nothing else will be performed after return
is done.
So, when the condition is met, return acc
is executed, and the second return is never performed.
Here is another example:
const someFunction = (a) => {
return 100;
return a;
return 4123123;
}
This function will always return 100
. Two other return statements are never reached, because the function instance is
destroyed after it does the first return. There can only be one return performed in any given instance.
Recall the function from the previous lesson:
const factorial = (n) => {
if (n === 1) {
return 1;
}
else {
return n * factorial(n-1);
}
}
The process of computing that this function creates when it's running is called a recursive process. The main idea is to delay the computations until the very end.
factorial(3); // don't multiply anything here
3 * factorial(2); // don't multiply anything here
3 * 2 * factorial(1); // don't multiply anything here
3 * 2 * 1; // finally start multiplying
3 * 2;
6;
All the information about computations, anything the program remembers at any given moment (computations, constants, functions) is called state. Many problems in programming come from the need to handle state.
Iterative process is about computing with a fixed amount of state.
const factorial = (n) => {
const iter = (counter, acc) => {
if (counter === 1) {
return acc;
}
return iter(counter-1, counter * acc);
}
return iter(n, 1);
}
Idea:
We need to start with something, because step 2 requires a number from the previous step, so we start with 1, because
then n*1
will be just n
:
return iter(n, 1);
This is how iter calls look like when computing 3!:
iter(3, 1); // iter(3-1, 1*3);
iter(2, 3); // iter(2-1, 2*3);
iter(1, 6); // counter === 1, return 6
6;
The iterative process in general:
Recursion can be used in different ways, and the one we've seen in the previous lesson is called recursive process. If you haven't seen it, go watch it first. Today's lesson will make much more sense if you've seen the previous lesson and completed the exercise.
Another way of using recursion in code is called iterative process. The naming is somewhat confusing: recursive process and iterative process are both about recursion.
Remember the series of calls from the previous lesson. Each newly created instance — or a box — of the factorial
function is waiting for the next instance to return something. No calculation is done until we get all the way to the
bottom — to the base case. Only then we get 1 and start multiplying backward: 1 times 2 is 2, then 3 times 2 is 6.
This wasn't too bad for factorial of 3, but consider factorial of 100, for example. The program will need to keep in mind a lot of numbers and delay all the multiplications. Delay is the key word here: recursive process is about delaying all the computation until the very end. It cannot multiply anything until it gets to the bottom, and if you stop it in the middle — it knows nothing, you won't get any useful information unless you let it finish completely. Recursive process is like that guy who does whole week's work on Friday afternoon.
All that information about computations is called state. Anything your program remembers at any given moment is state: computations, constants, functions. And very often state is the cause of many problems in programming.
Doing everything on Friday afternoon is certainly not the best way to work. A better way is doing a little bit on Monday, a little bit on Tuesday, etc. This is iterative process: the guy who distributes his work throughout the week.
Let's implement the same factorial function using an iterative process. This is the idea: don't delay the multiplications, but rather multiply two numbers right away, then pass the result to the next step.
Here is the code.
const factorial = (n) => {
const iter = (counter, acc) => {
if (counter === 1) {
return acc;
}
return iter(counter-1, counter * acc);
}
return iter(n, 1);
}
As you see, this doesn't look like the math formula for the factorial exactly, unlike the recursive process function from the last lesson. This is usually the case: the code for a recursive process is easier to read and understand, the code is visually closer to the idea. But it's not too efficient. Iterative process is more efficient, but it's more complicated.
The factorial function has another function defined inside it. Remember, function definitions are not boxes, only
descriptions of boxes. This inside function iter
takes two arguments: counter and accumulator. Counter keeps track of
the movement from n down to 1. And accumulator is the running result of multiplying numbers from n down to 1. If counter
hits 1, the accumulator is returned — by then it will be the complete answer.
After this function is defined we have a single line in the factorial function: return the result of running iter
with
n and 1 as arguments.
Let's run factorial(3)
. The only line that actually runs in the factorial
function is return iter(n, 1)
. It wants
to return, but it needs to get the value from the iter
function.
A new iter
box is created. It accepts 3 and 1. 3 is known as counter
and 1 is known as acc
inside this iter box.
Counter is not 1, so first condition is ignored. Then it wants to return, but it needs to get the value from a new
iter
instance.
This is the most important part: a new box is called with a counter reduced by 1, because we made 1 step, and accumulator multiplied by the counter.
A new iter
box is created. It accepts 2 and 3 — counter and accumulator. Counter is not 1, so it tries to return, but
it can't — it needs to get the value from a new iter
instance, called with 2-1 as the first argument, and 2*3 as the
second argument. We haven't finished yet, but we made a useful multiplication — 2*3 is one of the multiplications needed
to find 3!
A new iter
box is created. It accepts 1 and 6. Now the condition is satisfied, so this box just returns the
accumulator — number 6.
Then this 6 just trickles down to the first iter box, then to the factorial box, and then it's returned as the answer.
This is how computations look like step by step:
iter(3, 1); // iter(3-1, 1*3);
iter(2, 3); // iter(2-1, 2*3);
iter(1, 6); // counter === 1, return 6
6;
At any moment, the program needs to remember the state, but the size of it is always the same — it's just two numbers.
This iterative process in general can be described like so:
And this thing loops until it hits the terminating case.
Let's recap:
Now, after the short quiz, comes probably the hardest exercise in this course so far. But I'm sure you'll crack it. And when you do, you'll feel great. I know I did.