Recursion Examples in Python

Let’s look at some samples of using recursion. Sometimes we use t because it is easier to write and maintain. Sometimes it is because it’s about the only way we can.

The use of recursion is all around us. One major example is in fractals.

A fractal is a never-ending pattern. Fractals are infinitely complex patterns that are self-similar across different scales. They are created by repeating a simple process over and over in an ongoing feedback loop. Driven by recursion, fractals are images of dynamic systems – the pictures of Chaos. Geometrically, they exist in between our familiar dimensions. Fractal patterns are extremely familiar, since nature is full of fractals. For instance: trees, rivers, coastlines, mountains, clouds, seashells, hurricanes, etc. Abstract fractals – such as the Mandelbrot Set – can be generated by a computer calculating a simple equation over and over.

https://fractalfoundation.org/resources/what-are-fractals/

We’re going to look at some simpler forms of recursive functions however that allow us to better understand recursion.

Summing a List

def total(my_list, start, stop) :
  if start > stop :
    return 0
  else :
    return my_list[start] + total(my_list, start + 1, stop)

Here we have a list, and a starting and ending value. We assume that the starting and ending values are both positive, and the size of the list or smaller. We add an element from the list to be returned, and then call our function again, moving the starting index into our list forward by one value.

def total2(my_list) :
    if len(my_list) == 0 :
        return 0
    else :
        return my_list.pop() + total2(my_list)

Total 2 does a similar thing, however, it only requires passing the list. In it, you pop the last element off of the list, and add it to the value returned by the recursive all.

Of course there is a small problem with it, if we run it in a program.

arr = [1,3,5,1,4,2,6]
print(arr)       
print(total2(arr))
print(arr)

If you run this, you can see that the list is empty at the end. This is because lists are passed by value, so any changes to the list made inside a function, happen to the calling list as well.

Finding a Factorial

A factorial is the product of an integer and all the positive integers below it; For example 6 factorial (written as 6!) is 6*5*4*3*2*1.

def factorial(num) :
  if num < 0 :
    return 0
  elif num == 0 :
    return 1
  else :
    return num * factorial(num - 1)

The function calls itself multiplying the value by what is returned by the recursive function call.

Fibonacci Series

The Fibonacci Series of numbers is a number is a sum of the number of the two previous numbers. This means that they are designed to be recursive because their values are based on previous values.

It’s easy to code this in Python:

def fibonacci(num) :
  if num == 0 :
    return 0
  elif num == 1 :
    return 1
  else :
    return fibonacci(num - 1) + fibonacci(num - 2)

Recursion Examples in Python was originally found on Access 2 Learn