Skip to content

Repetition

Learning Objectives

At the end of this sub-unit, students should

  • know how to connect recursion with iteration.

Repeating Operations

We can think of recursion as a way to repeat an operation. The operation we want to repeat is computing the same problem but using simpler input. Another way to repeat an operation is via iteration. Can we connect recursion and iteration?

The answer is yes. A proof of that is our computer. A computer can be thought of as a single giant simple loop.

  1. Fetch the next operation.
  2. Execute the operation.
  3. Repeat Step 1.

Since we can execute a recursive function on our computer, it means we can convert any recursion into an iteration. However, the conversion may not be easy. Fortunately, there is a restricted kinds of recursion that has a more direct connection to iteration. This is called linear recursion.

This kinds of recursion is a recursion that we have done before where the function \(F(x)\) is calling itself at most once. Before we continue, we will show the prototypical non-linear recursive formula called the Fibonacci sequence. This sequence is defined only for non-negative \(n\).

\[ F(n) = \begin{cases} n &, \text{if } n \leq 1 \\ F(n - 1) + F(n - 2) &, \text{otherwise} \end{cases} \]

Notice how \(F(n)\) is calling \(F\) twice. The first is \(F(n - 1)\) and the second is \(F(n - 2)\). Although there is a way to convert a Fibonacci-like recursion into an iteration, such conversion is not general. What we are going to show is a general way of converting a linear recursion into iteration. We will try to discover these conversion via observations.

Comparing Factorial

Iterative Factorial

Our iterative factorial function is given below.

1
2
3
4
5
6
def factorial(n):
  res, i = 1, 1
  while i <= n:
    res = res * i
    i = i + 1
  return res

We can try evaluating factorial(6) and produce the trace table below.

Iteration n res3 i3 res5 = res3 * i3 i5 = i3 + 1
pre 6 1 1    
1 6 1 1 1 2
2 6 1 2 2 3
3 6 2 3 6 4
4 6 6 4 24 5
5 6 24 5 120 6
6 6 120 6 720 7
post 6 720 7    

If we look at the value of res5 over the entire iteration, we can see that it computing the following expression.

(((((1 * 1) * 2) * 3) * 4) * 5) * 6 = 720

Yet another factorial function is the following. We will use this alternative as it will provide a simpler comparison to the recursion. Recap that due to the abstraction into a function, we do not care about the implementation as long as it solves the same problem.

1
2
3
4
5
6
def factorial(n):
  res = 1
  while n > 0:
    res = res * n
    n = n - 1
  return res

Since we do not have the local variable i, the trace table is simpler.

Iteration n3 res3 n5 = n3 - 1 res5 = res3 * n3
pre 6 1    
1 6 1 5 6
2 5 6 4 30
3 4 30 3 120
4 3 120 2 360
5 2 360 1 720
6 1 720 0 720
post 0  720     

The unrolling is shown below.

(((((1 * 6) * 5) * 4) * 3) * 2) * 1 = 720

Recursive Factorial

Now we look at the recursive factorial function below.

1
2
3
4
5
def factorial(n):
  if n == 0:
    return 1
  else:
    return n * factorial(n - 1)

While this is not exactly a trace table, we can actually construct some kind of table that captures the computation. To highlight the time component of the component, we separate them into two parts. The first part is the sequence of recursive call to the base case. The second part is the sequence of return value and deferred operation.

Call n Deferred Return
factorial(6) 6 6 \(\times\) ░░░ ░░░
factorial(5) 5 5 \(\times\) ░░░ ░░░
factorial(4) 4 4 \(\times\) ░░░ ░░░
factorial(3) 3 3 \(\times\) ░░░ ░░░
factorial(2) 2 2 \(\times\) ░░░ ░░░
factorial(1) 1 1 \(\times\) ░░░ ░░░
factorial(0) 0   1
Call n Deferred Return
factorial(6) 6 6 \(\times\) 120  720 
factorial(5) 5 5 \(\times\) 24 120
factorial(4) 4 4 \(\times\) 6 24
factorial(3) 3 3 \(\times\) 2 6
factorial(2) 2 2 \(\times\) 1 2
factorial(1) 1 1 \(\times\) 1 1
factorial(0) 0   1

By the same idea of unrolling but applied to recursion, we get the following expression.

6 * (5 * (4 * (3 * (2 * (1 * 1))))) = 720

Now that we have both table and expression, we can compare them.

Comparison

Let us look at the table side by side.

  • Iterative Factorial

    Iteration n3 res3
    1 6 1
    2 5 6
    3 4 30
    4 3 120
    5 2 360
    6 1 720
    post 0  720 

    (((((1 * 6) * 5) * 4) * 3) * 2) * 1 = 720

  • Recursive Factorial

    Call n Deferred Return
    f(6) 6 6 \(\times\) 120  720 
    f(5) 5 5 \(\times\) 24 120
    f(4) 4 4 \(\times\) 6 24
    f(3) 3 3 \(\times\) 2 6
    f(2) 2 2 \(\times\) 1 2
    f(1) 1 1 \(\times\) 1 1
    f(0) 0   1

    6 * (5 * (4 * (3 * (2 * (1 * 1))))) = 720

There are few similarities but the most obvious one is probably the expression produced. This is not surprising because they compute the same result. In fact, because * is associative (i.e., x * (y * z) == (x * y) * z) we can remove all the parentheses. We keep the main parentheses to highlight the similarities.

  • Iterative Factorial

    1 * (6 * 5 * 4 * 3 * 2 * 1) = 720

  • Recursive Factorial

    (6 * 5 * 4 * 3 * 2 * 1) * 1 = 720

Because * is also commutative (i.e., x * y == y * x), we can then reorder the expression make it exactly identical. By comparing the table and mapping how the cell in the table is computed on the code, we can compare the code to see how they can produce the same value in the end. We will use some of the terminologies used for recursion in our comparison. However, by "recursion", we will simply look at the value of the next argument.

  • Iterative Factorial

    1
2
3
4
5
6
    def factorial(n):
  res = 1
  while n > 0:
    res = res * n
    n = n - 1
  return res

  • Recursive Factorial

    1
2
3
4
5
6
    def factorial(n):
  if n == 0:
    return 1
  else:
    return n * 
           factorial(n - 1)

Caution

Note that we split the operation n * factorial(n - 1) into two lines (i.e., Line 5 and Line 6) for a more precise comparison. However, this causes syntax error. It should be treated as a single line.

  • Iterative Factorial

    1
2
3
4
5
6
    def factorial(n):
  res = 1
  while n > 0:     # not (base case)
    res = res * n
    n = n - 1
  return res

  • Recursive Factorial

    1
2
3
4
5
6
    def factorial(n):
  if n == 0:                # base case
    return 1
  else:
    return n * 
           factorial(n - 1)

Explanation

The base case stops the recursion. In iteration, it stops the loop. But the loop condition must continue the loop, so we take the negation.

  • Iterative Factorial

    1
2
3
4
5
6
    def factorial(n):
  res = 1          # initial value
  while n > 0:
    res = res * n
    n = n - 1
  return res

  • Recursive Factorial

    1
2
3
4
5
6
    def factorial(n):
  if n == 0:
    return 1                # base value
  else:
    return n * 
           factorial(n - 1)

Explanation

This happens when the base case occurs. If we look at factorial(0), both must return 1. So that corresponds to the initial value of res before the loop.

  • Iterative Factorial

    1
2
3
4
5
6
    def factorial(n):
  res = 1
  while n > 0:
    res = res * n
    n = n - 1      # next value update
  return res

  • Recursive Factorial

    1
2
3
4
5
6
    def factorial(n):
  if n == 0:
    return 1
  else:
    return n * 
           factorial(n - 1) # next argument

Explanation

In recursion, we assign n = n - 1 during call by value before executing the function body. So it makes sense that it corresponds to the n = n - 1 at the bottom of the loop before we start the next iteration.

  • Iterative Factorial

    1
2
3
4
5
6
    def factorial(n):
  res = 1
  while n > 0:
    res = res * n  # accumulation
    n = n - 1
  return res

  • Recursive Factorial

    1
2
3
4
5
6
    def factorial(n):
  if n == 0:
    return 1
  else:
    return n *              # deferred
           factorial(n - 1)

Explanation

This operation is done on each iteration and recursion. The only issue is that the order for iteration (i.e., _ * n) is different from recursion (i.e., n * _). In our case, the behavior is identical but may not always be. So be careful.

Generalized Comparison

We can now use the idea of code generalization to further compare the two codes. Since we are only interested in linear recursion, we will look at our idealized linear recursion.

  • Iteration

    1
2
3
4
5
6
    def iter(x, y, z):
  res = base
  while not cond(x, y, z):
    res = op(res, x, y, z)
    x, y, z = nx(x), ny(y), nz(z)
  return res

  • Recursion

    1
2
3
4
5
6
    def rec(x, y, z):
  if cond(x, y, z):
    return base
  else:
    return op(rec(nx(x), ny(y), nz(z)),
              x, y, z)

The table of comparison is also shown below.

Recursive Code Recursive Element Iterative Element Iterative Code
cond(x, y, z) Base Case Loop Condition not cond(x, y, z)
return base Base Value Initial Value res = base
nx(x), ny(y), nz(z) Next Argument Next Value Update x, y, z = nx(x), ny(y), nz(z)
op(..., x, y, z) Deferred Operation Accumulation res = op(res, x, y, z)

So what is the use of knowing this? This will simplifies our task in case we need one form and not the other. In solving certain problems, we may be required to solve it iteratively and recursively. If we are stuck in one, but we can derive the other, then we can try to use this comparison to come up with the alternative code.

Let us apply this to some problem involving strings. We will not explain what the function is, so as to show how the comparison can be used as it is. Try to do it on your own first before looking at the other version.

Example #1

  • Iteration

    Iterative Version 
    1
2
3
4
5
6
    def foo(s):
  res = ''
  while not (s == ''): # simple condition
    res = res + s[-1]
    s = s[:-1]
  return res

  • Recursion

    Recursive Version

    1
2
3
4
5
    def foo(s):
  if s == '':
    return ''
  else:
    return s[-1] + foo(s[:-1])

It is easier to come up with the table of comparison first. One thing to note is that we need to think which of the following accumulation is the correct one.

  • res = res + s[-1]
  • res = s[-1] + res
Table of Comparison
Recursive Code Recursive Element Iterative Element Iterative Code
s == '' Base Case Loop Condition not (s == '') alternatively s != ''
return '' Base Value Initial Value res = ''
s[:-1] Next Argument Next Value Update s = s[:-1]
s[-1] + Deferred Operation Accumulation res = res + s[-1]

Example #2

  • Iteration

    Iterative Version

    1
2
3
4
5
6
    def bar(s):
  res = ''
  while s != '':
    res = res + s[0] + s[-1] 
    s = s[1:-1]
  return res

  • Recursion

    Recursive Version 
    1
2
3
4
5
    def bar(s):
  if not (s != ''):
    return ''
  else:
    return s[0] + s[-1] + bar1(s[1:-1])

Try to come up with the table of comparison on your own.