Rekurzija Fantasticno!!!!

The document discusses recursion concepts through examples like computing factorials and lengths/sums of lists iteratively and recursively. It provides code examples and step-by-step workings of a recursive factorial function. Later sections include exercises on defining recursive functions for problems like finding the minimum element and checking membership in a list.

Uploaded by

Dragan

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

0% found this document useful (0 votes)

42 views73 pages

Rekurzija Fantasticno!!!!

Uploaded by

Dragan

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

You are on page 1/ 73

Recursion: concepts,

examples, and makeChange

Acknowledgement: The following slides are

adopted, some with minor revisions, from
several lecture slides of the CS5 Green
course at Harvey Mudd.
Factorial: Iteration Code

n! = n(n-1)(n-2)…1

def factorial(n):
result = 1
for k in range(1, n+1):
result = result * k
return result
Recursion…

n! = n(n-1)(n-2)…1
n! = n  (n-1)! “inductive definition”
Recursion…

n! = n(n-1)(n-2)…1
n! = n x (n-1)! “inductive definition”
0! = 1 “base case”

Why is
0! = 1?
Math Induction = CS Recursion

Math Python (Functional)

inductive
recursive function
definition

0! = 1 # recursive factorial
def factorial(n):
n! = n  (n-1)! if n == 0:
return 1
else:
return n * factorial(n-1)
Is Recursion Magic?
factorial(3):
return 3 * factorial(2)

# recursive factorial
def factorial(n):
if n == 0:
return 1
else:
return n*factorial(n-1)
Is Recursion Magic?
factorial(3):
return 3 * factorial(2)

return 2 * factorial(1)

# recursive factorial
def factorial(n):
if n == 0:
return 1
else:
return n*factorial(n-1)
Is Recursion Magic?
factorial(3):
return 3 * factorial(2)

return 2 * factorial(1)

return 1 * factorial(0)

# recursive factorial
def factorial(n):
if n == 0:
return 1
else:
return n*factorial(n-1)
Is Recursion Magic?
factorial(3):
return 3 * factorial(2)

return 2 * factorial(1)

1
return 1 * factorial(0)

# recursive factorial
def factorial(n):
if n == 0:
return 1
else:
return n*factorial(n-1)
Is Recursion Magic?
factorial(3):
return 3 * factorial(2)

return 2 * factorial(1)
1
return 1 * factorial(0)

# recursive factorial
def factorial(n):
if n == 0:
return 1
else:
return n*factorial(n-1)
Is Recursion Magic?
factorial(3):
return 3 * factorial(2)
2
return 2 * factorial(1)
1
return 1 * factorial(0)

# recursive factorial
def factorial(n):
if n == 0:
return 1
else:
return n*factorial(n-1)
Is Recursion Magic?
factorial(3): 6
return 3 * factorial(2)
2
return 2 * factorial(1)
1
return 1 * factorial(0)

# recursive factorial
def factorial(n):
if n == 0:
return 1
else:
return n*factorial(n-1)
Computing the length of a list
>>> len([1, 42, “spam”]) Python has
3 this built-in!
>>> len([1, [2, [3, 4]]])
2

def len(L):
‘’’returns the length of list L’’’
Computing the length of a list
>>> len([1, 42, “spam”]) Python has
3 this built-
>>> len([1, [2, [3, 4]]]) in!
2

def len(L):
‘’’returns the length of list L’’’
if L == []: return 0 # base case
Computing the length of a list
>>> len([1, 42, “spam”])
3
>>> len([1, [2, [3, 4]]])
2

def len(L):
‘’’returns the length of list L’’’
if L == []: return 0 # base case
else: return 1 + len(L[1:])
Summing up the numbers in a list
>>> sum([3, 42, 7])
52 Python has
>>> sum([42]) this built-in
42 too!
>>> sum([])
0

def sum(L):
‘’’returns the sum of numbers in the list’’’

Worksheet
Summing up the numbers in a list
>>> sum([1, 42, 7])
50
>>> sum([42])
42 The base
>>> sum([]) case takes
0 care of the
simplest
case we
def sum(L): could get.
‘’’returns the sum of numbers in the list’’’
if L == []: return 0
Summing up the numbers in a list
>>> sum([1, 42, 7])
50
>>> sum([42])
42
>>> sum([])
0

def sum(L):
‘’’returns the sum of numbers in the list’’’
if L == []: return 0
else: return ???
Summing up the numbers in a list
>>> sum([1, 42, 7])
50
>>> sum([42])
42
>>> sum([])
0

def sum(L):
‘’’returns the sum of numbers in the list’’’
if L == []: return 0
else: return L[0] + sum(L[1:])
Recursion = :^)
“To understand recursion, you
must first understand recursion”
-anonymous Mudd alum
The following pages have
a number of exercises for
you to do (in your notes).
You’re welcome to work
at your own pace.

min
member
pal
Minimum! [ , , ]