Understanding Recursion

Strutture dati e algoritmi in 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

Example - factorial

$n!$

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

Example - factorial using recursion

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

def factorial_recursion(n):
  return n * factorial_recursion(n-1)

• Executed forever!

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

How recursion works

• Computer uses a stack to keep track of the functions
  • Call stack

How recursion works

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

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

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

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

How recursion works

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

How recursion works

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

How recursion works

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

How recursion works

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

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

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

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

Let's practice!

Strutture dati e algoritmi in Python