Showing Directly that Dyck Paths Satisfy the Catalan Recurrence How would one show, without appealing to a bijection with a well known problem, that Dyck Paths satisfy the Catalan recurrence?

A slightly novel approach to this: Considering your paths as mountain ranges (cf. this), let me first show:
Lemma. The number of mountain ranges (i.e. lattice paths over $\mathbb Z^2$ between $(0,0)$ and $(m,0)$ with only steps $(1,-1)$ and $(1,1)$) that is always contained in the region $\mathbb Z\times\mathbb Z_{\le 0}$ equals $0$ if $m\ge 1$ is not even and $$\binom{m}{\frac{m}2}-\binom{m}{\frac{m}2-1}$$
if $m\ge 2$ is even.
We also notice $$\binom{2m}{m}-\binom{2m}{ m-1}=\frac{(2m)!}{m!(m-1)!}\left(\frac1m-\frac1{m+1}\right)=\frac{1}{m+1}\binom{2m}m,$$ so that we indeed pick up the Catalan numbers $C_m$.
Proof (following this great post). If $m$ is not even, then looking at the $y$ coordinate modulo $2$ shows that you cannot land at $y=0$. Otherwise, you can pick $\frac{m}2$ "up" moves, then the other $\frac m2$ moves must be down moves to land at $y=0$. So $$\binom{m}{\frac{m}2}$$ is the number of mountain ranges starting at $(0,0)$ and ending at $(m,0)$. We now need to count the invalid mountain ranges, i.e. those which leave the $y\le 0$ range. Any such mountain range will have to intersect with the line $y=1$. By Andre's reflection principle, the number of mountain ranges that start at $(0,0)$, end at $(m,0)$ and intersect with $y=1$ equal the number of mountain ranges that start at $(0,2)$ and end at $(0,0)$. Using an analogous argument as before (exercise), this is $$\binom{m}{\frac m2-1},$$ which proves the Lemma. $\square$
Exercise. (see again the before-mentioned post) Generalize the Lemma to mountain ranges ending in $(m,n)$ for some $n\in\mathbb Z\cap [-m,m]$ and show that you obtain the number (where a binomial coefficient with negative entries is set to $0$ by convention) $$\binom{m}{\frac{m+n}{2}}-\binom{m}{\frac{m+n}{2}-1}.$$
Some nice applications:

*

*The number of all mountain ranges that start at $(0,0)$ and end in $x=m$ while always staying in $\mathbb Z\times\mathbb Z_{\le 0}$ is $$\sum_{k=-m}^0 \begin{cases}0 & \text{ if }m+k\text{ is odd};\\ \binom{m}{\frac{m+k}{2}}-\binom{m}{\frac{m+k}{2}-1} & \text{ if }m+k\text{ is even}.\end{cases}$$
This is a telescoping sum equal to $$\binom{m}{\frac{m}2}$$
if $m$ is even and $$\binom{m}{\frac m2-1}$$ if $m$ is odd. In short, the number equals $$\binom{m}{\left\lceil\frac m2\right\rceil}.$$

*One can do a similar thing if you don't want to intersect with $y=r+1$ for some $m>r\ge 1$. Looking at step 2 here (very similar to the Lemma above), we then obtain (binomial coefficients with negative entries being set to $0$) $$\sum_{k=-m}^r \binom{m}{\frac{m+k}2}-\binom{m}{\frac{m+k}2-r-1}.$$
This once again telescopes and we are left with, where for simplicity we assume $m\ge r+2$, (someone please re-check my calculations :)) $$\sum_{k=-r}^0\binom{m}{\left\lfloor\frac{m+r}2\right\rfloor+k}.$$
Here are some mountain ranges not surpassing a $y$-axis-barrier:

