Engineering 1020: Introduction to Programming

Lecture 23: Recursion

1 / 8

Let's finish up functions!Recall:Keyword argumentsDefault arguments2 / 8

Let's finish up functions!Recall:Keyword argumentsDefault argumentsToday:Recursion2 / 8

Recall: keyword arguments

Using the colour LCD screen:

rgb_lcd_colour(255, 0, 255)

(aside: what colour is this?)

Easier to tell now:

rgb_lcd_colour(red=255, green=0, blue=255)

No positional arguments after the first keyword argument

3 / 8

Recall: default arguments

def get_user_input(prompt='Input? '):
    return input(prompt)

Passed to the parameter if no argument in the call

One way to print:

print('these', 'words', 'go', 'on', 'one', 'line')
print('these', 'words', 'go', 'on', 'the', 'next', 'line')

Another way:

print(1, 2, 3, sep='*', end=' + ')
print(4, 5, 6, sep='*')

4 / 8

Recursion5 / 8

RecursionA function calling itself (??)5 / 8

There are lots of interesting problems in computing whose solutions can be expressed most elegantly via a recursive function. We won't require you to write a lot of those — that's more for a Data Structures and Algorithms course in Term 4 — but you do need to be at least somewhat familiar with the concept of recursion. It's an elegant tool, but like a lot of interesting concepts, it has subtleties to be aware of.

Recursion

A function calling itself (??)

def factorial(n):
    return n * factorial(n-1)

5 / 8

Recursion

A function calling itself (??)

def factorial(n):
    return n * factorial(n-1)

each call has its own variables

5 / 8

Recursion

A function calling itself (??)

def factorial(n):
    return n * factorial(n-1)

each call has its own variables
beware of infinite recursion (as in the example above!)

5 / 8

Like a loop with a perpetually-true condition, recursion can lead to a program that never stops running (at least until it runs out of memory for all of the function calls' memory!).

Recursion

A function calling itself (??)

def factorial(n):
    return n * factorial(n-1)

each call has its own variables
beware of infinite recursion (as in the example above!)
need a base case: when do we stop recursing?

5 / 8

Like a loop with a perpetually-true condition, recursion can lead to a program that never stops running (at least until it runs out of memory for all of the function calls' memory!).

A base case for recursion is when the recursion stops. In the example of a factorial, the factorial is actually defined in two parts:

$n! = n \times (n - 1)! | n > 0$

$0! = 1$

The base case for our factorial function, therefore, is that when n is 0, factorial should return 1.

ProblemsLet's work on some problems!6 / 8

SummaryMore fun with functions:Special arguments:keyword arguments
default arguments

Recursion
7 / 8

(here endeth the lesson)

8 / 8

↑, ←, Pg Up, k	Go to previous slide
↓, →, Pg Dn, Space, j	Go to next slide
Home	Go to first slide
End	Go to last slide
Number + Return	Go to specific slide
b / m / f	Toggle blackout / mirrored / fullscreen mode
c	Clone slideshow
p	Toggle presenter mode
t	Restart the presentation timer
?, h	Toggle this help

Engineering 1020: Introduction to Programming

Let's finish up functions!

Recall:

Keyword arguments

Default arguments

Let's finish up functions!

Recall:

Keyword arguments

Default arguments

Today:

Recursion

Recall: keyword arguments

Using the colour LCD screen:

Easier to tell now:

Recall: default arguments

One way to print:

Another way:

Recursion

Recursion

A function calling itself (??)

Recursion

A function calling itself (??)

Recursion

A function calling itself (??)

Recursion

A function calling itself (??)

Recursion

A function calling itself (??)

Problems

Let's work on some problems!

Summary

More fun with functions:

Let's finish up functions!

Recall:

Keyword arguments

Default arguments

Help