C++. Recursion. Examples of tasks solving. Advantages and disadvantages of recursion

Recursion. Examples of tasks solving. Advantages and disadvantages of recursion

Search other websites:

1. What is recursion? What is called recursion?

Any function (method) in its body can call itself. Recursion is a way to define a function in which the result of a return from a function for a given argument value is determined based on the result of returning from the same function for the previous (smaller or larger) argument value.

If a function (method) calls itself, then such a call is called a recursive function call. With each recursive call, the previous values of internal local variables and the obtained function parameters are saved. In order for the next step of the recursive call to differ from the previous one, the value of at least one of the parameters of the function must be changed. The recursive function call process stops when the variable parameter reaches a certain final value, for example, the last item in the array is processed.

⇑

2. Explanations for the implementation of tasks on recursion. How to organize a recursive function call?

A recursive function call can be made if the algorithm is defined recursively. In order to convert a cyclic process into a recursive process, you need to be able to identify three important points:

the condition of the termination of the sequence of recursive function calls. For example, if a counter or an iterator with the name k changes from 1 to 10 in ascending order, then the termination condition is the achievement of the value k = 10. The termination condition is specified in the return statement;
the formula of the next element or iterator that is used in the recursive process. This formula is specified in the return statement;
list of parameters that are passed to the recursive function. One of the parameters is necessarily an iterator (counter) that changes its value. Other parameters are optional, for example, a reference to the array on which processing is performed.

⇑

3. Search for the sum of array items. Example

For this example, you can create your own recursive functions that define any sums of the items of any arrays.

Task. An array of numbers A is given. Develop a recursive function that calculates the sum of the items of an array:

S = A[0] + A[1] + … + A[n],

here n – the number of items in the array. The program code of the function is as follows:

// sum of array items
int Sum(int i, int A[], int n)
{
    if (i==n-1)
        return A[i];
    else
        return A[i]+Sum(i+1,A,n);
}

As you can see from the example, 3 parameters are passed to the recursive function Sum():

the current value of the iterator i;
the array A;
number of array items n.

The exit from the function is performed if the last element of the array is processed. The condition for terminating a recursive process is:

if (i==n-1)
    return A[i];

To summarize the current value of A[i] with next value the following line is indicated:

return A[i]+Sum(i+1,A,n);

here the recursive call Sum(i+1, A, n) means the next value of array A. The parameter i+1 indicates that at the next level of the call to the recursive function, the next item after the given item of the array will be taken.

Using the Sum() function in other program code can be, for example, like this:

int A[] = { 5, 7, 2, -1 };
int n = 4;
int sum;
sum = Sum(0,A,n); // sum = 13

⇑

4. Example of counting the number of occurrences of a given character in a string

In this example, the recursive Count() function is implemented, which determines the number of occurrences of a given character c in the string s. Function receives 3 parameters:

the character c to be compared with each character of the string s;
the string s;
additional variable i, which is the counter of the recursive cycle.

The implementation of the Count() function is as follows:

// counting of c character in string s
int Count(char c, string s, int i)
{
    if (i==s.length()) // end condition of the recursive process - the entire string is processed
        return 0;
    else
    {
        if (c == s[i]) // if the symbol is found
            return Count(c,s,i+1)+1; // increase the number of characters found by 1
        else
            return Count(c,s,i+1); // otherwise, proceed to processing the next character
    }
}

⇑

5. An example of calculating the factorial of a number – n!

The calculation of the factorial of the number by the recursion method is in almost every textbook. The factorial of the number is calculated by the formula

f = 1 · 2 · … · (n-1) · n

here n>=1.

A recursive call can be organized in two ways:

in ascending order 1, 2, …, n;
in descending order n, n-1, …, 2, 1.

In this example, two functions are developed that find factorial in both ways. The program code of functions is as follows:

// factorial calculation - method 1
int Fact1(int n, int i)
{
    if (i==n)
        return n; // termination condition of the recursive process
    else
        return i*Fact1(n, i+1); // transition to the next number i + 1
}

// factorial calculation - method 2
int Fact2(int n)
{
    if (n==1)
        return 1; // termination condition of the recursive process
    else
        return n*Fact2(n-1); // transition to the next number n-1
}

The first function Fact1() accepts 2 parameters. The first parameter specifies the maximum possible value of n, which can be multiplied. The second parameter determines the current value of i which is multiplied.

In the second function Fact2(), one parameter is passed — the maximum possible value of n, which takes part in recursive multiplication. The second parameter is not necessary here, since the condition for terminating the recursive process is known and is equal to 1. In the function Fact2(), the recursive process ends when n = 1.

The use of functions in other program code may be as follows:

int f;

// the use of function Fact1()
f = Fact1(5,1); // f = 5! = 120
f = Fact1(7,1); // f = 7! = 5040
f = Fact1(2,1); // f = 2! = 2

// the use of function Fact2()
f = Fact2(5); // f = 5! = 120
f = Fact2(8); // f = 8! = 40320

⇑

6. The program for calculating the greatest common divisor (Euclidean algorithm). Example

In the example, the greatest common divisor is determined by the Euclidean formula:

The program code of the function is as follows:

// the greatest common divisor of the Euclidean algorithm
int MaxDiv(int n, int m)
{
    if (n==m)
        return n;
    else
    if (n>m)
        return MaxDiv(n-m, m);
    else
        return MaxDiv(n, m-n);
}

The use of the MaxDiv() function can be as follows:

int md;
md = MaxDiv(8, 3); // md = 1
md = MaxDiv(24, 96); // md = 24
md = MaxDiv(9, 15); // md = 3

⇑

7. Counting the number of elements in an array greater than a given number. Example

The Count() method is shown, which returns the number of items larger than the specified number num. Four parameters are passed to the method:

the num number to compare with each item of the array;
array of numbers A[ ];
the number of items n in the array;
the current value of the counter in the array.

// counting the number of elements in an array greater than a given number
int Count(double num, double A[], int n, int i)
{
    if (i==n)
        return 0; // termination condition of the recursive process
    else
    {
        if (num<A[i])
            return Count(num, A, n, i+1) + 1; // add 1 to the result and continue
        else
            return Count(num, A, n, i+1); // go to the next item of the array
    }
}

Using the Count() method in another method

double A[] = { 2.8, 3.5, 1.9, 2.2, 3.6 };
int k;
k = Count(2.3, A, 5, 0); // k = 3
k = Count(0.9, A, 5, 0); // k = 5

⇑

8. The advantages and disadvantages of using recursion in programs

Recursion is often compared with iteration. The organization of a cyclic process using recursion has its advantages and disadvantages.

The following interrelated advantages of recursion can be distinguished:

the naturalness of the presentation of seemingly complex algorithms;
recursive algorithm is more readable in comparison with iterative;
for many common tasks, recursion is easier to implement than iteration. Recursion is well suited for implementing list traversal algorithms, trees, expression parsers, combinatorial tasks etc.

The disadvantages of recursion are as follows:

compared to iteration, the reusable call of recursive function takes more time. This is due to the fact that when the recursive method is called, its parameters are copied to the stack. When the call to the recursive function is completed, the previous values of the parameters are pulled out of the stack, which leads to unnecessary operations. The iteration algorithm for the same task is faster;
if the recursive function contains large amounts of local internal variables and a large number of parameters, the use of recursion is not effective. This is due to the fact that for each recursive call you need to make copies of these variables and parameters. With a large number of recursive calls, this will lead to excessive memory usage.

⇑

BestProg