Higher-order functions¶
We covered higher-order functions (e.g., map, filter) last week, and last week's notebook contains various examples of higher-order functions.
As a reminder, map(func, data) applies a given function func to each element of data:
list(map(float, (0.2, '.5', 10, False, '-5')))
[0.2, 0.5, 10.0, 0.0, -5.0]
filter(func, data) applies a given function func (that returns True or False) to each element of data, and eliminates elements for which func returns False:
def is_numeric(x):
return type(x) in (int, float, complex, bool)
list(filter(is_numeric, (1, '2', 3.0, 4 + 5j, False, None, is_numeric, 'hello')))
[1, 3.0, (4+5j), False]
Recursion¶
Recursion is basically when you can define something using itself. (see the classic joke, did you mean recursion?). It is a technique in which a function solves a problem by calling it on smaller versions of the problem.
This idea lends itself nicely when we need to program algorithms or represent objects that are fractal-like in nature.
Recursive functions are made out of two parts:
- Recurrence relations (rules), where the function uses itself, inside the function definition.
- Base case(s), which represents the default values that the function takes for some values (ignoring the recurrence rule).
The trivial example of using recursion is computing the factorial for a number:
$n! = 1 \times 2 \times ... \times n$
For example, if n = 5, then
$5! = 1 \times 2 \times 3 \times 4 \times 5$
The recurrence is made clear when we look at n+1:
$$(n+1)! = 1 \times 2 \times \cdots \times n \times (n+1)$$
$$(n+1)! = (n+1) \times n! $$
Let's not forget that we need a base case so that we don't recurse infinitely. For the factorial function, we have the base case of $0! = 1$ which serves as our base case. The implementation is therefore trivial:
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1)
Now, factorial(6) will return 6 * factorial(5), which will be 6 * 5 * factorial(4), and so on until the result is 6! * factorial(0), where factorial(0) = 1 as we defined in our base case.
# Let's see it in action:
factorial(6)
720
# Another example
factorial(10)
3628800
Here's another example, using the Fibonacci numbers:
0, 1, 1, 2, 3, 5, 8, ...
They have the unique property that the next Fibonacci number is the sum of the previous two numbers in the sequence. The first two numbers (0 and 1) are exceptions to this rule (since they don't have any two numbers before them), so we should treat them as a base case.
Let's write a function that returns the i-th Fibonacci number, using these facts:
def fibonacci(index):
if index == 0:
return 0
if index == 1:
return 1
else:
return fibonacci(index - 1) + fibonacci(index - 2)
Our return value clearly reflects the idea of
$f_n = f_{n-1} + f_{n-2},$
where $n$ is the index of the Fibonacci sequence.
fibonacci(5) # 0, 1, 1, 2, 3, 5 <-- our expected value
5
Let's get the first 20 numbers in the sequence:
list(map(fibonacci, range(0, 20)))
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]
One such caveat of recursion-based methods is that when implemented naively, they can take a lot of time and memory. For example, let's see how much time it takes to find the 30th fibonacci number:
%timeit fibonacci(30)
53.4 ms ± 125 μs per loop (mean ± std. dev. of 7 runs, 10 loops each)
This takes a surprisingly long amount of time. The reason for this is that we are calling fibonacci many more times that we need to, and we're not storing the intermediate values for further use.
For demonstration purposes, let's track the number of times we use the fibonacci() function to find the 30th fibonacci number:
def fibonacci(index):
global fibonacci_counter
fibonacci_counter += 1
if index == 0:
return 1
if index == 1:
return 1
else:
return fibonacci(index - 1) + fibonacci(index - 2)
fibonacci_counter = 0
fibonacci(30)
print('Total number of calls to fibonacci():', fibonacci_counter)
Total number of calls to fibonacci(): 2692537
As an alternative, we can also implement our fibonacci function using an iterative approach. We'll still keep our base cases (index = 0 and index = 1), and in the general case we'll keep a loop to calculate the next fibonacci number using the relation $f_n = f_{n-2} + f_{n-1}$:
def fibonacci(index):
if index == 0:
return 0
elif index == 1:
return 1
n_minus_2 = 0 # Represents f_{n-2}
n_minus_1 = 1 # Represents f_{n-1}
i = index - 2
while i >= 0:
n = n_minus_2 + n_minus_1
n_minus_2 = n_minus_1
n_minus_1 = n
i = i - 1
return n
This implementation is very lightweight, since one loop is all it takes to calculate the next number in the sequence:
%timeit fibonacci(30)
493 ns ± 1.23 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
On my machine, the first version of fibonacci took around 50ms per loop, while this version takes around 500ns. Taking the ratio of these values gives us:
(50 * 1e-3) / (500 * 1e-9)
99999.99999999999
That's nearly a 100000x faster compared to the first version.
Here's the first 200 fibonacci numbers, using the iterative method:
list(map(fibonacci, range(0, 200)))
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842, 10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141, 117669030460994, 190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657, 2111485077978050, 3416454622906707, 5527939700884757, 8944394323791464, 14472334024676221, 23416728348467685, 37889062373143906, 61305790721611591, 99194853094755497, 160500643816367088, 259695496911122585, 420196140727489673, 679891637638612258, 1100087778366101931, 1779979416004714189, 2880067194370816120, 4660046610375530309, 7540113804746346429, 12200160415121876738, 19740274219868223167, 31940434634990099905, 51680708854858323072, 83621143489848422977, 135301852344706746049, 218922995834555169026, 354224848179261915075, 573147844013817084101, 927372692193078999176, 1500520536206896083277, 2427893228399975082453, 3928413764606871165730, 6356306993006846248183, 10284720757613717413913, 16641027750620563662096, 26925748508234281076009, 43566776258854844738105, 70492524767089125814114, 114059301025943970552219, 184551825793033096366333, 298611126818977066918552, 483162952612010163284885, 781774079430987230203437, 1264937032042997393488322, 2046711111473984623691759, 3311648143516982017180081, 5358359254990966640871840, 8670007398507948658051921, 14028366653498915298923761, 22698374052006863956975682, 36726740705505779255899443, 59425114757512643212875125, 96151855463018422468774568, 155576970220531065681649693, 251728825683549488150424261, 407305795904080553832073954, 659034621587630041982498215, 1066340417491710595814572169, 1725375039079340637797070384, 2791715456571051233611642553, 4517090495650391871408712937, 7308805952221443105020355490, 11825896447871834976429068427, 19134702400093278081449423917, 30960598847965113057878492344, 50095301248058391139327916261, 81055900096023504197206408605, 131151201344081895336534324866, 212207101440105399533740733471, 343358302784187294870275058337, 555565404224292694404015791808, 898923707008479989274290850145, 1454489111232772683678306641953, 2353412818241252672952597492098, 3807901929474025356630904134051, 6161314747715278029583501626149, 9969216677189303386214405760200, 16130531424904581415797907386349, 26099748102093884802012313146549, 42230279526998466217810220532898, 68330027629092351019822533679447, 110560307156090817237632754212345, 178890334785183168257455287891792, 289450641941273985495088042104137, 468340976726457153752543329995929, 757791618667731139247631372100066, 1226132595394188293000174702095995, 1983924214061919432247806074196061, 3210056809456107725247980776292056, 5193981023518027157495786850488117, 8404037832974134882743767626780173, 13598018856492162040239554477268290, 22002056689466296922983322104048463, 35600075545958458963222876581316753, 57602132235424755886206198685365216, 93202207781383214849429075266681969, 150804340016807970735635273952047185, 244006547798191185585064349218729154, 394810887814999156320699623170776339, 638817435613190341905763972389505493, 1033628323428189498226463595560281832, 1672445759041379840132227567949787325, 2706074082469569338358691163510069157, 4378519841510949178490918731459856482, 7084593923980518516849609894969925639, 11463113765491467695340528626429782121, 18547707689471986212190138521399707760, 30010821454963453907530667147829489881, 48558529144435440119720805669229197641, 78569350599398894027251472817058687522, 127127879743834334146972278486287885163, 205697230343233228174223751303346572685, 332825110087067562321196029789634457848, 538522340430300790495419781092981030533, 871347450517368352816615810882615488381, 1409869790947669143312035591975596518914, 2281217241465037496128651402858212007295, 3691087032412706639440686994833808526209, 5972304273877744135569338397692020533504, 9663391306290450775010025392525829059713, 15635695580168194910579363790217849593217, 25299086886458645685589389182743678652930, 40934782466626840596168752972961528246147, 66233869353085486281758142155705206899077, 107168651819712326877926895128666735145224, 173402521172797813159685037284371942044301]
Let's think of some other functions that can be implemented using recursion.
Checking if a number is even or odd, using recursion:
def is_even(num):
if num == 0:
return True
return not is_even(num - 1) # Would be equal to is_odd(num-1)
is_even(10)
True
is_even(999)
False
Example: Reversing a list, using recursion
The general idea is when we are writing our rev() function, we can pretend that it has already been implemented. So, reversing a list with rev() is the same as moving the first element of the list to the end, and reversing the rest of the list using rev().
Here, our base case is that an empty list is trivially reversed to be itself:
def rev(lst):
if lst == []:
return []
return rev(lst[1:]) + [lst[0]]
rev([1, 2, 3, 4, 5])
[5, 4, 3, 2, 1]
Example: Palindromes
Here's our implementation of checking if a string is a palindrome or not. Some notes:
- Our general idea is that a string is a palindrome if the first and last characters are the same, and the rest of the string is also palindrome (using the same idea).
- For strings of odd length, we will recurse until we have a string of one character. Trivially, such a string is a palindrome.
- For strings of even length, we will recurse until we have an empty string (
''). Again, such a string is a palindrome.
def is_palindrome(x):
if x == '':
return True
if len(x) == 1:
return True
return x[0] == x[-1] and is_palindrome(x[1:-1])
is_palindrome('aa')
True
is_palindrome('bab')
True
is_palindrome('aaababaaa')
True
is_palindrome('abab')
False
Finally, here is our annotated example of recursive binary search from class, a method that can be used for checking for a value inside a sorted container of values.
The general idea is that by comparing our searched value to the middle element in the list, we can eliminate half the values:
- If our value is smaller than the middle element, then it is also smaller than every number in the second half of the list. We can repeat the search using the first part of the list.
- If our value is bigger than the middle element, then it is also bigger than every number in the first half of the list. We can repeat the search using the second part of the list.
- If the middle number is equal to our number, than we have found our number.
- Finally, as a base case, an empty list trivially does not contain our value.
lst = [2, 4, 4, 4, 5, 6, 6, 8, 10, 12]
def binary_search(num, lst):
if lst == []:
return False
n = len(lst)
mid = n // 2
if num == lst[mid]:
return True
if num < lst[mid]:
print(f'{num} smaller than {lst[mid]}, searching in: {lst[:mid]}')
return binary_search(num, lst[:mid])
else:
print(f'{num} larger than {lst[mid]}, searching in: {lst[mid+1:]}')
return binary_search(num, lst[mid+1:])
binary_search(5, lst)
5 smaller than 6, searching in: [2, 4, 4, 4, 5] 5 larger than 4, searching in: [4, 5]
True
binary_search(12, lst)
12 larger than 6, searching in: [6, 8, 10, 12] 12 larger than 10, searching in: [12]
True
Here's happens when the searched value is not in the list:
binary_search(3, lst)
3 smaller than 6, searching in: [2, 4, 4, 4, 5] 3 smaller than 4, searching in: [2, 4] 3 smaller than 4, searching in: [2] 3 larger than 2, searching in: []
False
binary_search(7, lst)
7 larger than 6, searching in: [6, 8, 10, 12] 7 smaller than 10, searching in: [6, 8] 7 smaller than 8, searching in: [6] 7 larger than 6, searching in: []
False