## Functional Programming Basics

### Recursion and looping are related.

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.

## resources

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]:

print(result)

``````
``````

42
52

``````

## My rewrite of `functools.reduce` using recursion.

For the sake of demonstration only.

``````

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)

``````

## Test.

Test if the two functions return the sum of a list of random numbers.

``````

In [4]:

from random import choice

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))
for f
in (reduce, recursive_reduce))

test_results = ((f_name, test_answer == expected, )
try:
except AssertionError:
print(LINE)

``````
``````

--------------------
Testing these values: (1, 73, 82, 55)
The expected result: 211

`reduce` passed: True
`recursive_reduce` passed: True
--------------------
Testing these values: (43, 82, 37, 17, 99, 41, 32, 12)
The expected result: 363

`reduce` passed: True
`recursive_reduce` passed: True
--------------------
Testing these values: (46, 72, 90, 5, 76)
The expected result: 289

`reduce` passed: True
`recursive_reduce` passed: True
--------------------
Testing these values: (65, 31)
The expected result: 96

`reduce` passed: True
`recursive_reduce` passed: True
--------------------
Testing these values: (61, 14, 22, 61, 22, 58, 55)
The expected result: 293

`reduce` passed: True
`recursive_reduce` passed: True
--------------------

``````
``````

In [5]:

from recursion_looping_relationship_meta import tweets

``````
``````

Functional programming in three words: inquiry, declaration, abstraction. #functional #fp #crystallineIdea— Chris Stead (@cm_stead) March 19, 2016

Free book from O'Reilly Functional Programming in Python By David Mertz https://t.co/fVI2xsPEVC— CheckiO (@PlayCheckiO) October 7, 2016

Announcing @talkpython #82: Grokking Algorithms in Python with @_egonschiele https://t.co/j7Zl39lE6j pic.twitter.com/TYbjSr0LVw— Talk Python Podcast (@TalkPython) October 27, 2016

``````