How do you formulate an equation that require its own result to replace one of its unknown?

Question

Is the concept of recursion used in Mathematics as it is in computer science? How would you express it in a formula?

Answer 1

The equivalent of CS recursion in mathematical logic is induction: if a family of well-formed statements is indexed by the natural numbers, and the first statement is provable, and the $n$-th statement is deducible from the $(n-1)$-th statement, then the statement $\forall n S(n)$ is provable.

Following the above comments I have to add that there is also the notion of a recurrence relation. It is a definition of a function $\mathbb N\to\mathbb N$ by providing an explicit formula that expresses $f(n)$ in terms of $f(n-1)$ (or in terms of several preceding values, which can be reduced to the original case by a few formal tricks). "Solving" the recurrence then means finding an explicit expression for $f(n)$ that no longer refers to other values of $f.$

Answer 2

Definition by recursion lets you define functions on $\Bbb N$ in terms of other functions:

Given a set $X$, $n\in\Bbb N$, a function $g\colon X^n\to X$, and another function $h\colon \Bbb N \times X\times X^{n+1}\to X$, there is a unique function $f\colon X^{n+1}\to X$ such that: $$\begin{align} f(0, \vec{x}) &= g(\vec{x}), \\ f(n+1, \vec{x}) &= h(n, f(n), \vec{x}) \end{align}$$ where $\vec{x}\in X^n$.

By induction, any function $f$ satisfying the conclusion is unique. Existence follows from the axioms of set theory.

It's possible to state the principle of definition by recursion more generally — for any well-ordered set, not just $\Bbb N$, an analogous statement is true.