Рекурсивни функции

Един обект е рекурсивен, ако частично се съдържа в сеже си или е дефиниран с помощта на себе си.

C/C++ поддържа две езикови конструкции, които позволяват да се реализират рекурсивни алгоритми - рекурсивни функции и структори с рекурсия.

Функция, която се обръща пряко или косвено към себе си , се нарича рекурсивна.

При всяко рекурсивно обръщение в програмния стек се разпределя памет за параметрите и вътрешните променливи. Използването на рекурсия води до увеличване производителността на програмисткия труд ( обикновено рекурсивните алгоритми са по-кратки ).

Но рекурсията не води до ефиктивни програми, защото при нея се използва повече памет и е необходимо повече време за изпълнение на програмата.

За да бъде една функция рекурсия, то трябва тя да бъде дефинирана рекурсивна.

Пример за нерекурсивна функция пресмятащата n! .

        long fact ( int n)
        {
                int i;
                long f = 1;
                
                for ( i = 2; i<=n; i++ )
                        f = f * i;
                
                return f;
        }

Пример за рекурсивна функция пресмящата n! :

        long fact( int n )
        {
                if ( n == 0 ) 
                        return 1;
                
                else 
                        return ( n * fact( n - 1 ) );
        }

Note

При ползване на рекурсия има възможност за безброй много рекурсивни обръщения.

За това е необходимо да има 1 или няколко "прости" случаи ( без рекурсивно обръщение ) и 1 или няколко случая с рекурсивни обръщения.

Да се състави програма, в която чрез рекусивна функция се определя НОД на две цели неотрицателни числа, които не са едновременнно равни на 0.

За пресмятане ще използваме следната рекурсивна дефиниция:

НОД ( m, n ) =

1. m, ако n = 0
2. НОД ( n, m ), ако n > m
3. НОД ( n, m % n ) в останалите случаи

Код:

        #include <iostream.h>
        
        int nod ( int m, int n)
        {
                int result;
                
                if ( n == 0 )
                        result = m;
                else if ( n > m ) 
                        result = nod ( n, m ) ;
                else 
                        result = nod ( n, m % n);
                
                return result;
        }
        
        void main()
        {
                int m, n;
                
                do{
                        cout<<" m= ";
                        cin>> m;
                        cout<<"n = ";
                        cin>> n;
                } while ( m < 0 || n < 0 || ( m == 0 && n == 0 ) );
                
                cout<<"\n НОД = "<< nod ( m, n ) << endl;
        }