More ("MOAR!") Kinds of Loops

In this tutorial, we’ll discuss…

While Loops

Self-Similarity

Recursion

…and we’ll be doing so in both
Python AND JavaScript.

So, let’s get started:

For Loop: Reconsidered

So far we’ve learned about the for loop.

Its basic structure fulfills many of our programming tasks:

…For example, step-by-step, repetitive tasks
that may require things like:

counting

iterating

generating

Imagine:
You have a repetitive task…

But you don’t know in advance how many times to repeat it.

Can we use a for loop to accomplish this?

Recall the basic structure of a for loop, in JavaScript:

for (i = 1; i <= 10; i = i + 1) {
    first statement;
    second statement;
}

What are its 3 components?

The 3 Components of a For Loop:

1. initialization

2. termination condition

3. increment

And how do we code each of these (i.e. in JavaScript)?

1. initialization:
i = 1;

2. termination condition:
i <= 10;

3. increment:
i = i + 1

In this case, the termination condition is definite:

i <= 10;

It tells us: after a known number of iterations,

the loop will stop.

But what if the number of iterations
is not fixed in advance of the loop?

For example,

what if the number of iterations

depends on what the user does each time?

Well, in that case…

We need another kind of loop structure.

The while loop is also iterative.

So, like the for loop,
we can use both to count and repeat stuff.

But, unlike for loops…

the while loop only repeats itself
while a certain condition is true.

Here’s a flowchart describing how, logically,
a while loop functions:

view source

Think of it this way:

A while loop acts like the combination
of a for loop and a conditional statement.

As long as some condition continues to be true,
the loop keeps repeating…

But as soon as that condition is no longer true,

that is, when the condition becomes false,

the loop immediately stops repeating;

and our program “exits the loop.”

Wait, what?!

Yeah, yeah, I know, you’re only five, got it…

How about a fancy, shmancy example then?

For example, consider this simple,
amazingly stupid while loop in Python:

i = 1
limit = 10

while i <= limit:
    print(i)
    i = i + 1

# After the loop terminates, print this:  
print("i is now greater than ", limit)

As you can imagine,
this while loop produces the following output:

$ python3 /path/to/my/while-loop-script.py
1
2
3
4
5
6
7
8
9
10
i is now greater than 10
$

i = 1
limit = 10

while i <= limit:
    print(i)
    i = i + 1

# After the loop terminates, print this:  
print("i is now greater than ", limit)

Can you identify the 3 components of this loop?

While Loop: Initialization

# Intitialization:
i = 1
limit = 10

At the top, we declare + initialize 2 variables:

the i variable indexes our loop, as normal,

but we also make a limit variable…

Once this counter value has been reached (i.e. 10),
the loop will stop.

While Loop: Increment

Inside the while loop itself:

while i <= limit:
    print(i)
    i = i + 1

We find our usual incremental expression:

i = i + 1

Notice that it’s inside the loop (i.e. indented in Python),

meaning it increments each time the loop runs.

Anything missing?

We found the initial and incremental parts…

But where is our termination condition??

While Loop: Termination

Check out the while loop once again:

while i <= limit:
    print(i)
    i = i + 1

Its first line

while i <= limit:

includes its own termination condition…

This says to us: Once i is greater than limit, stop.

In other words,

like if and then clauses,

the while clause includes a condition.

As long as that condition continues to be true,

the loop will continue repeating itself.

What would this simple while loop look like

in JavaScript?

Simple While Loop: JavaScript Version

var i = 1;
var limit = 10;

while (i <= limit) {
  console.log(i);
  i = i + 1;
}

// After the loop terminates, print this:  
console.log("i is now greater than " + limit);

And what are the differences between this syntax
and the earlier Python version?

Key Differences Compared to Python

Declare all variables with var

Lines end with a semicolon ;

While clause is in parens (i <= limit)

Entire while loop is enclosed in braces {}

Now, maybe you noticed…

that this simple while loop
had a fixed number of iterations (10).

What about that situation I mentioned earlier?

Imagine:
You have a repetitive task…

But you don’t know in advance how many times to repeat it.

Well, we can use a while loop for this too…

Consider this while loop (in Python):

userstring = input("Is MTEC1003 the best class? (y/n) ")

while userstring != "y":
    userstring = input("Sorry, I don't understand... Is MTEC1003 the best class? (y/n) ")

print("That's exactly what I was thinking...")
print("I agree! MTEC1003 really IS the best class!")

(Scroll to the RIGHT to see the complete line…)

What is going on here?!

First of all…

What does the != operator do?

…Remember?

It means “not equal.”

So the first line of this while loop:

while userstring != "y":

which designates a condition,

tells us that the loop will keep repeating
for as long as userstring is not “y”.

Now, look at the whole thing once again:

userstring = input("Is MTEC1003 the best class? (y/n) ")

while userstring != "y":
    userstring = input("Sorry, I don't understand... Is MTEC1003 the best class? (y/n) ")

print("That's exactly what I was thinking...")
print("I agree! MTEC1003 really IS the best class!")

(Scroll to the RIGHT to see the complete line…)

On line 1, we prompt the user for input.

Inside the while loop we keep prompting the user
if their answer isn’t “correct,”

And once it’s “correct,” the loop terminates,
and we print some final messages.

So, as you can imagine, this while loop
can produce the following output:

$ python3 /path/to/my/while-loop-script.py
Is MTEC1003 the best class? (y/n) n
Sorry, I don't understand... Is MTEC1003 the best class? (y/n) n
Sorry, I don't understand... Is MTEC1003 the best class? (y/n) but i like my other classes...
Sorry, I don't understand... Is MTEC1003 the best class? (y/n) OK I RLY HATE THIS CLASS
Sorry, I don't understand... Is MTEC1003 the best class? (y/n) fine, ok you win
Sorry, I don't understand... Is MTEC1003 the best class? (y/n) y
That's exactly what I was thinking...
I agree! MTEC1003 really IS the best class!
$

(Scroll to the RIGHT to see the complete line, including user input…)

Why “can produce” and not “definitely will produce?”

Because the precise output of this while loop
entirely depends on what the user does.

The loop will keep cycling whenever
the user answers something other than “y”.

In other words,

the exact number of iterations

is not fixed in advance.

So, what would this intermediate while loop look like

in JavaScript?

Intermediate While Loop:
JavaScript Version

var userstring = prompt("Is MTEC1003 the best class? (y/n) ");

while (userstring != "y") {
  userstring = prompt("Sorry, I don't understand... Is MTEC1003 the best class? (y/n) ");
}

console.log("That's exactly what I was thinking...");
console.log("I agree! MTEC1003 really IS the best class!");

(Scroll to the RIGHT to see the complete line…)

Again, what are the differences between this syntax
and the earlier Python version?

Key Differences Compared to Python

Declare all variables with var

Lines end with a semicolon ;

While clause is in parens (userstring != "y")

Entire while loop is enclosed in braces {}

Iteration

To iterate is to execute a sequence of instructions
that is continually repeated. [view source]

We might use an iterative approach
to a problem requiring us to iterate:

a precise number of times, or

until some condition is no longer true, or

through the elements in a list,
until the entire list has been traversed.

For example, this entire structure consists
of continual variations of the same shape:

It’s called a Sierpiński Triangle…

And is constructed by taking a single triangle…

and continually subdividing it into a
potentially infinite number of smaller triangles.

Imagine a loop… Each time that loop repeats itself,

big triangles are subdivided into smaller triangles.

Each cycle through the loop generates results that are
not identical, but curiously similar:

Each time produces multiples of smaller triangles.

This is a property known as

Self-Similarity

meaning…

the WHOLE has approximately the same shape
as its internal, component PARTS.

In the case of the Sierpiński Triangle,

all smaller triangles, and their spatial arrangements,

bear resemblance to all the larger levels of triangles,

and vise versa!

So, why is self-similarity important?

It turns out that nature is full of things
that display this characteristic property…

Like trees…

view source

Or coastlines…

Location: Egypt. Source: Google Earth

Or models of population growth…

view source

So, it’s worth understanding

how self-similar structures work,

and how to “simulate” them in our programs.

Now, back to programming stuff…

Notice we aren’t calling them “Recursive Loops”…

Although recursive functions definitely
repeat sequences in a very “loop-like” way…

Instead, we define “Recursive Functions”

as functions with a very “loop-like” behavior…

Now, one way to incorrectly do this
would be to embed a for loop within a function:

def foo():
  for x in range(0, 5):
    print(x)

This is close to what we mean by
a function with “loop-like” behavior,

but this still isn’t recursion…

Why would it crash?

Basically, if a loop keeps cycling forever,

eventually we’ll run out of memory.

So, we need something to stop this loop…

Why would it crash?

Because this recursive function is missing
something very important…

something fundamental to all
recursive functions, which we call a…

Base Case

Base Case

Without a base case, a recursive function
would go on recursing forever…

A base case is used to STOP a recursive function.

Do you remember how we STOP a for loop?

We use a base case to STOP a recursive function

similarly to how a termination condition
is used to STOP a for loop.

In Python, here’s a recursive function with a base case:

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)

This one calculates the factorial of a number.

For example, 3 factorial would be defined as 3!

where n=3 evaluates to 3 x 2 x 1 = 6.

So, how does this crazy thing work?
First, notice that the function calls itself.

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)

On line 1, we define the function factorial(n),

But inside our definition; inside our else statement,

on line 5, the factorial function is called;

with an argument of n-1, or:

1 less than the argument n given in the previous function call.

This means the function factorial will keep calling itself!

Each time, reducing n by a value of 1…

For example, if we were to run factorial(3)

Our function would call itself in this order:

factorial(3)

factorial(2)

factorial(1)

And we obtain our solution: 3 x 2 x 1 = 6

But, how does this function know when to STOP?

How does it know when to stop reducing by 1?

The answer is:

The Base Case

But where is this BASE CASE thing already??

Inside our function definition,
the if clause gives us our base case:

def factorial(n):
    if n == 1:
        return 1

This says: if n is 1, return the value 1, and STOP repeating.

We know it will STOP because inside the else clause,

there is no function call to keep our function looping.

How can we see what’s going on inside the function?

And why is Confused John Travolta
asking all the questions??

To see what happens
each time the function is called internally,

we can add print() statements at each step.

Here, I’ll add 2 print() statements,
one inside the if clause, and another
inside the else clause:

def factorial(n):
    if n == 1:
        print("n is 1, so return 1 and STOP!")
        return 1
    else:
        print("n is " + str(n) + ", so reduce n and CALL n-1=" + str(n-1))
        return n * factorial(n-1)

Now, we can monitor what happens at each step…

Now, when we execute this function,
by calling it once inside our Python code:

factorial(3)

the output (in the Terminal) will be:

$ python /path/to/my/python/script.py
n is 3, so reduce n and CALL n-1=2
n is 2, so reduce n and CALL n-1=1
n is 1, so return 1 and STOP!
6
$ 

And we obtain our result: 3 x 2 x 1 = 6.

Each time, n is multiplied by n-1… UNTIL n=1.

Each repeated step is similar to the previous one:

factorial(3) : n=3 : 3
factorial(2) : n-1=2 : 3 x (3-1) = 6
factorial(1) : n-1=1 : 6 x (2-1) = 6
final result returned by our function: 6

Each operation is the same, but the input changes…

so, the result we evaluate each time
is not identical… but related.

What would this simple recursive function look like

in JavaScript?

Inside of an HTML file, and between <script> tags,
we could write a JS version of our factorial() function,
which would look like this:

function factorial(n) {
  if (n == 1) {
    return 1;
  } else {
    return n * factorial(n-1);
  }
}

On your own:
How could you add print statements to this?