1 of 20

Introduction to Recursion

2 of 20

Agenda

  • What is Recursion?
  • The Fibonacci Sequence
  • Dynamic Programming
  • Recursive Commas

2

3 of 20

What is Recursion?

It’s turtles all the way down

1

4 of 20

What is Recursion?

  • A recursive function calls itself
    • Can call itself with different parameters
  • Function must eventually stop
    • This is so the program eventually stops
    • This is called the base case
  • Closely related to mathematical principle of induction

4

5 of 20

Why Have Recursion?

  • Many concepts in computer science are naturally defined in terms of themselves
  • Functions are at the core of procedural languages
  • It is therefore natural to implement recursive functions in computer science

5

6 of 20

The Fibonacci Sequence

Our first recursion

2

7 of 20

The Fibonacci Sequence

  • A common sequence used to introduce recursion
  • 1, 1, 2, 3, 5, 8, 13, 21, 34, …
  • Each term is the sum of the previous two terms
  • The base case is f(1)=f(2)=1

7

8 of 20

Fibonacci Sequence

  • Introductory course often use the Fibonacci Sequence to illustrate looping
  • However it can also be used as a way to illustrate recursion

8

9 of 20

Fibonacci Sequence

  • Implement a recursive version of the Fibonacci Sequence
  • Get a positive integer from the user
  • Use the base case and ensure your function calls itself to calculate the appropriate result

9

10 of 20

Fibonacci Sequence

  • Student Work 1
  • Student Work 2
  • Student Work 3

​

10

11 of 20

Dynamic Programming

Why recompute something?

3

12 of 20

Dynamic Programming

  • Clearly there is an issue with the program
  • In grade 11, with looping, you were able to get results much higher than this and it was much faster
  • Look at the function calls

12

13 of 20

Dynamic Programming

  • The program makes an exponential number of nested calls

​

13

14 of 20

Dynamic Programming

  • Instead of having so many function calls
  • Save the results of previous computations
  • Results usually save in arrays or other data structures

14

15 of 20

Dynamic Programming

  • Student Work 1
  • Student Work 2
  • Student Work 3

​

15

16 of 20

Recursive Commas

Are we sure this is recursive?

4

17 of 20

Recursive Commas

  • Take a positive integer and then add commas (or other separator) every third digit
  • That is 12345678901 becomes 12,345,678,901
  • Is this recursive?
    • It seems easy enough to do with loops
    • Instead write it recursively

17

18 of 20

Recursive Commas

  • Start at the end of the integer first
  • If it’s smaller than 1000, just write the integer and we’re done
    • This is the base case
  • Otherwise, write last three digits and a comma and recurse

18

19 of 20

Recursive Commas

  • Student Work 1
  • Student Work 2
  • Student Work 3

​

  • L09 Recursive Commas C++

19

20 of 20

Credits

Special thanks to all the people who made and released these awesome resources for free:

  • Presentation template by SlidesCarnival

20