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 ... 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 ...
On my to do list, I wrote only one item ...
There are plenty of examples of recursion in natures as well ... watch the following presentation.
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?)
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 ...
What on Earth is Recursion? - Computerphile
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 numbersLet's start by coding a recursive solution for a function,
`sum(n>0)` .
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 nOne 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!
Power calculationFor a power function, we must specify two parameters - the base and the exponent and it is normally written
`m` where `a` is the base and `b` is the exponent.
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
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 characterThe 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)` ModuloA 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)`
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.
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.
END OF TOPIC ASSESSMENT |