Factorial (Recursive)

factorial(0) = 1, otherwise factorial(n) = n * factorial(n - 1). The smallest example of recursion with a single base case, used to visualise the call stack growing on descent and shrinking on unwind.

Algorithm

Canonical input n = 5 gives factorial(5) = 120. The replay shows six descent frames and five unwind frames (11 total).

Basic Implementation

basic.f90

module factorial_mod
    implicit none
contains
    recursive function factorial(n) result(r)
        integer, intent(in) :: n
        integer :: r
        if (n == 0) then
            r = 1
        else
            r = n * factorial(n - 1)
        end if
    end function factorial
end module factorial_mod

program recursion_factorial
    use factorial_mod
    implicit none
    integer :: result
    result = factorial(5)
    print '(I0)', result
end program recursion_factorial

Complexity

Time: O(n)
Space: O(n) call stack

Implementation notes

Fortran: the helper must be declared recursive function factorial(n) result(r) so the compiler permits self-calls. The result variable must be distinct from the function name to avoid the assumed-result alias.
The replay shows the call-stack contents on each frame and the computed n * factorial(n-1) value on each unwind, matching the lesson spec.

descend then unwind Each non-base call awaits the result of the next call, then multiplies.