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).

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

Visual walkthrough

The pinned run is factorial(5). The diagrams separate the descent, the base case, and the return values so the stack does not feel invisible.

Step 1 - Descend to the base case

Each call waits for one smaller call until f(0) returns 1.

Step 2 - Base value starts the unwind

The first finished frame is f(0) = 1; f(1) can now compute 1 * 1.

Step 3 - Unwind returns 120

Each frame multiplies its n by the completed smaller result.

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.