April 2018
Intermediate to advanced
408 pages
10h 42m
English
In some cases, the recursive definition is actually optimal. Some recursions involve a divide and conquer strategy that minimizes the work. One example of this is the exponentiation by the squaring algorithm. We can state it formally as follows:

We've broken the process into three cases, easily written in Python as a recursion. Look at the following command snippet:
def fastexp(a: float, n: int) -> float:
if n == 0: return 1
elif n % 2 == 1: return a*fastexp(a, n-1)
else:
t= fastexp(a, n//2)
return t*t
This function has three cases. The base case, the fastexp(a, 0) method is defined as having a value of 1. The ...