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

Функцию f можно определить следующим образом:

f(1, n) = 1 для всех n;

f(m, 1) = 1 для всех m;

f(m, n) = f(m, m), если m<n;

f(m, m) = 1 + f(m, m-1);

f(m, n) =  f(m, n-1) + f(m-n, n), если m > n.

Из этого определения следует рекурсивное определение функции:

int f (int m, int n) {if ((m==1) || (n==1))    f=1;             else if (m <=n)   f=1+f(m, m-1);                                     else f =  f(m, n-1) + f(m-n, n); }

А теперь посмотрим на последовательность вызовов, к которым приводит вызов f(6,4). Они представлены на схеме:

                                                    f(6,4)

f(6,3)                                                                                     f(2,4)

f(6,2)              f(3,3)                                                                         f(2,3)

f(6,1)     f(4,2)              f(3,2)                                                                         f(2,2)

f(4,1)   f(2,2)               f(3,1)   f(1,2)                                                              f(2,1)

f(2,1)

Число вызовов велико, и некоторые из них повторяются (f(2,1) и f(2,2)). Для больших m и n число повторяющихся вызовов значительно возрастает. В итоге выполнение алгоритма может быть неэффективным. Поэтому в тех случаях, когда существует простой итерационный алгоритм, применять рекурсию не следует.

Условия «правильного» рекурсивного определения:

§   множество определяемых объектов частично упорядочено;

§  каждая убывающая по этому упорядочению последовательность элементов заканчивается некоторым минимальным элементом;

§  минимальные элементы определяются нерекурсивно; характерное свойство описания рекурсивной функции состоит в том, что в ней должна содержаться проверка значений аргументов для принятия решения о завершении функции;

§  неминимальные элементы определяются с помощью элементов, которые меньше их по этому упорядочению.

Правила оформления и вызова функций

·  в виде функции можно оформить любую (не обязательно повторяющуюся), логически завершенную часть программы;

·  перед функцией main() записывается прототип (объявление, заголовок) функции; ключевое слово void перед именем функции означает, что функция не возвращает результата. Далее следует имя функции, которое записывается по обычным правилам записи идентификаторов. Пустые круглые скобки после имени функции означают, что функция не имеет никаких параметров, ни входных, ни выходных (результатов). При этом слово void в круглых скобках (но не в начале!!!) можно не писать. После прототипа обязательно записывается символ «;», а при описании функции этот символ не пишем.

·  в прототипе функции и при ее определении в заголовке обязательно надо записывать типы параметров, даже если они повторяются (в отличие от объявления переменных);

нельзя писать: void LINE (int Len, y, char ch)  //ошибка надо писать: void LINE (int Len, int y, char ch) при этом имена параметров обязательны только в заголовке описания, а в прототипе можно указать только их типы: void LINE(int , int, char).

·  определение функции размещаем после текста функции main(); повторяем заголовок, но без точки с запятой в конце; при необходимости внутри функции объявляются локальные переменные, предназначенные для хранения промежуточных величин;

·  в функции определяется своеобразный шаблон вычислений с формальными параметрами;

·  фактические параметры (аргументы) – это приказ «проработать» тело функции для данных значений;

·  соответствие формальных параметров и аргументов должно выполняться по количеству, порядку следования и типу;

·  вызов функции осуществляется отдельным оператоом вызова;

·  для вызова функции типа void достаточно записать имя функции и в скобках, если есть, параметры:  LINE(i, j, ch).