SciPy lecture, question 1 (recursive function)

Lectures
1

Hello,

First of all, I wanted to thank the contributors to this site. I learned a lot from the lectures and I’m a very satisfied user of you module quantecon.py!

I would change a small detail to the solution of ex 1 of the lecture about SciPy. The function bisect() you propose does not return anything (except the output from print). Here is a simple way to fix it (the 3 lines containing “result” have been changed/added):

def bisect(f, a, b, tol=10e-5):
    """
    Implements the bisection root finding algorithm, assuming that f is a
    real-valued function on [a, b] satisfying f(a) < 0 < f(b).
    """
    lower, upper = a, b
    if upper - lower < tol:
        return 0.5 * (upper + lower)
    else:
        middle = 0.5 * (upper + lower)
        if f(middle) > 0:   # Implies root is between lower and middle
            result = bisect(f, lower, middle)
        else:               # Implies root is between middle and upper
            result = bisect(f, middle, upper)
    return result

Again, thanks for your great work!

2

Hi pyanni, not a maintainer/mod but this makes sense to me so I made the change in https://github.com/QuantEcon/lecture-py-notebooks/pull/1.

3

Hi @pyanni, the code actually does eventually return the root once the distance between the lower and upper bounds is less than the tolerance (this return statement is under the first ‘if’). Until then, the function recursively calls itself to apply the bisection method.

Hope that makes sense.

4

@natashawatkins The current code does return when it’s in the tolerance, but that only returns at the innermost recursion. It doesn’t get returned into the end result. We can see this by assigning a variable to the function result:

def bisect(f, a, b, tol=10e-5):
    """
    Implements the bisection root finding algorithm, assuming that f is a
    real-valued function on [a, b] satisfying f(a) < 0 < f(b).
    """
    lower, upper = a, b
    if upper - lower < tol:
        return 0.5 * (upper + lower)
    else:
        middle = 0.5 * (upper + lower)
        print(f'Current mid point = {middle}')
        if f(middle) > 0:   # Implies root is between lower and middle
            bisect(f, lower, middle)
        else:               # Implies root is between middle and upper
            bisect(f, middle, upper)

import numpy as np
f = lambda x: np.sin(4 * (x - 0.25)) + x + x**20 - 1
x = bisect(f, 0, 1)
print(x)  # None

@pyanni’s revision correctly assigns x a value:

def bisect(f, a, b, tol=10e-5):
    """
    Implements the bisection root finding algorithm, assuming that f is a
    real-valued function on [a, b] satisfying f(a) < 0 < f(b).
    """
    lower, upper = a, b
    if upper - lower < tol:
        return 0.5 * (upper + lower)
    else:
        middle = 0.5 * (upper + lower)
        if f(middle) > 0:   # Implies root is between lower and middle
            result = bisect(f, lower, middle)
        else:               # Implies root is between middle and upper
            result = bisect(f, middle, upper)
    return result

x = bisect(f, 0, 1)
print(x)  # 0.408294677734375

The issue is that calling bisect in the final 3 lines doesn’t return. We can save a line from pyanni’s revision by just adding return statements to the original there, i.e.:

def bisect(f, a, b, tol=10e-5):
    """
    Implements the bisection root finding algorithm, assuming that f is a
    real-valued function on [a, b] satisfying f(a) < 0 < f(b).
    """
    lower, upper = a, b
    if upper - lower < tol:
        return 0.5 * (upper + lower)
    else:
        middle = 0.5 * (upper + lower)
        print(f'Current mid point = {middle}')
        if f(middle) > 0:   # Implies root is between lower and middle
            return bisect(f, lower, middle)
        else:               # Implies root is between middle and upper
            return bisect(f, middle, upper)
1 Like
5

Just adding the returns is the best solution - thanks!

1 Like
6

@pyanni @MaxGhenis — I agree and I like both versions (the longer version is also good because it’s very explicit).

Thanks for the feedback and contributions :+1:

1 Like