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

В большинстве языков программирования предусмотрены средства, позволяющие оформлять вспомогательный алгоритм как подпрограмму. Это бывает необходимо тогда, когда какой-либо алгоритм неоднократно повторяется в программе или имеется возможность использовать некоторые фрагменты уже разработанных ранее алгоритмов. Кроме того, подпрограммы применяются для разбиения крупных программ на отдельные смысловые части в соответствии с модульным принципом в программировании (считается хорошим тоном, если размер подпрограммы не превышает размера экрана).

Подпрограмма– это последовательность операторов, которые определены и записаны только в одном месте программы, однако их можно вызвать для выполнения из одной или нескольких точек программы. Каждая подпрограмма определяется уникальным именем.

Самое важное, что нужно усвоить: подпрограмма – это группа операторов, у которой есть имя. Подпрограммы используются в трех основных случаях:

1. Если операторы, составляющие тело подпрограммы, встречаются в программе много раз. Тогда имеет смысл создать для них отдельную подпрограмму. При этом произойдёт сокращение кода и, при необходимости, изменения надо будет вносить только в одно место.

2. Для организации кода, если несколько операторов программы выполняют какую-то конкретную задачу. При этом размер кода может и не уменьшится, но программа станет более читабельной.

3. Если подпрограмма может потребоваться в дальнейшем.

Формат определения функции:

[тип_возвращаемого_значения] имя_функции (список_параметров) {

описание данных

операторы

[returnвыражение;]

}

Рассмотрим, например, функцию, которая вычисляет сумму двух целых чисел:

int sum(int a, int b) {

int s;

s = a+b;

return s;

}

Определение функции – это ее полное описание, включающее тип возвращаемого значения, количество и типы самих параметров, и ее тело – тот код, который стоит внутри фигурных скобок после имени функции. Когда мы писали (создавали, а не вызывали) функции, мы выполняли именно определения функций.

В языке С всегда аргументы при вызове функции передаются по значению, т.е. в стеке выделяется место для формальных параметров функции и в это выделенное место при ее вызове заносятся значения фактических аргументов. Затем функция их использует и может изменять эти значения в стеке. Но при выходе из функции измененные значения теряются. Вызванная функция не может изменить значения переменных, указанных как фактические аргументы при обращении к данной функции.

void f(int k) { k = -k; } void main() {   int i = 1;   f(i);   printf("i = %d\n", i); // результат: i = 1 }

56. Рекурсивные функции.

В С функции могут вызывать сами себя. Функция является рекурсивной, если оператор в теле функции вызывает функцию, содержащую данный оператор. Иногда называемая круговым определением, рекурсия является процессом определения чего-либо с использованием самой себя.

Простым примером является функция factr(), вычисляющая факториал целого числа. Факториал числа N является произведением чисел от 1 до N. Например, факториал 3 равен 1*2*3 или 6. Как factr(), так и его итеративный эквивалент показаны ниже: /* Вычисление факториала числа */ int factr(int n) /* рекурсивно */ { int answer; if(n==1) return(1); answer = factr(n-1)*n; return(answer); } /* Вычисление факториала числа */ int fact (int n)    /* нерекурсивно */ { int t, answer; answer == 1; for(t=1; t<=n; t++) answer=answer*(t); return(answer); }

Действие нерекурсивной версии fact() должно быть совершенно очевидно. Она использует цикл, начиная с 1 и заканчивая указанным числом, последовательно перемножая каждое число на ранее полученное произведение.

Действие рекурсивной функции factr() немного более сложно. Когда factr() вызывается с аргументом 1, функция возвращает 1. В противном случае она возвращает произведение factr(n- 1) * n. Для вычисления этого значения factr() вызывается с n-1. Это происходит, пока n не станет равно 1.

При вычислении факториала числа 2, первый вызов factr() приводит ко второму вызову с аргументом 1. Данный вызов возвращает 1, после чего результат умножается на 2 (исходное значение n). Ответ, таким образом, будет 2. Можно попробовать вставить printf() в factr() для демонстрации уровней и промежуточных ответов каждого вызова.

Когда функция вызывает сама себя, в стеке выделяется место для новых локальных переменных и параметров. Код функции работает с данными переменными. Рекурсивный вызов не создает новую копию функции. Новыми являются только аргументы. Поскольку каждая рекурсивно вызванная функция завершает работу, то старые локальные переменные и параметры удаляются из стека и выполнение продолжается с точки, в которой было обращение внутри этой же функции. Рекурсивные функции вкладываются одна в другую как элементы подзорной трубы.

Рекурсивные версии большинства подпрограмм могут выполняться немного медленнее, чем их итеративные эквиваленты, поскольку к необходимым действиям добавляются вызовы функций. Но в большинстве случаев это не имеет значения. Много рекурсивных вызовов в функции может привести к переполнению стека. Поскольку местом для хранения параметров и локальных переменных функции является стек и каждый новый вызов создает новую копию переменных, пространство стека может исчерпаться. Если это произойдет, то возникнет ошибка - переполнение стека.

Основным преимуществом применения рекурсивных функций является использование их для более простого создания версии некоторых алгоритмов по сравнению с итеративными эквивалентами. Например, сортирующий алгоритм Quicksort достаточно трудно реализовать итеративным способом. Некоторые проблемы, особенно связанные с искусственным интеллектом, также используют рекурсивные алгоритмы. Наконец, некоторым людям кажется, что думать рекурсивно гораздо легче, чем итеративно.

При написании рекурсивных функций следует иметь оператор if, чтобы заставить функцию вернуться без рекурсивного вызова. Если это не сделать, то, однажды вызвав функцию, выйти из нее будет невозможно. Это наиболее типичная ошибка, связанная с написанием рекурсивных функций. Надо использовать при разработке функции printf() и getchar(), чтобы можно было узнать, что происходит, и прекратить выполнение в случае обнаружения ошибки.