Example 9 The permutation of integers $1,2, \cdots, n$ satisfies: each number is either greater than all the numbers before it, or less than all the numbers before it. How many such permutations are there?
(21st Canadian High School Mathematics Competition)
Let the number of permutations we are looking for be $a_{n}$.
Obviously, $a_{1}=1$.
For $n \geqslant 2$, consider the largest number $n$. If $n$ is placed in the $i$-th position, then the $n-i$ numbers after it are completely determined, i.e., they can only be $n-i, n-i-1, \cdots, 1$; and the $i-1$ numbers before it have $a_{i-1}$ ways to be arranged. Considering all different positions of $n$, by the principle of addition, we have
$$
a_{n}=1+a_{1}+a_{2}+\cdots+a_{n-1} .
$$

Thus,
$$
\begin{array}{l}
a_{n-1}=1+a_{1}+a_{2}+\cdots+a_{n-2} . \\
\text { Hence } a_{n}=2 a_{n-1} .
\end{array}
$$

From (1) and (2), we know
$$
a_{n}=2^{n-1} \text {. }
$$