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.

Sierpinski triangle

 

Fractal Tree

 

Extensions for the “fractal tree” program

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s