Функции. Основные принципы структурной методологии. Принцип формальности. Принцип иерархического упорядочивания, страница 24

#include <iostream.h>

#include <stdio.h>

#include <conio.h>;

main ()

{ void printd (int); int a=12345;

printd(a) ;

cout <<  endl ;

getch();

return 0 ;

}

void printd (int n) {         

if  (n < 0)

{putchar (‘-‘);

n=-n;

}                                                           if ( n)

{printd (n/10);                      //действия выполняются на рекурсивном возврате

putchar (n%10 +’0’);

} }

Пример 5. Вычисление НОД через итерации и через рекурсивную функцию

#include <iostream.h>

#include <conio.h>

main ()

{ int  NOD_iter (int, int);

   int  NOD_rec (int,  int);   int m=32, n=16;   cout << m <<”  ” << n << “   ”  <<  NOD_iter ( m, n) << endl ;

cout << m <<”  ” << n << “   ”  <<  NOD_rec ( m, n) << endl ;

getch();

return 0 ;

}

int  NOD_iter (int m, int n) { int r;

do             {r= m % n;

m=n;

n=r;

}  while (r);   return m; }

int  NOD_rec (int m,  int n) {     if (!(m % n))  return n;             //действия выполняются на рекурсивном спуске      else  return NOD_rec(n, m %n);

}

Пример 6. Рекурсивная функция вычисления суммы элементов числовой последовательности

#include <iostream.h>

#include <conio.h>

#include <iomanip.h>

main ()

{ double sum (int [],  int);   const int con =5;   int array[con]= {1, 2, 3, 4, 5};

for (int i=0; i<con; i++}

cout << setw(3) << array[i];

cout <<endl; cout << sum (array, con) << endl ;

getch();

return 0 ;

}

double sum (int s[], int n) {             if (n==1) return s[0];

else return sum(s, n-1) + s[n-1];   //действия выполняются на рекурсивном возврате }

Пример 7. Рекурсивная функция вычисления чисел Фибоначчи

#include <iostream.h>

#include <conio.h>

#include <iomanip.h>

unsigned long fib (unsigned long);

void main ()

{ unsigned long result, number;    cout << “ Input number:” << endl;

cin >> number;    cout << “Fib number (” << number << “) = “ << fib(number) << endl ;

getch();

return 0 ;

}

unsigned long fib (unsigned long n)

{             if (n==0 || n==1) return n;

else return  fib(n-1)+fib(n-2); //действия выполняются на рекурсивном возврате }

Виды рекурсий

Существуют два вида рекурсий. Прямая рекурсия – функция содержит вызовы самой себя. Косвенная рекурсия – функция обращается к себе через вызов в другой подпрограмме – кольцо. Глубина рекурсии вызова функции – максимальное количество незаконченных вызовов. Текущий уровень рекурсии – число рекурсивных вызовов в данный момент времени. Общее количество вызовов – количество вызовов всего, порожденных вызовом рекурсивной функции. Следует учитывать одну особенность, характерную для рекурсивных программ. Например, как было вычислено, для нахождения n-го числа Фибоначчи количество рекурсивных вызовов будет порядка 2n. Это называется экспоненциальной сложностью. Поэтому при написании программ рекурсию используйте, только убедившись, что она не вызовет очень большое число рекурсивных вызовов.

Особенности использования рекурсивных функций

Хотя рекурсивные функции очень часто позволяют решать определенные задачи элегантными способами, они не всегда эффективны, а иногда могут быть совсем неэффективны по сравнению с итеративными алгоритмами. Для иллюстрации этого рассмотрим следующую задачу: вычислить число способов, которыми натуральное число  N  может быть представлено как сумма натуральных чисел (суммы, отличающиеся порядком чисел, например, 4+1 и 1+4, следует учитывать только один раз). Если N=5, то имеется 7 способов:

5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1.

Решение этой задачи может быть выражено в виде функции f, такой, что f(m, n) есть число способов, которыми m может быть представлено суммой слагаемых, каждое из которых не больше n. Если можно определить функции f, то искомое число вычисляется как f(N, N).