SciPy lecture, question 1 (recursive function)

Lectures
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