Lab 4: Recursion
- Due: Friday 09/25 @ 11:59pm
- Points: 1
- Download: lab04.zip
Attendance
You need to submit the lab problems in addition to attending to get credit for lab. Students in mega lab only need to submit the lab problems. Preceptor interviews are highly recommended but not required for lab submissions.
If you are in regular lab, your TA will come around during lab to check you in. If you didn't attend for a good reason (such as being sick), fill out this form (within 2 weeks of your lab): attendance form.
Required Questions
Review
Lambda Expressions
Lambda expressions are expressions that evaluate to functions by specifying two things: the parameters and a return expression.
lambda <parameters>: <return expression>
While both lambda expressions and def statements create function objects,
there are some notable differences. lambda expressions work like other
expressions; much like a mathematical expression just evaluates to a number and
does not alter the current environment, a lambda expression
evaluates to a function without changing the current environment.
lambda |
def |
|
|---|---|---|
| Type | An expression that evaluates to a value. | A statement that alters the environment. |
| Result of execution | Creates an anonymous lambda function with no intrinsic name. | Creates a function with an intrinsic name and binds it to that name in the current environment. |
| Effect on the environment | Evaluating a lambda expression does not create or modify any variables. |
Executing a def statement both creates a new function object and binds it to a name in the current environment. |
| Usage | A lambda expression can be used anywhere that expects an expression, such as in an assignment statement or as the operator or operand of a call expression. |
After executing a def statement, use the function's bound name anywhere that expects an expression. |
lambda examples
# A lambda expression by itself does not alter
# the environment
lambda x: x * x
# We can assign lambda functions to a name
# with an assignment statement
square = lambda x: x * x
square(3)
# Lambda expressions can be used as an operator
# or operand
negate = lambda f, x: -f(x)
negate(lambda x: x * x, 3)
def example
def square(x):
return x * x
# A function created by a def statement
# can be referred to by its intrinsic name
square(3)
What Would Python Display? (WWPD)
Q1: WWPD: Lambda
Predict what Python will display when the following lines are entered into an interactive session, then unlock the test to check your answers:
Important: Type
FUNCTIONif you believe the answer is a function value. As a reminder, the following two lines of code will not display any output in the interactive Python interpreter when executed:>>> x = None >>> x >>>
python3 -m pytest -k lambda_wwpd --unlockUnlocking Examples
>>> lambda x: x # A lambda expression with one parameter x
______
>>> a = lambda x: x # Assigning the lambda function to the name a
>>> a(5)
______
>>> (lambda: 3)() # Using a lambda expression as an operator in a call expression
______
>>> b = lambda x, y: lambda: x + y # Lambdas can return other lambdas!
>>> c = b(8, 4)
>>> c
______
>>> c()
______
>>> d = lambda f: f(4) # They can have functions as arguments as well
>>> def square(x):
... return x * x
>>> d(square)
______
>>> higher_order_lambda = lambda f: lambda x: f(x)
>>> g = lambda x: x * x
>>> higher_order_lambda(g)(2)
______
>>> call_thrice = lambda f: lambda x: f(f(f(x)))
>>> call_thrice(lambda y: y + 2)(5)
______
>>> print_lambda = lambda z: print(z) # When is the return expression of a lambda expression executed?
>>> print_lambda
______
>>> one_thousand = print_lambda(1000)
______
>>> print(one_thousand) # What did the call to print_lambda return?
______
Recursion
Q2: Skip Factorial
Define the the skip_factorial function, which returns the
product of every other positive integer, starting with n.
def skip_factorial(n):
"""Return the product of positive integers n * (n - 2) * (n - 4) * ...
>>> skip_factorial(5) # 5 * 3 * 1
15
>>> skip_factorial(8) # 8 * 6 * 4 * 2
384
"""
if ___:
return ___
else:
return ___
python3 -m pytest -k skip_factorialHint
If n is even, then the base case will be 2. If n is odd, then the base case
will be 1. Try to write a condition that handles both possibilities.
Q3: Recursive Hailstone
Recall the hailstone function from Homework 1.
First, pick a positive integer n as the start. If n is even, divide it by 2.
If n is odd, multiply it by 3 and add 1. Repeat this process until n is 1.
Complete this recursive version of hailstone that prints out the values of the
sequence and returns the number of steps.
def hailstone(n):
"""Print out the hailstone sequence starting at n,
and return the number of elements in the sequence.
>>> a = hailstone(10)
10
5
16
8
4
2
1
>>> a
7
>>> b = hailstone(1)
1
>>> b
1
"""
print(n)
if n % 2 == 0:
return even(n)
else:
return odd(n)
def even(n):
return ____
def odd(n):
"*** YOUR CODE HERE ***"
python3 -m pytest -k hailstoneHint
An even number is never a base case, so even always makes a recursive call to
hailstone and returns one more than the length of the rest of the hailstone
sequence.
An odd number might be 1 (the base case) or greater than one (the recursive
case). Only the recursive case should call hailstone.
Optional Questions
These questions are optional. If you don't complete them, you will still receive credit for this assignment. They are great practice, so do them anyway!
Q4: Function Repeater
Define make_func_repeater, which takes a one-argument function f and a value
x. It returns another function that takes one argument, a non-negative
integer, and returns the result of applying f to x that many times.
Use recursion in your solution.
def make_func_repeater(f, x):
"""Return a function that applies f to x a given number of times.
>>> increment_repeater = make_func_repeater(lambda x: x + 1, 1)
>>> increment_repeater(2) # same as f(f(x))
3
>>> increment_repeater(5)
6
>>> increment_repeater(0)
1
"""
def repeat(____):
if ____:
return ____
else:
return ____
return ____
python3 -m pytest -k make_func_repeater