The iterative process and how to not be lazy — Programming fundamentals

• Important notes
• Lesson notes
  • Recap
• Lesson transcript

Important notes

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.

Lesson notes

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:

1. count down from n to 1
2. take the number from the previous step
3. multiply that number by the current number
4. pass it along to the next step
5. when counter hits 1, the number passed from the previous step is the answer

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:

1. Define the initial state. In our example, we make the first iter call with n and 1. This is the initial state
2. Check the terminating case. We check for the counter to be 1, and stop the recursion when it hits 1
3. Define the new state. This is how the process moves along. In our example, we make another iter call with the counter reduced and accumulator multiplied. These two new numbers define the new state
4. Repeat step 2

Recap

1. Recursion is when a thing is defined in terms of itself
2. Recursive process is the process of computing with delayed computations
3. Iterative process is the process of computing when the state can be described by a fixed number of things

Lesson transcript

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:

1. Define the initial state. In our example, we make the first iter call with n and 1. This is the initial state
2. Check the terminating case. We check for the counter to be 1, and stop the recursion when it hits 1
3. Define the new state. This is how the process moves along. In our example, we make another iter call with the counter reduced and accumulator multiplied. These two new numbers define the new state
4. Repeat step 2

And this thing loops until it hits the terminating case.

Let's recap:

1. Recursion is when a thing is defined in terms of itself
2. Recursive process is the process of computing with delayed computations
3. Iterative process is the process of computing when the state can be described by a fixed number of things

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.