"Everybody in this country should learn to program a computer, because it teaches you how to think” — Steve Jobs

Recursion

Recursion is one of the hardest computer programming concepts to understand.

Recursion is when a function calls itself.

A classic example that almost every Computer Science teacher uses is the “Factorial program”. (Factorials are used in Math (e.g. to calculate probability))

Factorial definition: (! is the factorial symbol)

1!=1

n!=n*(n-1)!

This is a recursive definition, because we use “!” to define “!”

(Similar to defining “writing” as “when you are writing something”)

5!= 5 * 4!

= 5 * 4 * 3!

= 5 * 4 * 3 * 2!

= 5 * 4 * 3 * 2 * 1!

= 5 * 4 * 3 * 2 * 1

= 120

Example of factorial program in Python.

# factorial.py (recursive factorial)

def fact(n):

if n==1: #base case

return 1

else:

return n * fact(n-1) #recursive function call

print fact(6) #calling the function “fact” from the main program (it will display 720)

After this program the teacher would usually talk about “call stack” and “stack frames” and some students would understand how recursion works (“pushing” and “popping” stack frames).

If students learn Computer Graphics before recursion, they can also see the power of recursion with the following 2 programs. With the graphical approach (visualizing recursion) more students understand the concept of recursion. In the following 2 examples there is some math included.