A recursive function is a function that calls itself in its body, either directly or indirectly. Recursive functions have two important components:
Let's look at the canonical example, factorial:
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
We know by its definition that 0! is 1. So we choose n = 0 as our base case. The recursive step also follows from the definition of factorial, i.e. n! = n * (n-1)!.
The next few questions in lab will have you writing recursive functions. Here are some general tips:
Make a recursive call with a slightly simpler argument. This is called the "leap of faith" - your simpler argument should simplify the problem, and you should assume that the recursive call for this simpler problem will just work. As you do more problems, you'll get better at this step.
Use the recursive call. Remember that the recursive call solves a simpler version of the problem. Now ask yourself how you can use this result to solve the original problem.
Problem 1: Write a function sum
that takes a single argument n
and computes the sum of all integers between 0 and n
. Assume n
is
non-negative.
Problem 2: Implement ab_plus_c
, a function that takes arguments
a
, b
, and c
and computes a*b + c
. You can assume a and b are
both positive integers. However, you can't use the *
operator. Try
recursion!
Problem 3: Now write the recursive version of summation
. Recall
that summation
takes two arguments, a number n
and a function
term
, and returns the result of applying term
to every number
between 0 and n
and taking the sum.
def summation(n, term):
if n == 0:
return term(0)
return term(n) + summation(n-1, term)
Recall the hailstone
function from homework 1. You
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. Write a recursive version of hailstone that prints out
the values of the sequence and returns the number of steps.
repeated
, repeatedIn Homework 2 you encountered the repeated
function, which takes
arguments f
and n
and returns a function equivalent to the nth
repeated application of f
. This time, we want to write repeated
recursively. You'll want to use compose1
, given below for your
convenience:
def compose1(f, g):
""""Return a function h, such that h(x) = f(g(x))."""
def h(x):
return f(g(x))
return h
This concludes the recursion portion of this lab. As a parting thought, keep in mind that recursion follows the same rules of evaluation that we've seen throughout the class. Try taking one of the above exercises and typing it into the online tutor! The remainder of the exercises will be various review problems.
For each of the following expressions, what must f
be in order for
the evaluation of the expression to succeed, without causing an error?
Give a definition of f
for each expression such that evaluating the
expression will not cause an error.
f
f()
f(3)
f()()
f()(3)()
Find the value of the following three expressions, using the given
values of t
and s
.
t = lambda f: lambda x: f(f(f(x)))
s = lambda x: x + 1
t(s)(0) # 1
t(t(s))(0) # 2
t(t)(s)(0) # 3
while
BunchIn lecture, you saw that it was possible to compute factorial
iteratively. Let's introduce a new function, a "falling" factorial
that takes two arguments, n
and k
and returns the product of k
consecutive numbers, starting from n
and working downwards. We're
going to write this iteratively - use a while
loop, instead of
recursion.
You hae seen continuous calculus in mathematics. However, there's
another definition of the derivative. Call the discrete derivative of
a function f
the quantity: Δf(n) = f(n+1) - f(n)
. Write a
higher order function make_deriv
that takes as input f
and
returns another function that calculates the discrete derivative.
Now, this type of calculus actually mirrors what you already know.
For example, the product rule actually holds as well in some form:
Δf(n)g(n) = Δf(n) g(n+1) + Δg(n) f(n)
Write
another higher order function called make_product
that takes two
functions f
and g
and returns a function that computes the
discrete derivative of the product. You can use the make_deriv
function that you defined above.
Draw the environment diagram for the following code:
def blondie(f):
return lambda x: f(x + 1)
tuco = blondie(lambda x: x * x)
angel_eyes = tuco(2)