Double Recursion¶

A nested two-level numerical recursion scheme that can feed earlier values into lower-row functions while preserving well-founded dependencies.

Version: v1 · 2026-10-17 · History
Domain-specific #: 14129
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomains: Recursive Function Theory, Numerical Definition Schemes → Mathematics

Core Idea¶

In the nested numerical convention, double recursion defines a family of natural-number functions by an initial row, a rule for starting each next row and a nested rule for its later values. The nested step may feed an earlier value in the current row into a function from a lower row. Recursive dependencies decrease the outer index, or keep that index and decrease the inner one; additional parameters need not decrease. Péter's 1935 treatment gives this scheme and explicit constructions using it.^[1]

The object is a form of numerical definition, rather than one particular rapidly growing function or a count of program calls. With finite substitution terms and total auxiliary functions, the decreasing dependencies define total values. With effective auxiliaries, they support effective computation. Some instances lie beyond the primitive-recursive class; others remain primitive recursive. Totality, computability and primitive recursiveness are separate questions.^[1]

Structural Signature¶

Ordered numerical indices → given auxiliary operations → complete initial row → next-row start → nested inner step → well-founded numerical definition.

Two recursion indices and optional parameters. Write \(F(m,n,\boldsymbol a)\), where \(m,n\in\mathbb N\) and \(\boldsymbol a\) is a finite parameter tuple, possibly empty. Merely having two arguments does not establish this structure.
Given helpers and finite terms. Specify the auxiliary numerical functions and the permitted finite substitutions. Calling a lower-row function at a computed argument is allowed; an unexplained, potentially divergent auxiliary search does not become total merely because the recursive indices decrease.
Whole initial row. Give \(F(0,n,\boldsymbol a)\) for all inner indices and parameters. Without it, the lower edge of the definition is unanchored.
Next-row initial value. Give \(F(m+1,0,\boldsymbol a)\) separately. At inner index zero there is no preceding value of the current row.
Nested inner step. Construct \(F(m+1,n+1,\boldsymbol a)\) through finite terms using the lower row and the previous current-row slice. The latter's output may become an argument of the former. Degenerate terms may ignore a permitted slot.
Well-founded dependency. Each recursive call uses a smaller outer index, or the same outer index and a smaller inner index. Parameters can change or grow without serving as ranks. Total helpers are a separate hypothesis.^[1]

The following is an explanatory renotation of the functional slots in Péter's equation (5), printed p. 50, rather than a verbatim transcription:

\[ \begin{aligned} F(0,n,\boldsymbol a)&=A(n,\boldsymbol a),\\ F(m+1,0,\boldsymbol a)&=T_0\!\left(m,\boldsymbol a; (z,\boldsymbol b)\mapsto F(m,z,\boldsymbol b)\right),\\ F(m+1,n+1,\boldsymbol a)&=T_1\!\left(m,n,\boldsymbol a; (z,\boldsymbol b)\mapsto F(m,z,\boldsymbol b), \boldsymbol b\mapsto F(m+1,n,\boldsymbol b)\right). \end{aligned} \]

Here \(T_0,T_1\) are finite substitution terms built from given numerical functions and the displayed function slots. They are not arbitrary higher-order procedures that may diverge. Only the preceding inner slice of the current row is available in the third clause; other recursive accesses are to a lower row. This presentation retains the optional parameters and distinguishes the definition rule from an implementation language.^[1]

What It Is Not¶

Not a two-argument function as such. Arity does not supply the three clauses, finite substitution rules or decreasing dependency. A function may admit such a presentation, but its argument list alone does not show it.
Not exactly two self-calls. A program's call count does not identify the permitted lower-row and previous-slice accesses. Conversely, a compound nested clause can contain several lower-row calls.
Not necessarily mutual recursion. Several named functions referring to one another do not by themselves provide this ordered row scheme.
Not necessarily non-primitive-recursive. For example, choosing constant-zero clauses throughout gives a degenerate primitive-recursive specialization. That is an illustration of the allowed scheme, not another historical construction.
Not an uncomputable definition. Péter's historical use of rekursiv concerns the restricted class now called primitive recursive. The title's nichtrekursiv must not be read as modern uncomputability.^[1]

A numerical function's membership in several classes or its availability through another encoding does not erase the particular structure of a supplied definition. Recognition here concerns a verified clause presentation; it is not a claim that no alternative iterative or single-counter representation can exist.

Scope of Application¶

The literal scope is nested numerical definition in recursive-function theory. Two different purposes occur in the same original paper: constructing a family that majorizes primitive-recursive functions, and constructing a uniform evaluator by prime-power coding. These are two whole mathematical constructions, not independent experiments or replications.^[1]

The convention permits additional numerical parameters. In particular, the coded evaluator below retains a third argument \(a\). Its role is not silently absorbed into one of the two recursion ranks. The definition does not cover every historical or modern meaning of “double,” “multiple” or “nested” recursion; those names require their own clause and function-class comparisons.^[1]

Clarity¶

Three names keep the examples separate. \(M(m,x)\) below renames the majorizing function that Péter writes with \(\varphi\) in §3. In §2, \(\varphi(m,n,a)=\varphi_m(n,a)\) is instead an evaluator for an enumeration of binary primitive-recursive functions; \(\psi\) is the prime-coded carrier used to put that evaluation into the nested scheme. Identical letters in separate parts of the source do not make these constructions identical.^[1]

The natural numbers include zero. For prime coding, \(p_0=2,p_1=3,p_2=5,\ldots\), and \(\pi_i(a)\) extracts the exponent of \(p_i\) in a positive integer \(a\), with the separate convention \(\pi_i(0)=0\). The source also adopts \(0^0=1\), which makes the power helper unambiguous at zero. The exponent convention at zero is not a literal factorization of zero.^[1]

“Earlier” describes the ranked pair, not every argument's numerical size. A call to \(F(m,z,\boldsymbol b)\) is below \(F(m+1,n+1,\boldsymbol a)\) even when \(z\) or a parameter is very large. This distinction is why nested substitution can remain well founded while escaping a primitive-recursive uniform definition.^[1]

Manages Complexity¶

The scheme separates how a new row may depend on earlier data from the numerical details of a particular construction. Initial data, row start, nested step and helper assumptions can be checked individually. A family with increasingly elaborate rows can thus have a compact uniform description without a single primitive-recursive uniform evaluator.^[1]

That compression is a definition-level benefit. It promises neither small outputs nor efficient evaluation, and does not furnish an empirical measurement or benchmark. A fixed row being primitive recursive is compatible with the complete two-variable family not being primitive recursive. The quantifier “for each row” must not be exchanged for one uniform primitive-recursive definition covering every row.^[1]

Abstract Reasoning¶

A useful totality proof first fixes the outer index. The initial row is given. Assuming the entire lower row is defined for every inner argument and parameter, the next row starts from finite applications of total helpers and lower-row functions. Induction on its inner index then supplies the rest of that row. Finite terms can call already established values at changed arguments; an undefined or divergent helper would break this proof. This is the dependency argument expressed by the clause scheme, not an additional theorem that every recursive-looking expression terminates.^[1]

A primitive-recursive classification requires more. In the majorant example, each unary primitive-recursive \(f\) has some row \(M(m,\cdot)\) above it at every input. It does not follow that each row dominates every such \(f\). The diagonal \(D(x)=M(x,x)\) yields the separate eventual-domination and non-primitive-recursiveness result.^[1]

The evaluator gives a different argument. If its uniform \(\varphi\) were primitive recursive, then

\[ \delta(n,a)=\varphi(n,n,a)+1 \]

would be a binary primitive-recursive function and so have some enumeration index \(k\). Substitution at \(n=k\) would give both \(\delta(k,a)=\varphi(k,k,a)\) and \(\delta(k,a)=\varphi(k,k,a)+1\), a contradiction. This expands Péter's diagonal reasoning on printed p. 49. It establishes failure of primitive recursiveness, not failure of computability.^[1]

Knowledge Transfer¶

Within numerical recursion theory, transfer consists of preserving the clause roles while changing what the values mean. The majorant's values are large numerical bounds; the evaluator's values encode finite lists of function outputs. Both have ranked indices, explicit helper operations, an initial row, a row start and nested dependencies. Their output specifications and non-primitive-recursiveness arguments remain different.^[1]

For a new construction, identify the indices and parameters, write all three clauses, expand the helpers and trace every recursive dependency. Only then ask whether the object majorizes a class, evaluates an enumeration or has another proven purpose. A resemblance to a two-level organizational hierarchy or two calls in a program supplies none of that mathematical mapping.

Examples¶

1. A majorizing numerical family¶

Péter's §3 construction is written here as \(M\), to avoid collision with the evaluator's \(\varphi\):

\[ \begin{aligned} M(0,x)&=2x+1,\\ M(m+1,0)&=M(m,1),\\ M(m+1,x+1)&=M\bigl(m,M(m+1,x)\bigr). \end{aligned} \]

These are the source's §17 clauses on printed p. 59; the base is \(2x+1\), not a later successor-base variant. The primitive-recursive majorization proof appears in §3, especially printed pp. 56–59.^[1]

Necessary role	Realization in this construction
Indices and parameters	Outer \(m\), inner \(x\); no extra parameter.
Helpers and finite terms	The linear base, constant \(1\) and finite composition.
Initial row	\(M(0,x)=2x+1\).
Row start	\(M(m+1,0)=M(m,1)\).
Nested step	The previous \(M(m+1,x)\) becomes an input of lower-row \(M(m,\cdot)\).
Decreasing dependency	The current-row call decreases \(x\); the enclosing call decreases \(m\), regardless of its computed input.

The role table is an analysis of the displayed source construction. For every unary primitive-recursive \(f\), there is an \(m\) such that \(f(x)<M(m,x)\) for every natural \(x\). Each fixed row is primitive recursive, while the uniform family is not. The diagonal \(D(x)=M(x,x)\) eventually dominates every unary primitive-recursive function and is not primitive recursive. These quantifiers concern a mathematical construction, not an observed growth comparison or an execution-time claim.^[1]

2. A prime-coded uniform evaluator¶

Péter's §2 enumerates the binary primitive-recursive functions as \(\varphi_m(n,a)\), allowing repetitions. The initial entries are

\[ \varphi_0(n,a)=n,\quad \varphi_1(n,a)=a,\quad \varphi_2(n,a)=p_n,\quad \varphi_3(n,a)=a^n,\quad \varphi_4(n,a)=\pi_n(a). \]

The source's explicit recursion and substitution indexing supplies the remaining entries. The uniform evaluator is \(\varphi(m,n,a)=\varphi_m(n,a)\). Its intermediate equation (6) is a course-of-values presentation; the positive nested construction below is the later carrier \(\psi\), not simply that intermediate equation relabeled.^[1]

Encode the outputs through index \(m\) by

\[ \psi(m,n,a)=\prod_{i=0}^{m}p_i^{\varphi(i,n,a)}, \qquad \varphi(i,n,a)=\pi_i\!\bigl(\psi(m,n,a)\bigr)\quad(0\le i\le m). \]

In particular, \(\varphi(m,n,a)=\pi_m(\psi(m,n,a))\). These are the coding and decoding relations on printed pp. 52–53.^[1]

The construction uses the following explicit selectors. For the selector values actually used, \(m\ge1\),

\[ \alpha(m,n,a,b,c)= \begin{cases} a &m=1,\\ p_n &m=2,\\ a^n &m=3,\\ \pi_n(a) &m=4,\\ b &m>4\text{ and }m\text{ even},\\ c &m>4\text{ and }m\text{ odd}. \end{cases} \]

No \(m=0\) branch is needed for the ensuing uses. Define

\[ \begin{aligned} \beta(m,a,c)&=\alpha(m+1,0,a,1,c),\\ \gamma(m,n,a,b,c)&=\alpha(m+1,n+1,a,b,c). \end{aligned} \]

These case and substitution definitions are on printed pp. 51–52. They are specified numerical helpers, rather than names hiding the desired evaluator.^[1]

The remaining compositions, printed p. 53 immediately before equation (9), are

\[ \begin{aligned} \mu_k(m,b)&=\pi_{\pi_k(m+1)}(b)\quad(k=0,1,2,3),\\ \nu(m,b)&=\pi_{m+1}(b),\\ \kappa(m,a,b,c)&=b\,p_{m+1}^{\beta(m,a,\mu_1(m,c))},\\ \lambda(m,n,a,b,c,d)&=b\,p_{m+1}^{\gamma(m,n,a,\mu_0(m,c),\mu_1(m,d))}. \end{aligned} \]

Here \(\lambda\) is the name of a particular numerical helper, not an unrestricted lambda-calculus operator. Prime selection, exponent extraction, arithmetic and the given case distinctions furnish the auxiliary operations.^[1]

With these definitions, the source's final equation (9), printed p. 53, is

\[ \begin{aligned} \psi(0,n,a)&=2^n,\\[2pt] \psi(m+1,0,a)&=\kappa\Bigl(m,a,\psi(m,0,a),\\ &\qquad\psi\bigl(m,\mu_2(m,\psi(m,0,a)), \mu_3(m,\psi(m,0,a))\bigr)\Bigr),\\[2pt] \psi(m+1,n+1,a)&=\lambda\Bigl(m,n,a,\psi(m,n+1,a),\\ &\qquad\psi\bigl(m,n,\nu(m,\psi(m+1,n,a))\bigr),\\ &\qquad\psi\bigl(m,\mu_2(m,\psi(m,n+1,a)), \mu_3(m,\psi(m,n+1,a))\bigr)\Bigr). \end{aligned} \]

The parameter \(a\) remains explicit throughout. In the step, \(\psi(m+1,n,a)\) is the only current-row recursive call; its value passes through \(\nu\) into a parameter of a lower-row call. Every other \(\psi\) access has outer index \(m\). Changed inner arguments and parameters in those lower-row calls do not violate the ranking.^[1]

Necessary role	Realization in this construction
Indices and parameters	Outer function-enumeration index \(m\), inner \(n\), retained numerical parameter \(a\).
Helpers and finite terms	The explicit prime/exponent operations and \(\alpha,\beta,\gamma,\mu,\nu,\kappa,\lambda\) above.
Initial row	\(\psi(0,n,a)=2^n\), encoding the initial evaluator \(\varphi_0(n,a)=n\).
Row start	The second clause of equation (9), combining lower-row values through \(\kappa\).
Nested step	The third clause, including the earlier current-row value inside \(\nu\), a lower-row call and \(\lambda\).
Decreasing dependency	The sole current-row access decreases the inner index; every remaining access decreases the outer index.

This role analysis concerns the full coded construction, including its helper chain. Decoding recovers every enumerated function. Since the evaluator cannot be primitive recursive by the diagonal argument, \(\psi\) cannot be primitive recursive either: otherwise primitive-recursive exponent extraction would recover a primitive-recursive evaluator. Its purpose is uniform evaluation and representation, rather than the first example's prescribed majorization. The two are unlike original constructions within one mathematical field and one article.^[1]

Structural Tensions¶

The definition scheme does not impose one universal pair of competing objectives. Well-founded totality and primitive-recursive expressibility are different properties: proving the first does not require maximizing it against the second. Likewise, a short definition can produce an expensive calculation, but that possibility is not a universal optimization trade-off constituting every instance. The useful discipline is to keep the separate proof obligations explicit.^[1]

Structural–Framed Character¶

Vocabulary travel. Ranked dependency and finite substitution are recognizable mathematical structures. The name double recursion here retains a particular numerical convention; using the name elsewhere does not establish the same definition.
Evaluative weight. Totality and primitive-recursive classification describe what a definition warrants. They do not rank it as morally or practically better.
Human-practice dependence. Notation, coding and clause choices are constructed. Once those choices are fixed, the equations and diagonal contradiction are mathematical obligations, not matters of curator or community approval.
Institutional origin. Recursive-function theory and the 1935 terminology explain the historical vocabulary. They do not make a function's values depend on an institution.
Recognition versus imported interpretation. A new numerical construction qualifies through its literal clause, helper and rank mapping. A metaphorical two-level process requires additional evidence before it can share that identity.^[1]

Its character: a structurally precise, domain-specific numerical definition scheme whose examples transfer through exact mathematical roles, while historical naming and helper assumptions constrain interpretation.

Structural Core vs. Domain Accent¶

The portable core is nested use of previously established values under a well-founded dependency rule. The domain specification consists of natural-number rows, finite numerical substitution, explicit auxiliary functions and comparison with the primitive-recursive class. Removing these commitments leaves a broader idea already expressed by Recursion and Well-Foundedness; it does not preserve this exact named scheme.^[1]

The two examples show variation inside numerical recursion theory. They do not establish an additional cross-domain Prime. Such a proposal would need independent cases in unlike domains, a common necessary structure surviving those changes and an account of what existing broader abstractions fail to cover. Similar words or two examples from the same article would not meet that evidential burden.

This entry presupposes Well-founded set.

Recursion provides the broader idea of defining values using other values of the same construction. Well-Foundedness clarifies why descending ranked dependencies can justify totality even when numerical parameters increase. These are conceptual relations; the precise numerical schema and helper obligations remain necessary to understand double recursion.^[1]

An Ackermann Function is a particular function or conventional family, rather than this entire definition scheme. A General Recursive Function concerns a computability class; Numbering concerns an indexing relation used by the evaluator example. Neither the complete computability class nor the existence of an enumeration substitutes for the three clauses. Mutual Recursion concerns interacting named definitions and is distinguished by that organization rather than by the number of recursion indices.

Relationships to Other Abstractions¶

Current abstraction Double Recursion Domain-specific

Parents (1) — more general patterns this builds on

Double Recursion presupposes Well-founded set Domain-specific

Double Recursion presupposes the well-founded lexicographic relation on its two natural-number recursion indices.

Hierarchy path (1) — routes to 1 parentless root

Double Recursion → Well-founded set

Neighborhood in Abstraction Space¶

Double Recursion sits in a sparse region of the domain-specific corpus (91^st percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (2721 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-17

Not to Be Confused With¶

Neighbor or near-miss	Discriminating test
Ackermann Function	Is the subject one selected function/variant, or the clause schema admitting many constructions, including primitive-recursive specializations?
Mutual Recursion	Are several definitions calling one another, or has a two-ranked numerical presentation with the stated three clauses been supplied?
General Recursive Function	Is the claim membership in a computability class, or a particular nested definition form? Non-primitive-recursive does not mean noncomputable.
Numbering	Is the subject an assignment of indices, or the explicit nested carrier used to evaluate and code indexed functions? Repetitions in this enumeration are allowed.
An ordinary two-index or two-call recurrence	Are the base row, row start, finite slots and decreasing dependencies established? Two indices or calls alone are insufficient evidence, but do not prove that a suitable presentation is impossible.
Nondecreasing self-reference	Which call is earlier? Without the required descent or total-helper hypotheses, the totality justification given here fails.

A familiar primitive-recursive function is not excluded merely by being primitive recursive. The question is whether its proposed presentation satisfies the scheme, not whether its name or growth rate resembles the majorizing example.^[1]

References¶

[1] Rózsa Péter, “Konstruktion nichtrekursiver Funktionen,” Mathematische Annalen 111 (1935), 42–60. DOI: 10.1007/BF01472200. Full original published-page facsimile, 19 pages, retained from a third-party mirror. General term conventions and historical usage: printed pp. 42–45. Prime/exponent conventions: p. 45. Enumeration and diagonal argument: pp. 48–49. General scheme: p. 50, eq. (5). Evaluator reduction, helpers and coding: pp. 51–53, especially eqs. (8)–(9); these are PDF pp. 10–12. Majorization and the renamed \(M\): §3, especially pp. 56 and 59; \(0^0=1\): p. 58. The general functional-slot display and role tables are explanatory analysis; the numerical constructions and helper formulas follow the original article. Both positive examples are formal constructions, not experimental studies. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s ↩t ↩u ↩v ↩w ↩x ↩y ↩z ↩27 ↩28 ↩29