Tutorial by Examples

If I wanted to find out the sum of numbers from 1 to n where n is a natural number, I can do 1 + 2 + 3 + 4 + ... + (several hours later) + n. Alternatively, I could write a for loop: n = 0 for i in range (1, n+1): n += i Or I could use a technique known as recursion: def recursion(n): ...

Recursion occurs when a function call causes that same function to be called again before the original function call terminates. For example, consider the well-known mathematical expression x! (i.e. the factorial operation). The factorial operation is defined for all nonnegative integers as follows:...

Say we have the following tree: root - A - AA - AB - B - BA - BB - BBA Now, if we wish to list all the names of the elements, we could do this with a simple for-loop. We assume there is a function get_name() to return a string of the name of a node, a function get_children() t...

There is a limit to the depth of possible recursion, which depends on the Python implementation. When the limit is reached, a RuntimeError exception is raised: RuntimeError: Maximum Recursion Depth Exceeded Here's a sample of a program that would cause this error: def cursing(depth): try: ...

When the only thing returned from a function is a recursive call, it is refered to as tail recursion. Here's an example countdown written using tail recursion: def countdown(n): if n == 0: print "Blastoff!" else: print n countdown(n-1) Any computat...

By default Python's recursion stack cannot exceed 1000 frames. This can be changed by setting the sys.setrecursionlimit(15000) which is faster however, this method consumes more memory. Instead, we can also solve the Tail Recursion problem using stack introspection. #!/usr/bin/env python2.4 # This...