Understanding Recursion

Structures de données et algorithmes en Python

Miriam Antona

Software engineer

Definition

  • Function calling itself
  • Almost all the situations where we use loops
    • substitute the loops using recursion
  • Can solve problems that seem very complex at first
Structures de données et algorithmes en Python

Example - factorial

$n!$

Structures de données et algorithmes en Python

Example - factorial

$n!=n$ · $(n-1)$ · $(n-2)$ · $...$ · $1$

$5!=$ $5$ · $4$ · $3$ · $2$ · $1=120$

def factorial(n):
  result = 1
  while n > 1:
    result = n * result
    n -= 1
  return result

factorial(5)

120
Structures de données et algorithmes en Python

Example - factorial using recursion

$n!= n$ · $(n-1)!$

def factorial_recursion(n):
  return n * factorial_recursion(n-1)
  • Executed forever!
Structures de données et algorithmes en Python

Example - identifying the base case

  • Add a condition
    • ensures that our algorithm doesn't execute forever
  • Factorial base case -> $n=1$
def factorial_recursion(n):
  if n == 1:

    return 1

  else:

    return n * factorial_recursion(n-1)

print(factorial_recursion(5))

120
Structures de données et algorithmes en Python

How recursion works

  • Computer uses a stack to keep track of the functions
    • Call stack
Structures de données et algorithmes en Python

How recursion works

  • factorial(5) starts
  • Before factorial(5) finishes -> factorial(4) starts
  • Before factorial(4) finishes -> factorial(3) starts

A picture of a queue with one element that represents a function.

Structures de données et algorithmes en Python

How recursion works

  • factorial(5) starts
  • Before factorial(5) finishes -> factorial(4) starts
  • Before factorial(4) finishes -> factorial(3) starts
  • Before factorial(3) finishes -> factorial(2) starts

A picture of a queue with two elements that represent two functions.

Structures de données et algorithmes en Python

How recursion works

  • factorial(5) starts
  • Before factorial(5) finishes -> factorial(4) starts
  • Before factorial(4) finishes -> factorial(3) starts
  • Before factorial(3) finishes -> factorial(2) starts
  • Before factorial(2) finishes -> factorial(1) starts

A picture of a queue with three elements that represent three functions.

Structures de données et algorithmes en Python

How recursion works

  • factorial(5) starts
  • Before factorial(5) finishes -> factorial(4) starts
  • Before factorial(4) finishes -> factorial(3) starts
  • Before factorial(3) finishes -> factorial(2) starts
  • Before factorial(2) finishes -> factorial(1) starts

A picture of a queue with four elements that represent four functions.

Structures de données et algorithmes en Python

How recursion works

  • factorial(1) finishes
    • returns 1
  • factorial(2) finishes

A picture of a queue with four elements that represent four functions.

Structures de données et algorithmes en Python

How recursion works

  • factorial(1) finishes
    • returns 1
  • factorial(2) finishes
    • returns 2

A picture of a queue with four elements that represent four functions. The last function is accompanied by its return value.

Structures de données et algorithmes en Python

How recursion works

  • factorial(1) finishes
    • returns 1
  • factorial(2) finishes
    • returns 2
  • factorial(3) finishes
    • returns 6

A picture of a queue with three elements that represent three functions.

Structures de données et algorithmes en Python

How recursion works

  • factorial(1) finishes
    • returns 1
  • factorial(2) finishes
    • returns 2
  • factorial(3) finishes
    • returns 6
  • factorial(4) finishes
    • returns 24

A picture of a queue with two elements that represent two functions.

Structures de données et algorithmes en Python

How recursion works

  • factorial(1) finishes
    • returns 1
  • factorial(2) finishes
    • returns 2
  • factorial(3) finishes
    • returns 6
  • factorial(4) finishes
    • returns 24
  • factorial(5) finishes
    • returns 120

A picture of a queue with one element that represents one function.

Structures de données et algorithmes en Python

How recursion works

  • factorial(1) finishes
    • returns 1
  • factorial(2) finishes
    • returns 2
  • factorial(3) finishes
    • returns 6
  • factorial(4) finishes
    • returns 24
  • factorial(5) finishes
    • returns 120

A picture of an empty queue.

Structures de données et algorithmes en Python

Dynamic programming

  • Optimization technique
  • Mainly applied to recursion
  • Can reduce the complexity of recursive algorithms
  • Used for:
    • Any problem that can be divided into smaller subproblems
    • Subproblems overlap
  • Solutions of subproblems are saved, avoiding the need to recalculate
    • Memoization
Structures de données et algorithmes en Python

Let's practice!

Structures de données et algorithmes en Python

Preparing Video For Download...