Analysis of algorithms and data structures, their order, their typology and their implementation in different languages

It is said that something is recursive if it is defined in terms of itself or itself. It is also said that the same word should never be included in the definition of this one. The fact is that recursive definitions appear frequently in mathematics, and even in real life. An example: just point a camera at the monitor that shows the image that that camera shows. The effect is truly curious, especially when you move the camera around the monitor.
ऐसा कहा जाता है कि कुछ पुनरावर्ती है अगर इसे खुद या स्वयं के संदर्भ में परिभाषित किया जाता है यह भी कहा जाता है कि एक ही शब्द को कभी भी इस एक की परिभाषा में शामिल नहीं किया जाना चाहिए। तथ्य यह है कि पुनरावर्ती परिभाषाएं गणित में अक्सर दिखाई देती हैं, और यहां तक कि वास्तविक जीवन में भी। एक उदाहरण: सिर्फ उस कैमरे को मॉनिटर पर इंगित करें जो छवि को दिखाता है जो कि कैमरा दिखाता है प्रभाव वास्तव में उत्सुक है, खासकर जब आप मॉनिटर के चारों ओर कैमरे को ले जाते हैं.

In mathematics, we have multiple recursive definitions:

– Natural numbers:

(1) 1 is natural number.
(2) the next number of a natural number is a natural number

– The factorial: n !, of a natural number (including 0):

(1) if n = 0 then: 0! = 1
(2) if n> 0 then: n! = n · (n-1)!

Also, a program can be defined in recursive terms, such as a series of basic steps, or base step (also known as a stop condition), and a recursive step, where the program is called again. On a computer, this series of recursive steps must be finite, ending with a base step. That is to say, at each recursive step, the number of steps that must be taken to finish is reduced, reaching a moment in which the condition of passage to recursion is not verified. Neither the base step nor the recursive step are necessarily unique.
इसके अलावा, एक प्रोग्राम को पुनरावर्ती शब्दों में परिभाषित किया जा सकता है, जैसे कि बुनियादी चरणों की श्रृंखला, या आधार चरण (जिसे स्टॉप स्थिति के रूप में भी जाना जाता है), और पुनरावर्ती कदम, जहां कार्यक्रम को फिर से बुलाया जाता है किसी कंप्यूटर पर, पुनरावर्ती चरणों की इस श्रृंखला को एक आधार चरण के साथ समाप्त होना चाहिए। यह कहने के लिए, प्रत्येक पुनरावर्ती चरण में, समाप्त करने के लिए किए जाने वाले चरणों की संख्या कम हो जाती है, जिसमें एक क्षण तक पहुंच होती है जिसमें पुनरावृत्ति के मार्ग की स्थिति सत्यापित नहीं होती है। न तो आधार कदम और न ही पुनरावर्ती कदम अनिवार्य रूप से अद्वितीय हैं

On the other hand, recursion can also be indirect, if we have a procedure P that calls another Q and this in turn calls P. Also in these cases there must be a stop condition.

There are certain structures whose definition is recursive, such as trees, and algorithms that use trees are usually recursive.

An example of a recursive program in C, the factorial:

int factorial (int n)
{
if (n == 0) return 1;
return n * factorial (n-1);
}
As it is observed, in each recursive call the value of n is reduced, arriving the case in which n is 0 and does not make more recursive calls. It should be noted that the factorial can be obtained easily without recursive functions, in fact, the use of the previous program is very inefficient, but it is a very clear example.

Below is an example of a program that uses indirect recursion, and tells us if a number is even or odd. Like the previous program, there is another much simpler method of determining if a number is even or odd, just determine the rest of the division between two. For example: if we do par (2) it returns 1 (true). If we do odd (4) it returns 0 (false).

/ * declaration of functions, to avoid errors * /

int pair (int n);

int odd (int n);

int pair (int n)
{
if (n == 0) return 1;
odd return (n-1);
}

int odd (int n)
{
if (n == 0) return 0;
return pair (n-1);
}
In Pascal, this is done (notice the use of forward):

odd function (n: Integer): Boolean; forward;
function pair (n: Integer): Boolean; forward;

function pair (n: Integer): Boolean;
begin
if n = 0 then par: = true
else pair: = odd (n-1)
end;

odd function (n: Integer): Boolean;
begin
if n = 0 then odd: = false
else odd: = pair (n-1)
end;

Example: if we make the odd call (3) it makes the following calls:
pair (2)
odd (1)
pair (0) -> returns 1 (true)

Therefore 3 is an odd number.

What happens if a recursive call is made that does not end?

Each recursive call stores the parameters that were passed to the procedure, and other variables necessary for the correct operation of the program. Therefore if an infinite recursive call occurs, that is, it never ends, there will come a time when there will be no memory left to store more data, and at that moment the execution of the program will be aborted. To test this you can try to make this call in the factorial program defined above:

factorial (-1);

Of course you do not have to pass parameters to a function that are outside your domain, since the factorial is defined only for natural numbers, but it is a clear example.

When to use the recursion?

To begin with, some programming languages ​​do not support the use of recursion, such as the assembler or FORTRAN. It is obvious that in this case a non-recursive (iterative) solution will be required. Nor should it be used when the iterative solution is clear to the naked eye. However, in other cases, obtaining an iterative solution is much more complicated than a recursive solution, and that is when you can ask whether it is worth transforming the recursive solution into another iterative one. Subsequently, it will explain how to eliminate the recursion, and it is based on storing in a stack the values ​​of the local variables that exist for a procedure in each recursive call. This reduces the clarity of the program. Even so, we must consider that the compiler will transform the recursive solution into an iterative one, using a stack, for when compiling the computer code.
On the other hand, almost all the algorithms based on the schemes of return back and divide and conquer are recursive, because somehow a recursive solution seems much more natural.

Oddly enough, it is generally much easier to write a recursive program than its iterative equivalent. If the reader does not believe it, it may be because he does not yet master recursion. Various examples of recursive programs of diverse complexity will be proposed to get used to the recursion.

Exercise

The famous Fibonacci succession can be defined in terms of recurrence as follows:

(1) Fib (1) = 1; Fib (0) = 0
(2) Fib (n) = Fib (n-1) + Fib (n-2) if n> = 2

How many recursive calls are produced for Fib (6)? Encode a program that calculates Fib (n) iteratively.
Note: do not use data structures, since we do not want to store the Fibonacci numbers before n; yes auxiliary variables are allowed.

Examples of recursive programs

– Given two numbers a (integer) and b (natural number greater than or equal to zero) determine a ^ b.

int power (int a, int b)
{
if (b == 0) return 1;
else return to * power (a, b-1);
}
The stop condition is met when the exponent is zero. For example, the power evaluation (-2, 3) is:
power (-2, 3) ->
(-2) · power (-2, 2) ->
(-2) · (-2) · power (-2, 1) ->
(-2) · (-2) · (-2) · power (-2, 0) ->
(-2) · (-2) · (-2) · 1

and the return of the recursion is:

(-2) · (-2) · (-2) · 1 / = / (-2) · (-2) · (-2) · power (-2.0)
<(-2) · (-2) · (-2) / = / (-2) · (-2) · power (-2, 1)
<(-2) · 4 / = / (-2) · power (-2.2)
<-8 / = / power (-2.3) in bold, the part of the expression that is evaluated in each recursive call has been highlighted.   – Given an array consisting of integers and containing N elements with N> = 1, return the sum of all the elements.

int sumarray (int numbers [], int position, int N)
{
if (position == N-1) return numbers [position];
else return numbers [position] + sumarray (numbers, position + 1, N);
}
…

int numbers [5] = {2,0, -1,1,3};
int N = 5;
printf (“% d \ n”, sumarray (numbers, 0, N));
Note that the stop condition is met when the end of the array is reached. Another alternative is to traverse the array from the end to the beginning (from right to left):

int sumarray (int numbers [], int position)
{
if (position == 0) return numbers [position];
else return numbers [position] + sumarray (numbers, position-1);
}
…

int numbers [5] = {2,0, -1,1,3};
int N = 5;
printf (“% d \ n”, sumarray (numbers, N-1));

– Given an array consisting of integers, return the sum of all the elements. In this case the number of elements is unknown. In any case, it is guaranteed that the last element of the array is -1, a number that will not appear in any other position.

int sumarray (int numbers [], int position)
{
if (numbers [position] == -1) return 0;
else return numbers [position] + sumarray (numbers, position + 1);
}
…

int numbers [5] = {2,4,1, -3, -1};
printf (“% d \ n”, sumarray (numbers, 0));

The reason why this example is included is due to the fact that, in general, the number of elements of the data structure that is being worked on will not be known. In this case, a sentinel is introduced – such as the constant -1 of this example or the NULL constant for pointers, or other values ​​such as the largest or smallest integer that the machine can represent – to indicate the end of the structure.

– Given an array consisting of integers and containing N elements with N> = 1, return the largest element.

int major (int numbers [], int position)
{
int aux;
if (position == 0)
return numbers [position];
else {
aux = greater (numbers, position-1);
if (numbers [position]> aux)
return numbers [position];
else
return aux;
}
}
…
int numbers [5] = {2,4,1, -3, -1};
int N = 5;
printf (“% d \ n”, major (numbers, 4));

– Now a little more complicated: given two arrays of integers A and B of length n and m respectively, where n> = m, determine if B is contained in A. Example:
A = {2,3,4,5,6,7, -3}
B = {7, -3} -> content; B = {5,7} -> not contained; B = {3,2} -> no content

To solve it, we start from the first element of A and compare from there with all the elements of B until we reach the end of B or find a difference.
A = {2,3,4,5}, B = {3,4}
–
2,3,4,5
3,4
^
In the case of finding a difference, it moves to the second element of A and so on until it is shown that B is equal to a subarray of A or that B has a length greater than the subarray of A.3,4,5
3,4
Seen graphically, it consists of sliding B along A and checking that at some position B it supposes on A.
Two functions have been written to solve it, content and esSubarray. The first returns true if subarray A and array B are equal; It has two stop conditions: either that it has traveled full B or that two elements do not coincide. The second function is the main one, and its task is to ‘slide’ B along A, and in each recursive step to call the content function once; has two stop conditions: that array B is greater than sub-array A or that B is contained in a sub-array A.

int content (int A [], int B [], int m, int pos, int desp)
{
if (pos == m) return 1;
else if (A [desp + pos] == B [pos])
return content (A, B, m, pos + 1, desp);
else
return 0;
}

int is Subarray (int A [], int B [], int n, int m, int desp)
{
if (desp + m> n)
return 0;
else if (content (A, B, m, 0, desp))
return 1;
else
return is Subarray (A, B, n, m, desp + 1);
}
…
int A [4] = {2, 3, 4, 5};
int B [3] = {3, 4, 5};
if (esSubarray (A, B, 4, 5, 0)) printf (“\ nB is contained in A”);
else printf (“\ nB is not contained in A”);
It should be noted that the requirement n> = m indicating in the statement is unnecessary, if m> n then it will return false as soon as it enters the execution of esSubarray.

This algorithm allows to search for words in texts. However, there are better algorithms such as Knuth-Morris-Prat, Rabin-Karp or finite automata; These algorithms are more complicated but much more effective.

– Given an array consisting of integers and containing N elements with N> = 1, return the largest element. In this case write a procedure, that is, that the largest element returned is a variable that is passed by reference.

greater void (int numbers [], int position, int * m)
{
if (position == 0)
* m = numbers [position];
else {
major (numbers, position-1, m);
if (numbers [position]> * m)
* m = numbers [position];
}
}
…
int numbers [5] = {2,4,1, -3, -1};
int M;
major (numbers, 5-1, & M);
printf (“% d \ n”, M);

You have to be careful with two very common mistakes: the first is to declare the variable so that it passes by value and not by reference, with which nothing is obtained. The other error is to call the function by passing a constant instead of the parameter by reference, for example: greater (numbers, 5-1, 0); In this case, a compilation error will also occur.

– The function of Ackermann, being n and m natural numbers, is defined as follows:

Ackermann (0, n) = n + 1
Ackermann (m, 0) = A (m-1, 1)
Ackermann (m, n) = A (m-1, A (m, n-1))

Oddly enough, you always get to the base case and the function ends. Try to execute this function with different values ​​of n and m … that are not very large! On the Internet you can find some curious things about this function and its applications.

Proposed exercises

Note: to solve the exercises, it is enough to make a single tour of the array. Neither an auxiliary array should be used, but variables of type integer or boolean can be used.

– Given an array consisting of integers and containing N elements with N> = 1, write a function that returns the sum of all the elements greater than the last element of the array.

– Given an array consisting of integers and containing N elements with N> = 1, write a function that returns true if the sum of the first half of the integers of the array equals the sum of the second half of the integers of the array. array

– Given two arrays A and B of length n and m respectively, n> = m whose elements are ordered and not repeated, determine if all the elements of B are contained in A. Remember that the elements are ordered, in this way it is enough to make a single tour over each array.

Conclusions

In this section we have tried to show that recursion is a powerful tool to solve multiple problems. Moreover, any iterative program can be done using recursive expressions and vice versa.

Beautiful love Massage for Your Love One
Richard Cory EA Robinson
La violencia sexual en el vecindario daña la salud mental en las mujeres