Finally Understanding Recursive Functions

hy86592 — Tue, 17 May 2022 02:57:15 +0000

I used to have a hard time wrapping my mind around recursive function. Today, I learned 3 characteristics about recursion that makes them easy to understand.

The 3 characteristics of recursive functions:

Recursive functions have a state that is represented by a parameter value.
When calling the inner function, ensure that the parameter (state) must be modified in some way that brings it closer to the 'break condition' and eventually meet it.
Set the 'break condition' for which the inner function is not called again (i.e. breaking the recursion).

Let's see examples.

Function #1

def run():
  run()

run()

This will run until the stack overflows because it's just running itself continuously.

Function #2

def run(n):     # the state is represented by the value n
  run(n)        # no break condition; no change of state (n)

run(10)

This will also run until the stack overflows because there is no breaking condition.

Function #3

def run(n):
  if n == 10:      # break condition (always unsatisfied)
    run(n)         # no change of state (n)

run(10)

This will also run until the stack overflows because the state (n) always satisfies the condition for running.

Function #4

def run(n):
  if n == 10:      # break condition (always unsatisfied)
    run(n)         # no change of state

run(5)

This will never run a second time because the state (n) never meets the conditions for running again.

Function #5

def run(n):
  if n > 1:     # breaking condition (satisfied until the state meets breaking condition)
    run(n-1)    # continuous change of state

run(10)

This will run recursively until the breaking condition is met.

There you have it. A recursive function has a state that is represented by a parameter value and requires a change of state (n) which eventually meets the 'breaking condition' of the function.