Recursion in Python

We’ve seen examples of where one function calls another. For example inside of main, you see that load_data(), total(), and average() are called.

def main() :
  steps = load_data();
  total = get_total(steps);
  avg = get_average(steps);

Recursion is where a function, calls itself.

def foo() :
  foo()

As you can see, calling yourself is “easy” but also “dangerous”. You can easily end up in an infinite recursive loop, that is until you run out of function call depth and/or memory.

Therefore it is important to have a test (condition statement) which allows us to break out of the cycle of our recursive function. Consider the following example:

def message(counter) :
  if counter > 0 :
    print("This is a recursive function. We are on call", counter)
    message(counter - 1)

Check that, versus the following:

def message2(counter) :
  if counter > 0 :
    message2(counter - 1)
    print("This is a recursive function. We are on call", counter)

You can test these with a simple call:

def main() :
  message(5)
  message2(5)

main()

Notice how they behave differently based upon when the print statement is displayed vs the recursive call.

Each time the function is called, you get a completely independent set of local variables.

Recursive functions are useful is a problem can be broken down into smaller, identical problems.

Recursion vs Loops

Now, usually, a recursive function can be solved with a loop. Sometimes its easier to use recursion, and sometimes it is easier to use the loop. Knowing how to use both, makes your job as a programmer easier.

Consider the two ways we can write a solution to solving a factorial:

def factorial(num) :
  fac = 1
  while num > 1 :
    fac *= num
    num -= 1

  return fac

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

Direct vs Indirect Recursion

There are two types of recursion , direct and indirect.

So far, we’ve seen direct – where a function calls itself directly.

With indirect recursion, a function calls another function which then calls the original function. So there has to be at least two functions. Technically there can be more, for example a() -> b() -> c() -> a(), and so on.

Indirect recursion can happen accidentally, and cause issues with an infinite recursion. Direct recursion rarely happens accidentally. However, in both cases, you need to be careful with your tests to make sure you properly break out of your recursion.

Recursion in Python was originally found on Access 2 Learn