CS40 : For recursion, see recursion ...

 
A famous online encyclopedia once said, "For recursion, see recursion".

We are learning ...
  • About recursion
So that we can ...
  • Show familiarity with recursive techniques
    - General case
    - Base case
  • Be able to solve problems using recursive techniques

A well known search engine once said ...

https://www.google.co.uk/?gws_rd=ssl#safe=strict&q=recursion

At the top of the page, we see our old friend Ben exhibiting the Droste Effect, most often observed in real life when you've got two mirrors on opposite walls and you stand between them - when will it stop ...

Activity 1 Classic recursive thinking (55)

On my to do list, I wrote only one item ...


Task 1.1
Recursive acronyms

A recursive acronym is a word formed as an abbreviation to a longer phrase which uses either the first letters of each word (e.g. NATO or laser) or syllables from each word (e.g. Benelux). A recursive acronym is one in which the acronym itself is one of the words being abbreviated!


Visit the Wikipedia page on recursive acronyms and choose a few interesting ones to write down in your notebooks. Can you find any funny recursion jokes?

Interesting note : "HURD" is a co-recursive acronym, standing for "HIRD of Unix-Replacing Daemons", where "HIRD" stands for "HURD of Interfaces Representing Depth".

OUTCOME : List of interesting recursive acronyms together with any funny recursion jokes (unlikely).


There are plenty of examples of recursion in natures as well ... watch the following presentation.



Task 1.2
Fractals

Download the Fractal Grower executable java file and try to create some fractals with it. Can you see the recursive nature of these images and their parallels in nature?

Print one of your finest examples out for your notebooks.

OUTCOME : Printed fractal of a tree or something similar
 

Recursive solutions are much more suitable for situations where parts of the solutions are similar to the whole, e.g. for problems involving graphs, trees and lists. Oh, and light bulbs (how excited is Ben?)

https://drive.google.com/file/d/0B83yXMOilskaNWI5aTBnQ0ZMLXc/view?usp=drive_web
Click to enlarge

As can be seen from this simple, real world example, recursion describes the ability of a routine to call itself and is an alternative to iteration (repetition). It can provide elegant solutions to problems but, often not as efficient in terms of time and space (storage).

Also, before you start searching for a recursive solution to your problem, note that not all problems have a recursive solution. Although it is thought that every iterative solution has a recursive version ...

Task 1.3
Real examples of recursion

By referring to the lightbulb example above, can you come up with at least one example of recursion in real life? Can you write it out like a programmed function? Technically, the light bulb example is a recursive procedure rather than a function as no value is returned. 


OUTCOME : A made up function based on recursion but which is applied to a real life situation ... exam.pass()


Activity 2 Classic recursive problems (160)

What on Earth is Recursion? - Computerphile

https://drive.google.com/file/d/0B83yXMOilskaQl9BaklmNkpkZ0U/view?usp=drive_web
Click to enlarge

Recursion is classically used when the 'parts of a problem resemble the whole'. The most well known examples of problems that can be solved recursively are ...
  • Sum
  • Factorial
  • Power calculations (exponentiation)
  • Fibonacci
  • Base conversion
  • Greatest common divisor
  • Palindrome checker
  • Printing a list of number in order and in reverse order
  • Edges on a complete graph
Recursion makes extensive use of the stack (see the video above) to keep track of a) which recursive call is currently occuring, b) what line in the function to return to and c) current values of any local variables.

Sum of n numbers

Let's start by coding a recursive solution for a function, sum(n>0).

Base case : sum(n=0) = 0 
General case : sum(n>0) = n + sum(n-1)

Example sum(5)
5 + sum(4)
5 + (4 + sum(3))
5 + (4 + (3 + sum(2)))
5 + (4 + (3 + (2 + sum(1))))
5 + (4 + (3 + (2 + (1 + sum(0))))
5 + (4 + (3 + (2 + (1 + 0))))
5 + (4 + (3 + (2 + 1)))
5 + (4 + (3 + 3))
5 + (4 + 6)
5 + 10
15

Pseudocode : function sum(n):
  if n = 0 return 0
  else return n + sum(n-1) 

Task 2.1
A coded solution

  • Open up the Python programming environment, IDLE

  • Code a recursive function, sum(n), which takes one parameter, n, and returns sum(n) ...

    def sum(n):
      if n == 0:
        return 0
      else:
        return n + sum(n-1)

  • Convince yourself that the functions base case will always operate - by virtue of the fact that the recursive call uses n-1 as a parameter, this must always be the case. Nice.

  • Test your function works using three separate tests.

  • Now edit your original script to introduce some debug commands (in red) ...

    def sum(n,call=0):
      if n == 0:
        print('sum(0) = 0 ... Wind me back up!')
        return 0
      else:
        print('sum({1}) = {1} + sum({2}) : call={0}, n={1}'.format(call,n,n-1))
        return n + sum(n-1,call+1)

    ... and run this script with the same values you used in the previous tests. Can you see what has happened? Once our script reaches the base case, it 'knows' the answer to the unknown part of the previous function call and can then 'wind back up' through the calls until it returns the answer to the original question. Cool!

  • Now can you implement a simple iterative solution to this problem using a for loop? Compare your iterative and recursive solution - which do you 'prefer'?

  • Document what you have done and what you have learnt for your notes.
OUTCOME : Function, sum(n) and associated documentation.


OK - so let's summarise what we have done ...
  • Determined the condition(s) for the base case;
  • Determined the general case;
  • Code the base case. The base case must not contain a recursive call;
  • Coding the general case;
  • Heuristically ensured that the algorithm cannot skip the base case.
  • Tested our algorithm works

Factorial of n

One really classic example of recursion is factorial(n>0). If you are not sure what the factorial of a number is, ask a mathematician - they use them all the time!

Base case : factorial(n=0) = 1 
General case : factorial(n>0) = n * factorial(n-1)

Example factorial(5)
5 * factorial(4)
* (4 * factorial(3))
* (4 * (3 * factorial(2)))
* (4 * (3 * (2 * factorial(1))))
* (4 * (3 * (2 * (1 * factorial(0))))
* (4 * (3 * (2 * (1 * 1))))
* (4 * (3 * (2 * 1)))
* (4 * (3 * 2))
* (4 * 6)
* 24
120

Pseudocode : function factorial(n):
  if n = 0 return 1
  else return n * factorial(n-1) 


Task 2.2
A coded solution

  • Open up the Python programming environment, IDLE

  • Code a recursive solution to factorial(n). I would like you to try to create this function yourself using the previous example to help you. Check in with me if you are struggling.

  • Test your solution works using 3 separate tests. Don't go mad with 'n' or you might get a runtime error - don't say I didn't warn you!

  • Introduce debugging commands into your script like the previous example to help you to trace its operation.

  • Now can you implement a simple iterative solution to this problem using a for loop? Compare your iterative and recursive solution - which do you 'prefer'?

  • Document what you have done and learnt for your notes.
OUTCOME : Recursive function, factorial(n) and associated notes.


Power calculation

For a power function, we must specify two parameters - the base and the exponent and it is normally written mn where a is the base and b is the exponent.

Base case : power(m,n=0) = 1 
General case : power(m,n>0) = m * power(m,n-1)

Example power(4,3)
4 * power(4,2)
* (4 * power(4,1))
* (4 * (4 * power(4,0)))
* (4 * (4 * 1))
* (4 * 4)
* 16
64

Pseudocode : function power(m,n):
  if n = 0 return 1
  else return m * power(m,n-1) 

Task 2.3
A coded solution

  • Open up the Python programming environment, IDLE

  • Code a recursive solution to power(m,n). I would like you to try to create this function yourself using the previous example to help you. Check in with me if you are struggling.

  • Test your solution works using 3 separate tests. Don't go mad with 'n' or you might get a runtime error - don't say I didn't warn you!

  • Introduce debugging commands into your script like the previous example to help you to trace its operation.

  • Now can you implement a simple iterative solution to this problem using a for loop? Compare your iterative and recursive solution - which do you 'prefer'?

  • Document what you have done and learnt for your notes.
OUTCOME : Recursive function, power(m,n) and associated notes.


Caching in recursive functions

# Caching example
# ---------------
# Run the script with and without the first two lines 
# to see the effect of caching results
# Python uses a dictionary to do this

from functools import lru_cache
@lru_cache(maxsize=None)

def fibonacci(n):
  print('Calculating F({0})'.format(n))
  # Base case
  if n == 0: 
    print('Base case returning 0')
    return 0
  elif n == 1:
    print('Base case returning 1')
    return 1
  # General case
  else: return fibonacci(n-1) + fibonacci(n-2)

print(fibR(10))

Need to incorporate Fib into teaching and make something of this caching example.

If you haven't had enough yet, you might want to try to attempt to solve the remaining problems recursively :
  • Fibonacci series
  • Base conversion
  • Greatest common divisor
  • Palindrome checker
  • Printing a list of number in order and in reverse order
  • Edges on a complete graph
  • Adding up all the numbers in an integer without turning the numbers into strings


Activity 3 Contrived examples (40)

When someone else has done the work for you, it's not always necessary to go back to first principles to solve computational problems. That's the point. However, sometimes, it pays dividends to understand the principles underlying some common tasks.

Searching through a string to find occurrences of a character

The basic premise of this routine is just to check the first item in the string for a match, increment a counter variable for a match and send this through as an accumulator to recursively check the reminder of the string minus the first character. Technically, this is an example of tail recursion.

def countChar(s,c):
    if len(s) == 0:
        return 0
    else:
        if s[0] == c:
            return 1 + countChar(s[1:len(s)],c)
        else:
            return 0 + countChar(s[1:len(s)],c)

Modulo

A modulo function works out the remainder after division of one whole number by another. This routine works on the premise that division is repeated subtraction and keeps taking the divisor from the dividend until the value remaining is less than the dividend. Again this is an example of tail recursion.

def modulo(i,d):
    if i < d:
        return i
    else:
        return modulo(i-d,d)


Task 3.1
Implement this!

Try implementing these two examples of contrived recursion yourself and document their operation.

OUTCOME : Documented evidence of contrived recursion examples.


Activity 4 Consequences of recursion and when to use it (30)

The main consequences of recursion are ...
  • A more elegant or natural solution to a problem
  • A solution which is not as space and time efficient as iteration
  • A solution which can lead to stack overflow errors where values added to the stack frame fill the stack before the recursion ends.
Some programmers say never to use recursion but there are some limited situations where recursion performs better than iteration, namely during graph and tree traversal, directory structure navigation and operating system process management. Functional programming languages like Haskell only use recursion - they have no looping structures at all.

Task 4.1
Notes on uses of recursion

Visit the following websites and read about the benefits / uses of recursion ...
... and write some notes about the real uses of this esoteric programming technique.

OUTCOME : Some notes about real world uses for recursion



Extension Activities 

How about these?
  • Research the recursive solution to the Towers of Hanoi problem.  Can you code this in Python?

  • The Oxford University Computer Science Department use a piece of software called GeomLab which can be accessed online at their home page. Either by running the software online or by downloading the ‘binary jar file’, investigate how the software operates and use it to increase your knowledge of Recursion – there are a number of activities related to recursion in images on the ‘worksheets’ page.

  • There are also links to this and other resources at CS4FN which is a super website which contains lots of really interesting computer science stuff.  Fill your boots!

  • There is an alternative to traditional recursive functions called tail recursion which is more efficient (in terms of stack usage) for most languages.

What's next?

Before you hand your book in for checking, make sure you have completed all the work required and that your book is tidy and organised. Your book will be checked to make sure it is complete and you will be given a spicy grade for effort.

END OF TOPIC ASSESSMENT