Recursion

Algorithmics – Session 2

  • Recursive algorithms
  • Recap of the session

Recursive algorithms

What is recursion?

Definition

Recursion is the process a procedure goes through when one of the steps of the procedure involves invoking the procedure itself (Wikipedia)

In brief

  • Recursive functions are functions that call themselves
  • Recursive data structures contain references to instances of themselves

Recursive algorithms

A classic example: factorial

$$\begin{align*} n! &= \underbrace{1}_{1!} \times 2 \times \dots \times (n-1) &\times n\\ n! &= \underbrace{1 \times 2}_{2!} \times \dots \times (n-1) &\times n\\ n! &= \underbrace{1 \times 2 \times 3}_{3!} \times \dots \times (n-1) &\times n\\ &\dots\\ n! &= \underbrace{1 \times 2 \times 3\times \dots \times (n-1)}_{(n-1)!} &\times n\\ \end{align*}$$

Recursive algorithms

A classic example: factorial

$$\begin{align*} n! &= \underbrace{1 \times 2 \times \dots \times (n-1)}_{} &\times n\\ n! &= \quad\quad\quad(n-1)! &\times n\\ \end{align*}$$

  • $n!$ and $(n-1)!$ are related by a simple formula

  • This is a recursive definition of the factorial function

Recursive algorithms

Principle

The two main parts of a recursive function

  • The base case – This condition(s) that ends the recursion

  • The recursive call – This is when the function calls itself

def factorial (n: int):

    # Base case, the recursion ends here
    if n <= 1: 
        return 1

    # Recursive call, the function calls itself
    return factorial(n-1) * n

Important — Make sure the base case is reachable, otherwise the function will run forever

Recursive algorithms

How recursion works

The call stack

  • Each time a function is called, a new frame is added to the call stack

  • The frame contains the function’s arguments and local variables

  • When the function returns, the frame is removed from the stack

Recap of the session

Main elements to remember

Recursion is the process a procedure goes through when one of the steps of the procedure involves invoking the procedure itself


  • Base case(s):

    • Stop the recursion
    • Define the result for the simplest case(s)

  • Recursive call :

    • Calls the function with a more elementary case
    • The function should eventually reach the base case

Recap of the session

What’s next?

Practical activity (~2h30)

Experiment recursivity

  • Identify base cases and recursive calls
  • Various application exercises

After the session

  • Review the articles of the session
  • Check your understanding with the quiz
  • Complete the practical activity
  • Check next session’s “Before the class” section