Recursion

Cacao ad with a recursive image. The woman shows a package identical to that of her own announcement, thus containing another woman who shows another smaller package, in a recursive way.

Recursive image formed by a triangle of Sierpinski. Each triangle is composed of others, composed in turn of the same recursive structure.

Recursion or recursion is the way in which a process is specified based on its own definition. Recursion has this discernible characteristic in terms of self-referentiality, autopoiesis, fractality or, in other words, construction from the same type. With the aim of greater precision, and to avoid the apparent circularity in this definition, the concept of recursion is formulated as follows:

A problem that can be defined based on its size, be this N, can be divided into smaller instances (< N) of the same problem and the explicit solution to the simplest instances will be known, which are known as cases base, and induction can be applied to smaller calls and assumed to be resolved.^{[citation needed]}

Here are some examples:

• Factor: You want to calculate n!{displaystyle n,} (the factorial of n{displaystyle n,}which is defined as the product of all positive integers of 1{displaystyle 1,} a n{displaystyle n,}). You can define the problem on a recurrent basis as n(n− − 1)!{displaystyle n(n-1)}!as (n− − 1)!{displaystyle (n-1)}! is less than n!{displaystyle n,} We can apply induction so we have the result. The base case is 0!{displaystyle 0,} That's 1{displaystyle 1,}.
• Merge Management Algorithm: Be v a vector n elements, we can separate the vector in two halves. These two halves are sized n/2 so, by induction, we can apply ordination in these two subproblems. Once we have both tidy halves, we just have to merge them. The base case is to order a zero vector or an element, which is trivially ordained and nothing needs to be done.

In these examples it can be seen how a problem is divided into several (one or more) instances of the same problem, but smaller, thanks to which induction can be applied, reaching a point where the result is known (the base case).^{[citation required]}

Math Recursion

Recursively defined sets

An example of a recursively defined set is that of the natural numbers, that is, the set of non-negative integers:

1. 0{displaystyle 0,} belongs to N.
2. Yeah. n{displaystyle n,} belongs to N, then n+1{displaystyle n+1,} belongs to N.
3. Yeah. x{displaystyle x,} verifies the previous conditions, then x{displaystyle x,} is included in N ^{[chuckles]required]}.

Recursively defined functions

Those functions whose domain is a set at most enumerable can be defined recursively.

A well-known example is the recursive definition of the factorial function n!:

n!={Yeah.n=0⇒ ⇒ 1Yeah.n≥ ≥ 1⇒ ⇒ n(n− − 1)!{displaystyle n!={begin{cases}{mbox{si }}n=0 fakeRightarrow 1{mbox{si }ngeq 1 strangerRightarrow n;(n-1)!

Let's see how this definition can be used to find the value of the factorial of 3:

3!=3⋅ ⋅ (3− − 1)!=3⋅ ⋅ 2!=3⋅ ⋅ 2⋅ ⋅ (2− − 1)!=3⋅ ⋅ 2⋅ ⋅ 1!=3⋅ ⋅ 2⋅ ⋅ 1⋅ ⋅ (1− − 1)!=3⋅ ⋅ 2⋅ ⋅ 1⋅ ⋅ 0!=3⋅ ⋅ 2⋅ ⋅ 1⋅ ⋅ 1=6{cdot}{cdot}{cdot}{3cdot (3-1)!{{cdot 2}{cdot}{3cdot 2cdot (2-1)}{cdot}{3cdot}{3cdot}{3cdot}{1cdot}{1}{3}{3cdot}{1cdot}

Other examples of recursively defined mathematical functions and sequences are:

• Fibonacci succession — f(0)= 1, f(1) = 1; f(n) = f(n-1) + f(n-2) for n ≥ 2.
• Catalan Numbers — C(22)n, n)/(n+1)
• Ackermann function

Constants

The golden ratio can be defined recursively, as a continued fraction in which all numbers are ones:

φ φ =1+1φ φ =1+11+11+11+...{displaystyle phi =1+{frac {1}{phi }}=1+{cfrac {1}{1}{1+{cfrac {1}{1+{1}{1}{1}{1}}}}}}}}}}.

Similarly, identity x=1+x− − 11+x{displaystyle {sqrt {x}}=1+{frac {x-1}{1+{sqrt {x}}}}}}}{x1+{sqrt {x}}}}}}}} gives rise to a definition as a continuous fraction of any square root:

x=1+x− − 12+x− − 12+x− − 12+ {displaystyle {sqrt {x}}=1+{cfrac {x1}{2+{cfrac {x1}{2+{cfrac {x1}{2+{ddots}}}}}}}}}}}}}

Troubleshooting

Solving homogeneous equations of first degree, second order:

(a) The terms are passed to the first member an{displaystyle a_{n}}, an− − 1{displaystyle a_{n-1}, an− − 2{displaystyle a_{n-2}}which could also be an+2{displaystyle a_{n+2}}, an+1{displaystyle a_{n+1}}, an{displaystyle a_{n}}

(b) Replacement an{displaystyle a_{n}} for r2{displaystyle r^{2}}, an− − 1{displaystyle a_{n-1} for r{displaystyle r} and an− − 2{displaystyle a_{n-2}} for 1{displaystyle 1}, remaining a second degree equation with real and different roots r1{displaystyle r_{1}} and r2{displaystyle r_{2}}.

(c) It raises a=ur1n+vr2n{displaystyle a=u;r_{1}n+v;r_{2}n}

(d) We must have as a data the values of the first two terms of succession: A0=k{displaystyle A_{0}=k,} and A1=k♫ ♫ {displaystyle A_{1}=k^{prim }}. Using this data we order the 2x2 system:

{u+v=kur1+ur2=k♫ ♫ {displaystyle {begin{cases}u+v=ku;r_{1}+u;r_{2}=k^{prim }end{cases}}}}}}}}}

The resolution of this system results in the values u0{displaystyle u_{0}} and v0{displaystyle v_{0}}which are known real numbers.

e) The general solution is:

an=u0r1n+v0r2n{displaystyle a_{n}=u_{0};r_{1}n+v_{0};r_{2}n}

Recursion in computer science

In programming, a common method of simplifying a complex problem is to divide it into subproblems of the same type. This programming technique is known as divide and conquer and it is the core in the design of numerous algorithms of great importance, as well as a fundamental part of dynamic programming.

C implementation:

int factorial (int n){ if (n ▪ 1) { return n ♪ factorial(n-1); !else { return 1; !!int main(){ printf("Recustivityn"); int result = factorial(5); printf("The result is: %i", result); return 0;!

C++ implementation:

 int factorial(int x) { if (x ▪ -1 " fake " x . 2) return 1; // When -1 Δ 2 we return 1 since 0! = 1 and 1! = 1 else if (x . 0) return 0; // Error does not exist factorial of negative numbers return x ♪ factorial(x - 1); // Yes x  2 return the product of x by the factorial of x - 1 !

Pascal implementation:

 FUNCTION Factor (CONST N: INTEGER): INTEGER; BEGIN IF N ▪ 1 THEN Factor := N ♪ (Factor (N - 1); ELSE BEGIN IF (N=0) OR (N=1) Factor := 1; ELSE Factor := 0; END; END; END;

Python implementation:

def factorial(n(c): if n ♪ 1 or n ♪ 0: return 1 else: return n ♪ factorial(n-1)

The monitoring of the programmed recursion is almost exactly the same as the examples given before, to try to help it to be better understood, it has been accompanied with many explanations and with colors that differentiate the different sub-processes of the recursion.

X = 3 //We want 3!, therefore X initial is 3
X pur= 2 - voluntary return 3*factorial(2); X = 2 //Now we are requesting the 2-factorial
 X pur= 2 - tax return 2*factorial(1); X = 1 // Now we are requesting the 1 factor
 " X ";[At this point we have the 1 factorial so we turn back solving all the results]
 return 2 [i.e. return 2*1 = return 2*factorial(1)]
return 6 [i.e. return 3*2 = return 3*factorial(2)*factorial(1)] // The returned result is 6

Recursive humor

Recursion is often used humorously in computer science, philosophical, or mathematical texts. It is not uncommon for a textbook of these disciplines to include in its glossary an entry similar to this:

Recursivenesssee Recursiveness.

In the Google search engine, when searching for "recursion", the site suggests "Did you mean: recursion".

A computer joke goes like this: "The first thing to understand recursion is to understand recursion." In computer science, the choice of recursive acronyms is also common. PHP stands for PHP Hypertext Preprocessor, WINE stands for WINE Is Not an Emulator, and GNU stands for GNU's Not Unix (GNU is not Unix).