Sorting with Recursion

Prof. Dr. Mirco Schoenfeld

What this is about

https://xkcd.com/2688/

Getting Started

What does this code do?

def magic(s):
    if len(s) == 0: return ''
    if len(s) == 1: return s[0]
    return magic(s[1:]) + s[0]

Try it out, e.g. using

print(magic('do geese see god?'))

Recursion

That principle is called

Recursion

Recursion occurs when the definition of a concept or process depends on a simpler version of itself

https://en.wikipedia.org/wiki/Recursion

Recursion

Making sourdough requires sourdough.

https://commons.wikimedia.org/wiki/File:Mixing_Sourdough_starter_into_the_flour.jpg

Recursion

Recursion in computer science means that a function calls itself.

That requires

  • a breaking condition
  • mapping a problem to a simpler version of the problem

Quicksort

Using recursion, you can implement Quicksort,
an efficient sorting algorithm:

  1. if the list is empty, return
  2. pick a pivot element, e.g. the first in the list
  3. reorder:
    1. all elements smaller than the pivot
    2. all elements equal to the pivot
    3. all elements greater than the pivot
  4. recursively apply quicksort to the 1. and 3. subrange.

Quicksort

def quicksort(lst):
    if len(lst) == 0: # the breaking condition
        return lst
    pivot = lst[0]
    pivots = [x for x in lst if x == pivot]
    # here, the recursion happens
    # but with "simpler" (i.e. shorter)
    # versions of the list
    small = quicksort([x for x in lst if x < pivot])
    large = quicksort([x for x in lst if x > pivot])
    return small + pivots + large

quicksort([5,4,9,2,6,3,8,7,1,0])

Thanks

https://xkcd.com/244/

Back to Lecture Website