🎓 A1Learner
🔍
0 of 52 lessons completed

Julia Recursion

Recursion is when a function calls itself to solve a smaller version of a problem. Each call works on a smaller input until the answer is simple enough to give directly.

A countdown calls itself with a smaller number

Each call prints its number and then calls itself with one less. The call with 0 is the stopping case and prints the final word.

function countdown(n)
    if n == 0
        println("Go!")
    else
        println(n)
        countdown(n - 1)
    end
end
countdown(3)

Factorial multiplies a number by the factorial below it

The factorial of 0 is 1 by definition, and that is the stopping case. Every other call multiplies its number by the answer from the smaller call.

function factorial(n)
    if n == 0
        return 1
    else
        return n * factorial(n - 1)
    end
end
println(factorial(5))
println(factorial(3))

A ternary can hold the stopping case

This function adds the whole numbers from 1 up to its input. When the input reaches 0, the ternary picks 0 and the calls stop.

function total(n)
    return n == 0 ? 0 : n + total(n - 1)
end
println(total(4))

Example

function countdown(n)
    if n == 0
        println("Go!")
    else
        println(n)
        countdown(n - 1)
    end
end
function factorial(n)
    if n == 0
        return 1
    else
        return n * factorial(n - 1)
    end
end
countdown(2)
println(factorial(4))

Key points

  • Recursive function: a function that calls itself inside its own body.
  • Stopping case: the simple input where the function gives an answer without calling itself.
  • Recursive call: the step where the function calls itself with a smaller input.
  • Smaller input: each call must move closer to the stopping case.
  • Unwinding: once the stopping case answers, the waiting calls finish one by one.

In this example, the program first defines countdown, whose stopping case prints Go. It then defines factorial, whose stopping case returns 1. The call countdown(2) prints 2, then 1, then Go. The last line prints the factorial of 4, which is 24.

Note

A recursive function with no stopping case would call itself forever, so the stopping case always comes first.

Try it Yourself

Edit the code, then press Run.

Running is simulated · JuliaHub

Exercise

Why does a recursive function need a stopping case?