

In [1]:

    
%load_ext watermark
%watermark -a 'Sebastian Raschka' -u -d -v









    



Sebastian Raschka 
last updated: 2017-08-03 

CPython 3.6.1
IPython 6.1.0

Examples using Recursion

Important Note

For most cases, using function recursion should be avoided in Python are better be implemented using for/while loops most of the time (although, I must admit that recursive solutions do look elegant). One of the reasons is that stacking recursive calls can easily blow up memory or at least result in the popular yet nasty "RuntimeError: maximum recursion depth exceeded". Also, keep in mind that Python does not optimize tail recursion in favor of having the full tracebacks for debugging; related to that, please see Guido van Rossums blog posts "Tail Recursion Elimination" and "Final Words on Tail Calls." If you do like to play around with recursion more efficiently, I highly recommend taking a look at Haskell or other functional programming languages. That being said, below are some examples of recursive function implementations in Python for illustrative purposes.

Factorial



In [2]:

    
def factorial(x):
    if x <= 1:
        return x
    else:
        return x * factorial(x-1)



In [3]:

    
factorial(0)









    Out[3]:





0



In [4]:

    
factorial(1)









    Out[4]:





1

5! = 5 x 4 x 3 x 2 x 1 = 120



In [5]:

    
factorial(5)









    Out[5]:





120

Length of an array



In [6]:

    
def array_len(x):
    if x == []:
        return 0
    else:
        return 1 + array_len(x[1:])



In [7]:

    
array_len([])









    Out[7]:





0



In [8]:

    
array_len([1, 2, 3])









    Out[8]:





3

Sum of the elements in an array



In [9]:

    
def array_sum(x):
    if x == []:
        return 0
    else:
        return x[0] + array_sum(x[1:])



In [10]:

    
array_sum([])









    Out[10]:





0



In [11]:

    
array_sum([5])









    Out[11]:





5



In [12]:

    
array_sum([1, 2, 3, 4, 5])









    Out[12]:





15

Binary search using recursion



In [13]:

    
def binary_search(array, value, min_idx=0, max_idx=None):
    
    if min_idx == max_idx:
        return None
    elif max_idx is None:
        max_idx = len(array)
    else:
        pass

    middle_idx = min_idx + (max_idx - min_idx) // 2

    if array[middle_idx] == value:
        return middle_idx
    elif array[middle_idx] < value:
        min_idx = middle_idx + 1
    else:
        max_idx = middle_idx
        
    return binary_search(array, value, min_idx, max_idx)



In [14]:

    
binary_search(array=[1, 2, 4, 7, 8, 10, 11],
                value=1)









    Out[14]:





0



In [15]:

    
binary_search(array=[1, 2, 4, 7, 8, 10, 11],
                value=2)









    Out[15]:





1



In [16]:

    
binary_search(array=[1, 2, 4, 7, 8, 10, 11],
                value=4)









    Out[16]:





2



In [17]:

    
binary_search(array=[1, 2, 4, 7, 8, 10, 11],
                value=11)









    Out[17]:





6



In [18]:

    
binary_search(array=[1, 2, 4, 7, 8, 10, 11],
                value=99)

Quicksort



In [5]:

    
def quicksort(array):
    if len(array) < 2:
        return array
    else:
        pivot = array[0]
        smaller, bigger = [], []
        for ele in array[1:]:
            if ele <= pivot:
                smaller.append(ele)
            else:
                bigger.append(ele)
        return quicksort(smaller) + [pivot] + quicksort(bigger)



In [6]:

    
quicksort([])









    Out[6]:





[]



In [7]:

    
quicksort([5])









    Out[7]:





[5]



In [8]:

    
quicksort([5, 4])









    Out[8]:





[4, 5]



In [9]:

    
quicksort([1, 2, 7, 5, 4])









    Out[9]:





[1, 2, 4, 5, 7]



In [10]:

    
quicksort([5, 4, 3, 2])









    Out[10]:





[2, 3, 4, 5]