Recursion

Algorithmics – Session 2

  • What is recursion?
  • An example: Factorial
  • Principle
  • The call stack
  • Things to remember

What is recursion?

A fundamental concept in CS

Wikipedia

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

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

Factorial

A classic example


$$\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*}$$

Factorial

A classic example

$$\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

Principle

The two main parts of a recursive function

In Computer Science, a recursive function consists of two parts:

  • The base case – This condition(s) that ends the recursion.
  • The recursive call – This is when the function calls itself
def factorial(n):
  if n == 1: # base case, the recursion ends here
    # could also be n == 0
    return 1
  else: # recursive call, the function calls itself
    return factorial(n-1) * n

Note: Make sure the base case is reachable, otherwise the function will run forever.

The call stack

How recursion works

  • 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

The call stack

factorial(3):

stack

Things to remember

Check-list for recursive functions

  • Base case
    • Stops the recursion
    • Defines the result for the simplest case
  • Recursive call
    • Calls the function with
    • The function should eventually reach the base case

Recursive algorithms

Algorithmics – Session 2