# SciPy lecture, question 1 (recursive function)

#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 Like