{title2=$F(0)=1,\quad F(n)=nF(n-1)$}

For a <natural number> $n$, the <factorial> satisfies $0!=1$ and $n!=n(n-1)!$ for $n\geq1$. The following description includes the zero <base case> explicitly; a negative or nonintegral <input> is outside its <precondition>:
``
F(n):
    require n is an integer and n >= 0
    if n == 0:
        return 1
    child_result = F(n - 1)
    return n * child_result
``
For $n=4$, the arguments on descent are $4,3,2,1,0$. Each positive-argument invocation postpones one <multiplication> until its <recursive call> returns. At the deepest point, the <call stack> has five <stack frames>: four suspended callers and the active zero <base case>. The invocation at zero returns $1$ to the invocation at one, rather than finishing the entire computation. Returns then give
$$
F(0)=1,\quad F(1)=1\cdot1=1,\quad F(2)=2\cdot1=2,\quad F(3)=3\cdot2=6,\quad F(4)=4\cdot6=24.
$$
A <stack frame> retains the caller's argument and where to resume. When the invocation at three receives $2$, it uses its own $n=3$, obtains $6$, and returns that value to the invocation at four. The <recursive calls> share a definition, but their local <variables> belong to separate invocations.

\Image[/recursion-factorial-returning-frames.png]
{title=Factorial descent builds pending work; returning frames complete it}
{description=Original trace of $F(4)$ with <base case> $F(0)=1$. The central snapshot shows all five <stack frames> at maximum depth. Downward arrows create <recursive calls>; upward arrows carry completed answers to suspended callers. A return removes only the completed invocation's <stack frame>.}

The <natural number> measure $n$ decreases by one on every <recursive call>, so <algorithm termination> follows. For <algorithm correctness>, use <mathematical induction>: the zero <base case> returns $0!=1$; assuming the child's answer is $(n-1)!$, the caller returns $n(n-1)!=n!$. This also explains why keeping the caller's $n$ matters.

There are exactly $n+1$ invocations and $n$ <multiplications>, including one invocation and no <multiplications> when $n=0$. Ordinary execution of this <recursive process> uses at most $n+1$ active <stack frames>, hence $O(n)$ frames for $n\geq1$ in <Big O notation>. If each test, call, <subtraction> and <multiplication> is counted as constant cost, its <time complexity> is $O(n)$. That is an arithmetic-operation model: exact arbitrary-length <integer> <multiplication> has growing cost, and neither the <factorial> <output> nor every <stack frame>'s numeric contents occupies a universally fixed number of <bits>.


 Factorial recursion and returning frames (source code)