Recursive functions

Introduction

Recursiveness is the property of notions to define themselves.
Exemples:
-the factorial of a number: N!=N⋅(N−1)! ;
-number powers: a^n=a⋅a^n−1 ;
-the term of an arithmetic progression: an=an−1+r ;
-Fibonacci's sequence: Fn=Fn−1+Fn−2 ;
Take notice that these rules don't always apply. If they did then, for 3! we would get: 3!=3⋅2! , 2!=2⋅1! , 1!=1⋅0! , 0!=0⋅(−1)! From here we can deduct 0!=0 and substituting in the above relations we obtain that n!=0 , for any natural number n . Of course, that's not right. In fact, the recursive formula for n! it only applies for n>0 , and by definition 0!=1 .
Therefore, we get the following definition for n! , now complete: n!=n⋅(n−1)!, n>0 Similarly, for all the formulas above there is at least one situation where the recursive formula can no longer be applied, and the result is determined directly. In C++, recursion is achieved through functions, which can call themselves. We remember that a function must be defined and then it can be called. Recursion consists in the fact that in the definition of a function appears the call itself. This call, which appears in the function definition itself, is called a self call. The first call, made in another function, is called the main call.

Solved problems

Problem 1
Write a recursive function that calculates and returns the difference between the sum of the elements on even positions and that of those on odd positions in a vector A received as a parameter together with n representing its number of elements. Array elements are indexed from 1. Example: If the function receives the array A={4,5,6,3,2,9} with n=6, then it will return 5, i.e. (5+3+9)-(4+6+2).

Solution

     
        int dif_poz(int A[], int n)
        {
            if(n==0) return 0;
            else if(n%2==0) return dif_poz(A,n-1)+A[n];
                 else return dif_poz(A,n-1)-A[n];
        }
    

Problem 2

Write a recursive function that receives as a parameter a natural number n and returns the number obtained from n by removing the odd digits.

                int stergimp(int n)
                {
                    if(n==0) return 0;
                    else if(n%2==1) return stergimp(n/10);
                         else return stergimp(n/10)*10+n%10;
                }
               

Solution
    #include < fstream>
        using namespace std;
        ifstream fin("i.in");
        ofstream fout("i.out");
        
        int X[21],Q[21],n,a,b,p,q;
        
        void afisare(int k)
        {
            for(int i=1;i<=k;i++)
                fout<=a && k<=b && pp>=p) afisare(k);
                        back(k+1,pp);
                    }
                    pp=pp-Q[X[k]];
                }
        }
        
        int main()
        {
            fin>>n>>a>>b>>p>>q;
            for(int i=1;i<=n;i++)
                fin>>Q[i];
            back(1,0);
            return 0;
        }

Practice exercises

1)A vector with n natural number elements (n<=100) is read. To replace each element of the vector with the sum of digits with the same parity as the index of the element. Indexing of elements starts from 1. Recursive functions will be written and used for:

    - reading the vector
   - vector display
   - calculating the sum of digits of a certain parity
   - the requested replacement
   Example: For the data below
   7
   223 435 6667 24 55 662 122
   The resulting string is
   3 4 7 6 10 14 1
        

2) A natural number n with at most 9 digits is read. Display the number of distinct digits of n. Only recursive subroutines will be used.

 Example:
          For n=38837, 3 is displayed (the distinct numbers are 3,7 and 8).

3) A natural number n (n<=20) is read. Display a drawing consisting of the character * as in the example below. Only recursive subroutines will be used. Example:

        For n=3 it is displayed
*
**
***
**
*
    

4) A natural number n is read. Let it be decomposed as the sum of increasing powers of 2. Only processing/calculations made with the help of recursively implemented functions will be used. Example: For n=84 it will display 4 16 64 (84 decomposes as 4+16+64)

5) a) Write a recursive function letter with two parameters s and c where s is a word and c is a letter s that returns how many times the letter c appears in the word s. b) Write a recursive function letters with three parameters s, n and c where s is a vector that stores at most 20 words, n is a natural number representing the number of words in the vector s, and c is a letter s that returns how many times it appears the letter c in total in the n words in the vector s (it will use the letter function). c) A number n and a vector s of n words are read. Using the letters function, determine and display the letters that appear a maximum number of times in the words in the vector s. Example: n=3, s={"ana", "are", "apples"} => a e