Recvrsio

Definitiones recvrsivae

Factoriale

Factoriale nvmeri natvralis $n$ est prodvctvm nvmerorvm natvralivm ab 1 ad $n$: $n! = 1 \cdot 2 \cdots n$, cvm conventione $0! = 1$. Pvncta svspensionis eivs formvlae circvitvm celant, et lectio Circvitvs docvit qvomodo scriberetvr. Atqvi eadem definitio aliam formam admittit, qvae nvllvm circvitvm memorat: factoriale ipsivs $n$ est $n$ vicibvs factoriale ipsivs $n - 1$, et factoriale nvmeri 0 est 1.

Haec est definitio recvrsiva: factoriale ipsivs $n$ per factoriale nvmeri minoris definit. Circvlaris non est, qvia qvaeqve applicatio secvndae regvlae gradvm vnvm descendit et scala in prima finitvr: $3! = 3 \cdot 2! = 3 \cdot 2 \cdot 1! = 3 \cdot 2 \cdot 1 \cdot 0! = 6$. Dvae regvlae nomen habent. Prima est casvs basis, qvi resvltatvm dat ad nihil alivd referens; secvnda est casvs recvrsivvs, qvi qvaestionem ad minorem eivsdem qvaestionis instantiam redvcit.

C++ fvnctioni permittit vt se ipsam vocet, et hoc modo definitio fere verbvm pro verbo transfertvr.

#include <print>​// Factoriale ipsivs n.// Praecondicio: 0 <= n <= 12 (margo infra ivstificatvr).// Postcondicio: reddit n! = 1 · 2 · ... · n, cvm 0! = 1.int factorial(int n){    if (n == 0) {        return 1;                   // casvs basis    }    return n * factorial(n - 1);    // casvs recvrsivvs}​int main(){    for (int n{0}; n <= 6; ++n) {        std::println("{}! = {}", n, factorial(n));    }}

0! = 11! = 12! = 23! = 64! = 245! = 1206! = 720

Pactvm non est ornamentvm: cvm $n = -1$ casvs recvrsivvs cvm $-2$ vocaret, deinde cvm $-3$, nec vmqvam ad 0 perveniret; et $13!$ in int non capitvr. Mvlti libri introdvctorii hoc factoriale cvm casv basis if (n == 0 || n == 1) scribvnt, svpervacvo sed innocvo, nec qvicqvam de negativis neqve de magnitvdine resvltati dicvnt: eorvm codex cvm $n < 0$ non finitvr et resvltatvm absvrdvm a $13!$ dat. Ambo vitia svo loco infra inspicientvr.

Casvs basis et casvs recvrsivvs

Omnis fvnctio recvrsiva vnvm vel plvres casvs basis habet, qvi directe solvvntvr, et vnvm vel plvres casvs recvrsivos, qvi eandem fvnctionem cvm argvmento aliqvo certo sensv minore vocant et id qvod reddit componvnt.

Potentia $x^n$, cvm $n$ natvrali, per $x^0 = 1$ et $x^n = x \cdot x^{n - 1}$ definitvr: magnitvdo est exponens. Svmma cifrarvm nvmeri natvralis $n$ (illa nvmeri 2026 est $2 + 0 + 2 + 6 = 10$) sic definitvr: si $n < 10$, svmma est $n$, qvia vnam tantvm cifram habet; sin minvs, est svmma cifrarvm ipsivs $\lfloor n / 10 \rfloor$, qvod est $n$ sine vltima cifra, addita ea vltima cifra, $n \bmod 10$. Hic magnitvdo est nvmervs cifrarvm.

#include <print>​// x ad potentiam n elatvm.// Praecondicio: n >= 0.// Postcondicio: reddit x^n, cvm x^0 = 1.double power(double x, int n){    if (n == 0) {        return 1.0;    }    return x * power(x, n - 1);}​// Svmma cifrarvm decimalivm ipsivs n.// Praecondicio: n >= 0.// Postcondicio: reddit svmmam cifrarvm ipsivs n.int digitSum(int n){    if (n < 10) {        return n;    }    return digitSum(n / 10) + n % 10;}​int main(){    std::println("2^10 = {}", power(2.0, 10));    std::println("1.5^3 = {}", power(1.5, 3));    std::println("svmma cifrarvm nvmeri 2026: {}", digitSum(2026));}

2^10 = 10241.5^3 = 3.375svmma cifrarvm nvmeri 2026: 10

Fvnctionem recvrsivam scribere igitvr est dvabvs qvaestionibvs respondere: qvi casvs sine avxilio solvantvr, et qvomodo solvtio casvs ex solvtione minoris obtineatvr. Si ambo responsa recta svnt, fvnctio qvoqve recta est, et qvae seqvvntvr id demonstrant.