Recursive Techniques for Summation
undefined
Recursion and
Linked Lists
Recursion Exercises
Recursively sum a list
Let's code this up recursively:
Docstrings typically would not specify whether an approach was
recursive or iterative, since that is an implementation detail.
However, we'll make it clear in assignments and exam questions.
def sum_nums(nums):
"""Returns the sum of the numbers in nums.
>>> sum_nums([6, 24, 1984])
2014
>>> sum_nums([-32, 0, 32])
0
"""
Recursively sum a list (solution)
When recursively processing lists, the base case is often the empty list
and the recursive case is often all-but-the-first items.
def sum_nums(nums):
"""Returns the sum of the numbers in nums.
>>> sum_nums([6, 24, 1984])
2014
>>> sum_nums([-32, 0, 32])
0
"""
if nums == []:
return 0
else:
return nums[0] + sum_nums( nums[1:] )
Iteratively sum a range
Let's code this up iteratively:
def sum_up_to(n):
"""Returns the sum of positive numbers from 1
up to n (inclusive).
>>> sum_up_to(5)
15
"""
Iteratively sum a range (solution)
Using the range type:
Remember that
range(start, end)
always ends right before
end
.
def sum_up_to(n):
"""Returns the sum of positive numbers from 1
up to n (inclusive).
>>> sum_up_to(5)
15
"""
sum = 0
for i in range(1, n+1):
sum += i
return sum
Recursively sum a range
Now try it recursively:
def sum_up_to(n):
"""Returns the sum of positive numbers from 1
up to n (inclusive).
>>> sum_up_to(5)
15
"""
Recursively sum a range (solution)
Now try it recursively:
def sum_up_to(n):
"""Returns the sum of positive numbers from 1
up to n (inclusive).
>>> sum_up_to(5)
15
"""
if n == 1:
return 1
else:
return n + sum_up_to(n-1)
Recursively reversing a string
Breaking it down into subproblems
def reverse(s):
"""Returns a string with the letters of s
in the inverse order.
>>> reverse('ward')'draw'
"""
reverse("ward") = reverse("ard") + "w"reverse("ard") = reverse("rd") + "a"reverse("rd") = reverse("d") + "r"reverse("d") = "d"Recursively reversing a string (solution)
When recursively processing strings, the base case is typically an
empty string or single-character string, and the recursive case is often
all-but-the-first characters.
def reverse(s):
"""Returns a string with the letters of s
in the inverse order.
>>> reverse('ward')'draw'
"""
if len(s) == 1:
return s
else:
return reverse(s[1:]) + s[0]
Helper functions
If a recursive function needs to keep track of more state than the
arguments of the original function, you may need a helper function.
def fUnKyCaSe(text):
"""Returns text in fUnKyCaSe
>>> fUnKyCaSe("wats up")'wAtS Up'
"""
def toggle_case(letter, should_up_case):
return letter.upper() if should_up_case else letter.lower()
def up_down(text, should_up_case):
if len(text) == 1:
return toggle_case(text, should_up_case)
else:
return toggle_case(text[0], should_up_case) + up_down(text[1:], not should_up_case)
return up_down(text, False)
Reversing a number
def reverse_digits(n):
"""Returns n with the digits reversed.
>>> reverse_digits(123)
321
"""
Reversing a number (solution)
def reverse_digits(n):
"""Returns n with the digits reversed.
>>> reverse_digits(123)
321
"""
def reverse(n, r):
r *= 10
if n < 10:
return r + n
else:
return reverse(n // 10, r + n % 10)
return reverse(n, 0)
Recursion on different data types
Linked Lists
Why do we need a new list?
Python lists are implemented as a "dynamic array", which isn't optimal
for all use cases.
😭 Inserting an element is slow, especially near front of list.
What happens if we have this list and want to insert Z at the front
😭 Plus inserting too many elements can require re-creating the
entire list in memory, if it exceeds the pre-allocated memory.
A
B
C
D
E
F
G
Z
Linked Lists
A linked list is a chain of objects where each object holds a
value
and
a
reference to the next link
. The list ends when the final reference
is empty.
Let's add Z to this list:
Now let's add X after C
Linked lists require more space but provide faster insertion*.
* when we're already at the point of insertion.
A Link class
How would we use that?
class Link:
empty = ()
def __init__(self, first, rest=empty):
self.first = first
self.rest = rest
ll = Link("A", Link("B", Link("C")))View in PythonTutor
A fancier LinkedList
class Link:
"""A linked list."""
empty = ()
def __init__(self, first, rest=empty):
assert rest is Link.empty or isinstance(rest, Link)
self.first = first
self.rest = rest
def __repr__(self):
if self.rest:
rest_repr = ', ' + repr(self.rest)
else:
rest_repr = ''
return 'Link(' + repr(self.first) + rest_repr + ')'def __str__(self):
string = '<'
while self.rest is not Link.empty:
string += str(self.first) + ' '
self = self.rest
return string + str(self.first) + '>'
Creating linked lists
Creating a range
Similar to
[x for x in range(3, 6)]
def range_link(start, end):
"""Return a Link containing consecutive integers
from start to end, not including end.
>>> range_link(3, 6)
Link(3, Link(4, Link(5)))
"""
if start >= end:
return Link.empty
return Link(start, range_link(start + 1, end))
View in PythonTutor
Exercise: Mapping a linked list
Similar to
[f(x) for x in lst]
def map_link(f, ll):
"""Return a Link that contains f(x) for each x
in Link LL.
>>> square = lambda x: x * x
>>> map_link(square, range_link(3, 6))
Link(9, Link(16, Link(25)))
"""
Exercise: Mapping a linked list (solution)
Similar to
[f(x) for x in lst]
def map_link(f, ll):
"""Return a Link that contains f(x) for each x
in Link LL.
>>> square = lambda x: x * x
>>> map_link(square, range_link(3, 6))
Link(9, Link(16, Link(25)))
"""
if ll is Link.empty:
return Link.empty
return Link(f(ll.first), map_link(f, ll.rest))
View in PythonTutor
Exercise: Filtering a linked list
Similar to
[x for x in lst if f(x)]
def filter_link(f, ll):
"""Return a Link that contains only the elements
x of Link LL
for which f(x) is a true value.
>>> is_odd = lambda x: x % 2 == 1
>>> filter_link(is_odd, range_link(3, 6))
Link(3, Link(5))
"""
Exercise: Filtering a linked list (solution)
Similar to
[x for x in lst if f(x)]
def filter_link(f, ll):
"""Return a Link that contains only the elements
x of Link LL
for which f(x) is a true value.
>>> is_odd = lambda x: x % 2 == 1
>>> filter_link(is_odd, range_link(3, 6))
Link(3, Link(5))
"""
if ll is Link.empty:
return Link.empty
elif f(ll.first):
return Link(ll.first, filter_link(f, ll.rest))
return filter_link(f, ll.rest)
View in PythonTutor
Mutating Linked Lists
Linked lists can change
Attribute assignments can change
first
and
rest
attributes of a Link.
s = Link("A", Link("B", Link("C")))s.first = "Hi"
s.rest.first = "Hola"
s.rest.rest.first = "Oi"
View in PythonTutor
Beware infinite lists
The rest of a linked list can contain the linked list as a sub-list.
s = Link("A", Link("B", Link("C")))t = s.rest
t.rest = s
s.first
s.rest.rest.rest.rest.rest.first
# 'A'
# 'B'
Exercise: Adding to front of linked list
def insert_front(linked_list, new_val):
"""Inserts new_val in front of linked_list,
returning new linked list.
>>> ll = Link(1, Link(3, Link(5)))
>>> insert_front(ll, 0)
Link(0, Link(1, Link(3, Link(5))))
"""
Exercise: Adding to front of linked list
(Solution)
def insert_front(linked_list, new_val):
"""Inserts new_val in front of linked_list,
returning new linked list.
>>> ll = Link(1, Link(3, Link(5)))
>>> insert_front(ll, 0)
Link(0, Link(1, Link(3, Link(5))))
"""
return Link(new_val, linked_list)
Exercise: Adding to an ordered linked
list
def add(ordered_list, new_val):
"""Add new_val to ordered_list, returning modified ordered_list.
>>> s = Link(1, Link(3, Link(5)))
>>> add(s, 0)
Link(0, Link(1, Link(3, Link(5))))
>>> add(s, 3)
Link(0, Link(1, Link(3, Link(5))))
>>> add(s, 4)
Link(0, Link(1, Link(3, Link(4, Link(5)))))
>>> add(s, 6)
Link(0, Link(1, Link(3, Link(4, Link(5, Link(6))))))
"""
if new_val < ordered_list.first:
elif new_val > ordered_list.first and ordered_list.rest is Link.empty:
elif new_val > ordered_list.first:
return ordered_list
Exercise: Adding to an ordered linked
list (solution)
def add(ordered_list, new_val):
"""Add new_val to ordered_list, returning modified ordered_list.
>>> s = Link(1, Link(3, Link(5)))
>>> add(s, 0)
Link(0, Link(1, Link(3, Link(5))))
>>> add(s, 3)
Link(0, Link(1, Link(3, Link(5))))
>>> add(s, 4)
Link(0, Link(1, Link(3, Link(4, Link(5)))))
>>> add(s, 6)
Link(0, Link(1, Link(3, Link(4, Link(5, Link(6))))))
"""
if new_val < ordered_list.first:
original_first = ordered_list.first
ordered_list.first = new_val
ordered_list.rest = Link(original_first, ordered_list.rest)
elif new_val > ordered_list.first and ordered_list.rest is Link.empty:
ordered_list.rest = Link(new_val)
elif new_val > ordered_list.first:
add(ordered_list.rest, new_val)
return ordered_list
Delve into the world of recursion and linked lists with examples and solutions for summing elements both iteratively and recursively. Explore exercises and solutions for summing a list and a range of numbers, understanding base cases, and recursive implementations.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Recursion and Linked Lists
Recursively sum a list Let's code this up recursively: def sum_nums(nums): """Returns the sum of the numbers in nums. >>> sum_nums([6, 24, 1984]) 2014 >>> sum_nums([-32, 0, 32]) 0 """ Docstrings typically would not specify whether an approach was recursive or iterative, since that is an implementation detail. However, we'll make it clear in assignments and exam questions.
Recursively sum a list (solution) def sum_nums(nums): """Returns the sum of the numbers in nums. >>> sum_nums([6, 24, 1984]) 2014 >>> sum_nums([-32, 0, 32]) 0 """ if nums == []: return 0 else: return nums[0] + sum_nums( nums[1:] ) When recursively processing lists, the base case is often the empty list and the recursive case is often all-but-the-first items.
Iteratively sum a range Let's code this up iteratively: def sum_up_to(n): """Returns the sum of positive numbers from 1 up to n (inclusive). >>> sum_up_to(5) 15 """
Iteratively sum a range (solution) Using the range type: def sum_up_to(n): """Returns the sum of positive numbers from 1 up to n (inclusive). >>> sum_up_to(5) 15 """ sum = 0 for i in range(1, n+1): sum += i return sum Remember that range(start, end) always ends right before end.
Recursively sum a range Now try it recursively: def sum_up_to(n): """Returns the sum of positive numbers from 1 up to n (inclusive). >>> sum_up_to(5) 15 """
Recursively sum a range (solution) Now try it recursively: def sum_up_to(n): """Returns the sum of positive numbers from 1 up to n (inclusive). >>> sum_up_to(5) 15 """ if n == 1: return 1 else: return n + sum_up_to(n-1)
Recursively reversing a string def reverse(s): """Returns a string with the letters of s in the inverse order. >>> reverse('ward') 'draw' """ Breaking it down into subproblems reverse("ward") = reverse("ard") + "w" reverse("ard") = reverse("rd") + "a" reverse("rd") = reverse("d") + "r" reverse("d") = "d"
Recursively reversing a string (solution) def reverse(s): """Returns a string with the letters of s in the inverse order. >>> reverse('ward') 'draw' """ if len(s) == 1: return s else: return reverse(s[1:]) + s[0] When recursively processing strings, the base case is typically an empty string or single-character string, and the recursive case is often all-but-the-first characters.
Helper functions If a recursive function needs to keep track of more state than the arguments of the original function, you may need a helper function. def fUnKyCaSe(text): """Returns text in fUnKyCaSe >>> fUnKyCaSe("wats up") 'wAtS Up' """ def toggle_case(letter, should_up_case): return letter.upper() if should_up_case else letter.lower() def up_down(text, should_up_case): if len(text) == 1: return toggle_case(text, should_up_case) else: return toggle_case(text[0], should_up_case) + up_down(text[1:], not should_up_case) return up_down(text, False)
Reversing a number def reverse_digits(n): """Returns n with the digits reversed. >>> reverse_digits(123) 321 """
Reversing a number (solution) def reverse_digits(n): """Returns n with the digits reversed. >>> reverse_digits(123) 321 """ def reverse(n, r): r *= 10 if n < 10: return r + n else: return reverse(n // 10, r + n % 10) return reverse(n, 0)
Recursion on different data types Data Type Base case condition Current item Recursive case argument Numbers == 0 n % 10 n // 10 L[1:] L[:-1] Lists == [] L[0] == '' len(S) == 1 S[1:] S[:-1] Strings S[0]
Why do we need a new list? Python lists are implemented as a "dynamic array", which isn't optimal for all use cases. Inserting an element is slow, especially near front of list. What happens if we have this list and want to insert Z at the front A Z B C D E F G Plus inserting too many elements can require re-creating the entire list in memory, if it exceeds the pre-allocated memory.
Linked Lists A linked list is a chain of objects where each object holds a value and a reference to the next link. The list ends when the final reference is empty. Value: X Next: Let's add Z to this list: Value: Z Next: Value: A Next: Value: B Next: Value: C Next: Value: D Next: Value: E Next: () Now let's add X after C Linked lists require more space but provide faster insertion*. * when we're already at the point of insertion.
A Link class class Link: empty = () def __init__(self, first, rest=empty): self.first = first self.rest = rest How would we use that? ll = Link("A", Link("B", Link("C"))) View in PythonTutor
A fancier LinkedList class Link: """A linked list.""" empty = () def __init__(self, first, rest=empty): assert rest is Link.empty or isinstance(rest, Link) self.first = first self.rest = rest def __repr__(self): if self.rest: rest_repr = ', ' + repr(self.rest) else: rest_repr = '' return 'Link(' + repr(self.first) + rest_repr + ')' def __str__(self): string = '<' while self.rest is not Link.empty: string += str(self.first) + ' ' self = self.rest return string + str(self.first) + '>'
Creating a range Similar to [x for x in range(3, 6)] def range_link(start, end): """Return a Link containing consecutive integers from start to end, not including end. >>> range_link(3, 6) Link(3, Link(4, Link(5))) """ if start >= end: return Link.empty return Link(start, range_link(start + 1, end)) View in PythonTutor
Exercise: Mapping a linked list Similar to [f(x) for x in lst] def map_link(f, ll): """Return a Link that contains f(x) for each x in Link LL. >>> square = lambda x: x * x >>> map_link(square, range_link(3, 6)) Link(9, Link(16, Link(25))) """
Exercise: Mapping a linked list (solution) Similar to [f(x) for x in lst] def map_link(f, ll): """Return a Link that contains f(x) for each x in Link LL. >>> square = lambda x: x * x >>> map_link(square, range_link(3, 6)) Link(9, Link(16, Link(25))) """ if ll is Link.empty: return Link.empty return Link(f(ll.first), map_link(f, ll.rest)) View in PythonTutor
Exercise: Filtering a linked list Similar to [x for x in lst if f(x)] def filter_link(f, ll): """Return a Link that contains only the elements x of Link LL for which f(x) is a true value. >>> is_odd = lambda x: x % 2 == 1 >>> filter_link(is_odd, range_link(3, 6)) Link(3, Link(5)) """
Exercise: Filtering a linked list (solution) View in PythonTutor Similar to [x for x in lst if f(x)] def filter_link(f, ll): """Return a Link that contains only the elements x of Link LL for which f(x) is a true value. >>> is_odd = lambda x: x % 2 == 1 >>> filter_link(is_odd, range_link(3, 6)) Link(3, Link(5)) """ if ll is Link.empty: return Link.empty elif f(ll.first): return Link(ll.first, filter_link(f, ll.rest)) return filter_link(f, ll.rest)
Linked lists can change Attribute assignments can change first and rest attributes of a Link. s = Link("A", Link("B", Link("C"))) s.first = "Hi" s.rest.first = "Hola" s.rest.rest.first = "Oi" View in PythonTutor
Beware infinite lists The rest of a linked list can contain the linked list as a sub-list. s = Link("A", Link("B", Link("C"))) t = s.rest t.rest = s s.first # 'A' s.rest.rest.rest.rest.rest.first # 'B'
Exercise: Adding to front of linked list Value: Z Next: Value: A Next: Value: B Next: Value: C Next: Value: D Next: Value: E Next: () def insert_front(linked_list, new_val): """Inserts new_val in front of linked_list, returning new linked list. >>> ll = Link(1, Link(3, Link(5))) >>> insert_front(ll, 0) Link(0, Link(1, Link(3, Link(5)))) """
Exercise: Adding to front of linked list (Solution) def insert_front(linked_list, new_val): """Inserts new_val in front of linked_list, returning new linked list. >>> ll = Link(1, Link(3, Link(5))) >>> insert_front(ll, 0) Link(0, Link(1, Link(3, Link(5)))) """ return Link(new_val, linked_list)
Exercise: Adding to an ordered linked list Value: 6 Next: Value: 1 Next: Value: 3 Next: Value: 5 Next: Value: 7 Next: Value: 9 Next: () def add(ordered_list, new_val): """Add new_val to ordered_list, returning modified ordered_list. >>> s = Link(1, Link(3, Link(5))) >>> add(s, 0) Link(0, Link(1, Link(3, Link(5)))) >>> add(s, 3) Link(0, Link(1, Link(3, Link(5)))) >>> add(s, 4) Link(0, Link(1, Link(3, Link(4, Link(5))))) >>> add(s, 6) Link(0, Link(1, Link(3, Link(4, Link(5, Link(6)))))) """ if new_val < ordered_list.first: elif new_val > ordered_list.first and ordered_list.rest is Link.empty: elif new_val > ordered_list.first: return ordered_list
Exercise: Adding to an ordered linked list (solution) def add(ordered_list, new_val): """Add new_val to ordered_list, returning modified ordered_list. >>> s = Link(1, Link(3, Link(5))) >>> add(s, 0) Link(0, Link(1, Link(3, Link(5)))) >>> add(s, 3) Link(0, Link(1, Link(3, Link(5)))) >>> add(s, 4) Link(0, Link(1, Link(3, Link(4, Link(5))))) >>> add(s, 6) Link(0, Link(1, Link(3, Link(4, Link(5, Link(6)))))) """ if new_val < ordered_list.first: original_first = ordered_list.first ordered_list.first = new_val ordered_list.rest = Link(original_first, ordered_list.rest) elif new_val > ordered_list.first and ordered_list.rest is Link.empty: ordered_list.rest = Link(new_val) elif new_val > ordered_list.first: add(ordered_list.rest, new_val) return ordered_list
