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.

Sierpinski triangle

Fractal Tree

Extensions for the “fractal tree” program