Recursion 101

In computer science, it refers to solving a problem by solving a smaller version of the same problem that is solved by solving a smaller version of the same problem that is solved by solving a smaller version of the same problem that is solved by solving a smaller version of the same problem …and so on… until we reach a problem that is small enough to be trivial to solve.

This is often done by having a function invoke itself until the problem is trivial to solve without invoking itself.

You can write all recursive functions iteratively (with loops). You will see this.

In general, if you can, write things with loops.

1. Factorial

One of the simplest recursive methods computes the factorial of a number, where given a number n, n factorial (usually written as n!) is computed as:

n! = n × (n-1) × (n-2) ×.. × 1

E.g:

5! = 5 × 4 × 3 × 2 × 1 = 120

NOTE: for those of you familiar with maths. 0! = 1 and this is normally the base case. We have ignored this and are stopping at 1.

If we use computing speak and write this as a function fact(n):

# note this is not working code, just more familiar notation
fact(n) = n * (n-1) * ... * 1

E.g:

fact(5) = 5 * (5-1) * ... * 1 = 5*4*3*2*1 = 120

Which we could choose to implement in python write using a for loop.

def fact(n):
  total = 1
  for i in range(1, n+1):
    total = total * i
  return total

print(fact(5)) # prints 120 = 5*4*3*2*1

If we look carefully at

fact(n) = n * (n-1) * ... * 1

we will notice something seemingly unremarkable, but it has deep consequences!

fact(5) = 5*4*3*2*1

Take a look at

4*3*2*1

this is also fact(4), therefore we can rewrite fact(5) as follows:

fact(5) = 5*fact(4)

We now have a function defined in terms of itself!

In general,

fact(n) = n*fact(n-1)
Where, 
fact(1) = 1

So, when we call fact(5) the following happens:

fact(5) = 5*fact(5-1)

which calls

fact(4) = 4*fact(4-1)

which calls

fact(3) = 3*fact(3-1)

which calls

fact(2) = 2*fact(1)

which calls

fact(1)=1

We reach the easily evaluated case of fact(1)

We can then unwind all of this.

fact(1)=1

means that

fact(2) = 2*fact(1) = 2*1 = 2

which means

fact(3) = 3*fact(2) = 3*2 = 6

which means

fact(4) = 4*fact(3) = 4*6 = 24

and finally

fact(5) = 5*24 = 120

fact(1) is known as the base case. This is normal a case we know how to evaluate easily. If you think about it, if we didn’t have a base case, we would have just kept on going!!!

Written as a python program is simple. We just need to put in our general recursion and base case.

fact(n) = n*fact(n-1)
Where, 
fact(1) = 1

Which becomes

def fact(n):
  if n < 2:
    return 1 # return base case
  return n*fact(n-1)

print(fact(5)) # prints 120

Note that we could put in a float or a number less than 0 and get erroroneous answers, but for ease of reading we assume whole numbers of 0 and above.

You can visualise what is happening on Python Tutor. Paste in the code and call fact(4) which will return 24.

2. Summing a List of Numbers

We can also consider summing a list of numbers, e.g. 5,4,2,6.

Let’s just define a function called sum_list() that takes a list of numbers and adds them up.

Then by definition of additon.

sum_list([3,4,9]) = 3 + sum_list([4,9])

sum_list([3,4,9]) = 3 + sum_list([4,9])
             = 3 + 4 + sum_list([9])
             = 3 + 4 + 9 + sum_list([])
             = 3 + 4 + 9 + 0 = 16

Here we can clearly see the base case is the sum of an empty list, which is just 0. i.e. sum_list([]) = 0.

In general,

sum_list(number_list) = item_one + sum_list(rest_of_list)
Where,
sum_list(empty_list) = 0

def sum_list(num_list):
  # test for base case
  if len(num_list) == 0:
    return 0
  # return head + sum of rest of list
  return num_list[0] + sum_list(num_list[1:])

print(sum_list([3,4,9])) # prints 16

To me that is pretty darn beautiful!

Note that you can also do this in one less recursive call by noting the following:

sum_list([3,4,9]) = 3 + sum_list([4,9])
             = 3 + 4 + sum_list([9])
             = 3 + 4 + 9

i.e. a list with 1 item can also be considered a base case. We don't have to go all the way to the empty list.

sum_list(number_list) = item_one + sum_list(rest_of_list)
Where,
sum_list(single_item_list) = single_item_list

def sum_list(num_list):
  # test for base case
  if len(num_list) == 1:
    return numlist[0]
  # return head + sum of rest of list
  return num_list[0] + sum_list(num_list[1:])

print(sum_list([3,4,9])) # prints 16

Of course you can just use a loop.

def sum_list(num_list):
  total = 0
  for num in num_list:
    total += num
  return total

print(sum_list([3,4,9])) # prints 16

3. Fibonacci Numbers

No introduction to recursion would be complete without a look at the Fibonacci numbers.

These are a sequence of numbers that you get by adding the previous two numbers of the sequence. You start with 1 and 1.

1,1                # add 1 and 1
1,1,2              # add 1 and 2
1,1,2,3            # add 2 and 3
1,1,2,3,5          # add 3 and 5
etc...
1,1,2,3,5,8,13,21,34

If you define the nth fibonacci number of the sequence as fib(n) then

# the next number is the sum of the previous 2 in the sequence!
fib(n) = fib(n-1) + fib(n-2)
where,
fib(0) = 1 and fib(1) = 1

Here we have the recursive formula and the two base cases fib(0) and fib(1).

We can easily put this into python.

def fib(n):
  if n < 2:
    return 1

  return fib(n-1) + fib(n-2)

# Two ways of printing the first 6 terms
for n in range(6):
  print(f"fib({n}) = {fib(n)}")
# prints 
# fib(0) = 1
# fib(1) = 1
# fib(2) = 2
# fib(3) = 3
# fib(4) = 5
# fib(5) = 8

print([fib(n) for n in range(6)]) # prints [1,1,2,3,5,8]

I recommend that you look at this in Python Tutor to see an animated version of what is happening.

4. Why Bother?

You can write all recursive methods iteratively (with loops), but:

it does require you to track the information
sometimes it is just a lot easier to solve a problem recursively.

You'll see a lovely example of this in the exercise for the lesson on Memoization.

In general, if you can, write things with loops.

===TASK ===

Create the functions string_list_concat() and string_list_concat_with_space() so that it takes a list of strings as input and concatenates (joins) them into one string as per the function docstring.

YOUR FUNCTION SHOULD USE RECURSION AND USE THE MINIMAL AMOUNT OF RECURSIVE CALLS.

HINT: Section 2 on summing numbers is an excellent place to start. You should consider how this task is similar to the recursive program given in Section 2.

Copy and paste the following into a new Python file to get started.

def string_list_concat(string_list):
  """ Concatenates a list of strings into a single string
  eg. ["This", "is", "a", "list", "of", "strings"] 
  returns
  "Thisisalistofstrings"
  """
  pass

def string_list_concat_with_space(string_list):
  """ Concatenates a list of strings into a single string
  eg. ["This", "is", "a", "list", "of", "strings"] 
  returns
  "This is a list of strings"
  """
  pass

if __name__ == "__main__":
  str_list = ["This", "is", "a", "list", "of", "strings"]
  print(string_list_concat(str_list)) # prints the return value of "Thisisalistofstrings"
  print(string_list_concat_with_space(str_list)) # prints the return value of "This is a list of strings"

Programming in Python

Recursion 101

1. Factorial

2. Summing a List of Numbers

3. Fibonacci Numbers

4. Why Bother?

===TASK ===