21: , D -C

[Pages:33]15-110 PRINCIPLES OF COMPUTING ? S19 LECTURE 21: RECURSION, DIVIDE-AND-CONQUER

TEACHER: GIANNI A. DI CARO

Recursion

The adjective recursive originates from the Latin verb recurrere, which means to run back. A recursive definition or a recursive function it is "running back" in the sense of returning to itself (possibly with a simpler instance)

"To understand recursion you must

first understand recursion!" J

Informal definitions of recursion: ? A function that makes a call to itself ? More in general, a thing defined in terms of itself or of its type

A matryoshka doll is a wooden Russian doll that contains a smaller sized matryoshka doll

? This might lead to an infinite regress! ? Properly defined mathematical recursion solution is never infinite: the recursive calls

to itself eventually reach an end, when some minimal input (base case) is reached

2

Infinite regression case

import time def infinite_regress(n):

print("At", n) time.sleep(0.01) # makes the process go to "sleep" for the given amount of seconds infinite_regress(n-1)

At 5

infinite_regress(5)

At 4

At 3

# need to interrupt the kernel to stop the running process that would never end, in theory.

At 2

At 1

# In practice it will end when the memory stack for calling the function will get full.

At 0

# When this happens we get the following error:

At -1 At -2

# RecursionError: maximum recursion depth exceeded while calling a Python object

At -3

At -4

At -5

At -6

? To make a meaningful use of recursion, we need to define

At -7 ....

criteria (base cases) for letting the recursive process reach an end (and then possibly reuse the values generated

At -2955 At -2956

---------------------------------------------------------------------------

during the recursion process)

RecursionError Traceback (most recent call last) in ()

----> 1 infinite_regress(5)

3

A concrete example: computing the factorial

? Mathematical definition (e.g., 5! = 5 ? 4 ? 3 ? 2 ? 1 = 120)

0! = 1

1! = 1

!! = ! ? ! - 1 ? ! - 2 ? ? 1,

! , ! > 1

? We can rewrite it as: 0! = 1 1! = 1 !! = ! ? ! - 1 !

! ,

!>1

? In a more general form: 2 ! !! ! 0

2 0 =1 2 1 =1 2 ! = ! 5 2(! - 1)

Recursive definition of the factorial function

4

A concrete example: computing the factorial

Recursive definition of the factorial function !: ! 0 = 1 ! 1 = 1 Base case(s): it doesn't require recursion, where the recursive calls of ! stop ! % = % & !(% - 1) Recursive case(s): the function calls itself, with a simpler instance / smaller value

def factorial_recursive(n): if n == 1 or n == 0: return 1 else: return n * factorial_recursive(n-1)

print(factorial_recursive(5)) 120

5

Let's look inside the recursive process ...

6

Let's look inside the recursive process ...

? Let's consider the case ! = 5 and let's expand the function calls:

n = 5 1

f(5) 6

n = 4 1

f(4) 5

n = 5 1

n = 5

f(5) 6

if 5 == 1: False

return 1

else:

return 5 * if 4 == 1: False

f(5)

return 1 else:

return 4 *

f(4)

n = 3 1

f(3) 5

n = 4 1

f(4) 5

n = 5 1

f(5) 6

if 3 == 1: False return 1

else: return 3 *

f(3)

n = 2 1

f(2) 5

n = 3 1

f(3) 5

n = 4 1

f(4) 5

n = 5 1

f(5) 6

if 2 == 1: False return 1

else: return 2 *

f(2)

n = 1 1

f(1) 5

n = 2 1

f(2) 5

n = 3 1

f(3) 5

n = 4 1

f(4) 5

n = 5 1

f(5) 6

if 1 == 1: True return 1

f(1)

Run-time memory stack

Recursive calls end: the base case, that does not require recursion, is reached!

7

Let's look inside the recursive process ...

? Now all the returns can be processed backward, popping out the functions' call frames from the run-time memory stack

120

n = 5 1

?

f(5)

?

6

return 5 * 24

n = 4 1

?

f(4)

?

5

n = 5 1

f(5) 6

return 4 * 6

n = 3 1

?

f(3)

?

5

n = 4 1

f(4) 5

n = 5 1

f(5) 6

return 3 * 2

return 2 * 1

n = 2 1

?

f(2)

?

5

n = 3 1

f(3) 5

n = 4 1

f(4) 5

n = 5 1

f(5) 6

n = 1 1

?

f(1)

?

5

n = 2 1

f(2) 5

n = 3 1

f(3) 5

n = 4 1

f(4) 5

Each function return pops out a call frame from the run-time memory stack

n = 5 1

if 1 == 1:

return 1

f(5) 6

8

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download