This is my attempt to grok how recursion and looping are related.
I was already reading Functional Programming in Python when I discovered Grokking Algorithms: An illustrated guide for programmers and other curious people.
I was trying to make sense of this passage from Functional Programming in Python:
29.0 / 73 Functional Programming in Python by David Mertz
Eliminating Recursion
As with the simple factorial example given above, sometimes we can perform "recursion without recursion" by using functools.reduce() or other folding operations. A recursion is often simply a way of combining something simpler with an accumulated intermediate result, and that is exactly what reduce() does at heart.
And then I was NOT surprised to read this passage after reading about recursion in Grokking Algorithms: An illustrated guide for programmers and other curious people.
64.3 / 229 Grokking Algorithms: An illustrated guide for programmers and other curious people by Aditya Y. Bhargava
“Why would I do this recursively if I can do it easily with a loop?” you may be thinking. Well, this is a sneak peek into functional programming! Functional programming languages like Haskell don’t have loops, so you have to use recursion to write functions like this. If you have a good understanding of recursion, functional languages will be easier to learn.
And then I decided to search for some discussion about recursion from a JavaScript point of view and found this.
All in the Family: Filter, Map, Reduce, Recur
We loop over everything in the list and apply a reduction. You can create an add function and a list of numbers and try it for yourself. Anyway, if you really want to do this functionally, you would pull out our good friend, recursion. Recursion is a more mathematical means for looping over a set of values, and dates back to some of the earliest prototypes for computing back in the 1930’s.
Functional Programming in Python by David Mertz Copyright Get the free book here.
Grokking Algorithms: An illustrated guide for programmers and other curious people by Aditya Y. Bhargava
All in the Family: Filter, Map, Reduce, Recur: http://www.chrisstead.com/archives/841/all-in-the-family-filter-map-reduce-recur/
I am most comfortable with Python when it comes to exploring programming concepts, so I turned to the Python docs for more discussion.
Python docs: functools.reduce(function, iterable[, initializer])
Apply function of two arguments cumulatively to the items of sequence, from left to right, so as to reduce the sequence to a single value. For example, reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) calculates ((((1+2)+3)+4)+5). The left argument, x, is the accumulated value and the right argument, y, is the update value from the sequence. If the optional initializer is present, it is placed before the items of the sequence in the calculation, and serves as a default when the sequence is empty. If initializer is not given and sequence contains only one item, the first item is returned.
functools.reduce imitated here. Taken from the Python docs.
In [1]:
def reduce(function, iterable, initializer=None):
it = iter(iterable)
if initializer is None:
try:
initializer = next(it)
except StopIteration:
raise TypeError('reduce() of empty sequence with no initial value')
accum_value = initializer
# it exhausted if initializer not given and sequence only has one item
# so this loop does not run with sequence of length 1 and initializer is None
for x in it:
accum_value = function(accum_value, x)
return accum_value
Trying reduce without and with an initializer.
In [2]:
from operator import add
for result in (reduce(add, [42]), reduce(add, [42], 10)):
print(result)
In [3]:
def first(value_list):
return value_list[0]
def rest(value_list):
return value_list[1:]
def is_undefined(value):
return value is None
def recursive_reduce(function, iterable, initializer=None):
if is_undefined(initializer):
initializer = accum_value = first(iterable)
else:
accum_value = function(initializer, first(iterable))
if len(iterable) == 1: # base case
return accum_value
return recursive_reduce(function, rest(iterable), accum_value)
In [4]:
from random import choice
from operator import add
LINE = ''.join(('-', ) * 20)
print(LINE)
for _ in range(5):
# create a tuple of random numbers of length 2 to 10
test_values = tuple(choice(range(101)) for _ in range(choice(range(2, 11))))
print('Testing these values: {}'.format(test_values))
# use sum for canonical value
expected = sum(test_values)
print('The expected result: {}\n'.format(expected))
test_answers = ((f.__name__, f(add, test_values))
for f
in (reduce, recursive_reduce))
test_results = ((f_name, test_answer == expected, )
for f_name, test_answer in test_answers)
for f_name, answer in test_results:
try:
assert answer
print('`{}` passed: {}'.format(f_name, answer))
except AssertionError:
print('`{}` failed: {}'.format(f_name, not answer))
print(LINE)
In [5]:
from recursion_looping_relationship_meta import tweets