1 of 28

AddisCoder: Week 2

Lecture 7A:

  • Recursion

2 of 28

Recursion

3 of 28

Lecture Idea Outline

  • Remember our function calls? Remember how they can call other functions?
  • Digit-extraction(371) = Digit-extraction(37) + [1] = [3,7,1]
  • Some problem depends on similar problems of the same type
  • Example: exponentiation as a running example
  • Iterative vs Recursive: side-by-side.
    • Pros/cons for each
  • Why is this useful?
    • Break large problem into smaller problems -> key idea in CS
    • If sub-problems are smaller versions of the larger problem, allows for elegant problem modeling for some very complex problems.

4 of 28

Context

We know how to define and call functions.

def sumTwo(x, y):

return x + y

​

def sumFour(a, b, c, d):

return a + b + c + d

​

print(sumTwo(1, 2)) # == 3

print(sumFour(9, 8, 7, 6)) # == 30

5 of 28

Context

We know how to call functions from other functions.

def sumTwo(x, y):

return x + y

​

def sumFour(a, b, c, d):

return sumTwo(a, b) + sumTwo(c, d)

​

print(sumTwo(1, 2)) # == 3

print(sumFour(9, 8, 7, 6)) # == 30

6 of 28

Functions Calling Themselves

Let’s make a more general sum function without using iteration (for loops).

​

​

7 of 28

General Steps for Recursion

  1. Given an instance of a problem, how can you break the problem down into smaller instances of the same type? (ignore the base-case)
  2. What are the simple cases that do not fit into the above pattern but we can solve directly by other means? (base case)
  3. Put them together

8 of 28

When to Use Recursion?

Recursion is used when a problem can be easily divided into smaller problems of the same form.

​

Are each of these well-suited to be written recursively?

  • Fine for driving over limit?
  • Steps for brushing your teeth?
  • Picking coins to make change?
  • Summing a list of numbers?

​

​

​

each step is different: find brush, apply paste, etc.

pick 1 coin, make change for remaining amount

add 1 number to sum of remaining list

no substeps: single conditional decision only

9 of 28

Why do we do this?

  • Learning to frame problems recursively is the first step to being able to solve much more complex algorithmic problems.

​

​

Many function can be written either as a loop or a recursion. However, for some more complex problems, the recursive implementation is much more elegant and easy to reason about.

10 of 28

Fibonacci

11 of 28

Fibonacci Sequence

Special sequence of numbers where a number is the sum of last two numbers

Start with 0 and 1

0, 1

12 of 28

Fibonacci Sequence

Special sequence of numbers where a number is the sum of last two numbers

Start with 0 and 1

0, 1,

+

0

1

1

13 of 28

Fibonacci Sequence

Special sequence of numbers where a number is the sum of last two numbers

Start with 0 and 1

0, 1,

+

1

1

1,

2

14 of 28

Fibonacci Sequence

Special sequence of numbers where a number is the sum of last two numbers

Start with 0 and 1

0, 1,

+

1

2

1,

2,

3

15 of 28

Fibonacci Sequence

Special sequence of numbers where a number is the sum of last two numbers

Start with 0 and 1

0, 1,

+

2

3

1,

2,

3,

5

16 of 28

Fibonacci Sequence

Special sequence of numbers where a number is the sum of last two numbers

Start with 0 and 1

0, 1,

+

3

5

1,

2,

3,

5,

8

17 of 28

Fibonacci Sequence

Special sequence of numbers where a number is the sum of last two numbers

Start with 0 and 1

0, 1,

+

5

8

1,

2,

3,

5,

8,

13

18 of 28

Fibonacci Sequence

Special sequence of numbers where a number is the sum of last two numbers

Start with 0 and 1

0, 1,

+

8

13

1,

2,

3,

5,

8,

13,

21

19 of 28

Fibonacci Sequence

Special sequence of numbers where a number is the sum of last two numbers

Start with 0 and 1

0, 1, 1, 2, 3, 5, 8, 13, 21...

20 of 28

Code Fibonacci Sequence

Function: fibonacci()

Input: number n

Output: nth value in Fibonacci Sequence

Examples:

fibonacci(0) -> 0

fibonacci(1) -> 1

fibonacci(2) -> 1

fibonacci(3) -> 2

​

fibonacci(4) -> 3

fibonacci(5) -> 5

fibonacci(6) -> 8

fibonacci(7) -> 13

21 of 28

Recursion

Way of describing problems

Way of designing solutions

​

Base case - simplest version of problem

Inductive case - how reduce problem to simpler versions of same problem

22 of 28

Base Case

Gives direct answer

Simple

​

23 of 28

Recursive / inductive case

  • Reduce to simplest version plus other simple operations

​

  • How do i build solutions to bigger problems from solutions to smaller versions of the same problems?

​

24 of 28

25 of 28

Example: Exponentiation

 

26 of 28

Example: Exponentiation

def exponent(b, n):

if n == 0:

return 1

return b * exponent(b, n - 1)

27 of 28

Another Exponentiation

 

28 of 28

Example: Exponentiation

def exponent(b, n):

if n == 0:

return 1

else:

m = n//2

bm = exponent(b, m)

if n % 2 == 0:

return bm*bm

else:

return bm*bm*b