return 1; // выход из рекурсии – терминальная ветвь
else return n * factorial(n-1);
}
При n = 5 эта функция будет работать следующим образом:
factorial := 5 * factorial(4)
В данном случае реализована так называемая нисходящая рекурсия: вызов factorial(5) означает, что функция factorial вызывает себя раз за разом: factorial(4), factorial(3), … до тех пор, пока не будет достигнута терминальная ситуация – ситуация окончания рекурсии. При каждом вызове текущие вычисления откладываются, локальные переменные и адрес возврата остаются в стеке. Терминальная ситуация factorial = 1 достигается при n = 1. При этом рекурсивный спуск заканчивается, начинается рекурсивный возврат изо всех вызванных в данный момент копий функции: начинает строиться ответ n*factorial(n-1). Сохраненные локальные параметры выбираются из стека в обратной последовательности, а получаемые промежуточные результаты: 1*1, 2*1, 3*2*1, 4*3*2*1, 5*4*3*2*1 – передаются вызывающим функциям.
Рекурсивная функция, вычисляющая n-й член ряда Фибоначчи, может иметь вид:
{
if ((n == 1) || (n == 2))
return 1; // выход из рекурсии
else return fibo(n-2) + fibo(n-1);
}
Примеры:
1. Составить функцию, рекурсивно определяющую значение биномиального коэффициента при 0<m<n по формулам:
= = 1, = +
{
if ((m == 0) || (m == n))
return 1; // выход из рекурсии
else return binom(m, n-1) + binom(m-1, n-1);
}
2. Составить функцию, рекурсивно определяющую максимальный элемент в заданной части целочисленного массива vectorn , начиная с k-го и до n-го элемента:
int max_element(int k, int n, int vector[])
{
if (k == n-1)
return a[n-1]
{
temp = max_element(k+1, n, vector[]);
if (a[k] > temp)
return a[k];
}
}
3. Составить функцию, реализующую рекурсивный алгоритм К.Хоара быстрой сортировки массива vectorn. Сравниваются элементы vectori и vectorj , причем i=1, j=n-1. Если vectori< vectorj , то эти элементы уже отсортированы по возрастанию, поэтому значение правого индекса уменьшается на единицу, и алгоритм повторяется. Если vectori> vectorj , то они меняются местами, останавливается правый индекс, и начинает увеличиваться левый. Обмен значениями с изменением направления движения после каждого обмена продолжается до тех пор, пока левый и правый индексы не встретятся друг с другом: i = j. В этом случае элемент vectori будет стоять на своем месте в массиве: слева от него стоят элементы меньше его, а справа – больше. После этого алгоритм рекурсивно повторяется для левой и правой частей массива:
void quick_sort(int left, int right, int vector[])
{
if (left >= right) // в векторе меньше двух элементов
swap(left, (left + right)/2, vector);
last= left;
for (i=left+1; i<=right; i++)
if (vector[i]<vector[left])
swap(++last, i, vector);
quick_sort(last+1, right, vector);
}
Операцию перестановки i-го и j-го элементов массива можно оформить функцией:
void swap(int i, int j, int vector[])
{
temp=vector[i];
vector[i]=vector[j];
vector[j]=temp;
}
Особенности рекурсии:
· использование рекурсивной формы организации алгоритма выглядит изящнее итерационной и дает более компактный текст программы,
· недостатки рекурсии состоят в следующем:
1. если глубина рекурсии велика, то программа будет требовать во время исполнения много памяти, что может привести к переполнению стека,
2. рекурсивные алгоритмы, как правило, выполняются более медленно,
· при рекурсивном программировании велика вероятность ошибок, вынуждающих программиста к перезагрузке компьютера.
Таким образом, если у программиста есть возможность выбора между итерацией и рекурсией, то предпочтительным выбором является итерация.
Между объектами реального мира, которые моделируются на компьютерах, существуют разнообразные, постоянно меняющиеся связи. Эти связи, как и сами объекты, могут появляться и исчезать. Поэтому если мы хотим описать в программе группу с переменным числом объектов, связи между которыми тоже подвержены изменениям, нужны соответствующие структуры. Эти структуры должны позволять устанавливать, изменять и разрывать связи между моделируемыми объектами, а также порождать или уничтожать сами объекты.
Для этой цели в Си используются указатели и динамические структуры.
До сих пор мы рассматривали только статические структуры. Этим термином обозначаются структуры данных (массивы, файлы, структуры), которые возникают непосредственно перед выполнением программы в соответствии со своим описанием, существуют в течение всего времени ее выполнения, и размер которых задается заранее с помощью описания их типов и не изменяется в ходе выполнения программы.
Однако при решении многих задач мы заранее, то есть на этапе написания программы, не знаем не только размера того или иного программного объекта (структуры данных), но и даже того, будет ли вообще нужен этот объект. Такого рода программные объекты или структуры данных, возникающие уже в процессе выполнения программы по мере необходимости, размер которых определяется или изменяется при ее выполнении, называются динамическими объектами или структурами.
Язык Си отличается от других языков программирования, прежде всего широким использованием указателей. Именно наличие в нем указателей сделало его очень удобным для системного программирования.
Под указателем (ссылкой) понимается переменная, содержащая адрес (номер) ячейки памяти, в которой хранится значение любого программного объекта – переменной, элемента массива, функции, структуры.
Оперативная память компьютера – это последовательность байтов, каждый из которых имеет номер (адрес). Адреса байтов памяти идут по возрастанию: если к – это номер текущего байта, то к-1 – номер предыдущего, а к+1 – последующего байтов. Указатель как раз и содержит адрес некоторого байта памяти. Меняя значение указателя, можно перемещаться по памяти, адресуясь к различным данным, записанным в просматриваемых ячейках.
Таким образом, в Си под указателем понимается переменная, содержащая адрес любого объекта программы. Значит, указатель говорит о том, где в памяти размещен тот или иной программный объект (переменная, массив, структура, функция), но ничего не говорит об имени и значении этого объекта. По аналогии – можно знать почтовый адрес человека, но этот адрес не дает нам информацию о количестве комнат в его квартире и ее обстановке.
Применение указателей полезно:
- при работе с массивами – обеспечивается использование сразу всех элементов массива,
- при обращении к функциям – можно одновременно возвратить сразу несколько значений, вычисляемых функцией,
- при работе с файлами – обеспечивается быстрый доступ к компонентам файла,
- при создании новых переменных в процессе выполнения программы – можно динамически выделять память для них.
Для работы с указателями в Си используются две операции:
* - доступ по адресу (обращение по адресу),
& - получение адреса.
Знак * , стоящий перед именем переменной-указателя, означает «взять (записать) значение по данному адресу»: *ptr – записать значение по адресу ptr.
Знак & , стоящий перед именем обычной переменной, означает «получить адрес переменной»: &x – получить адрес переменной x..
Перед использованием в программе указатели, как и любые другие переменные, должны быть описаны – задан тип объекта, адрес которого будет хранить указатель, поставлена звездочка * и задано имя указателя:
int i, j, *ptr;
float x, y, *ukaz;
char c, d, *adr;
Описаны указатели:
рtr – на любой объект (переменную, массив, функцию) целого типа,
ukaz – на любой объект вещественного типа,
adr – на любой объект символьного типа.
После описания указателей им можно присвоить значения адресов переменных этого же типа, используя операцию получения адреса &:
ptr = &i;
ukaz = &x;
adr = &c;
Сейчас указатели ptr, ukaz, adr будут хранить адреса (номера) первых (младших) байтов памяти, отведенной для переменных i, x, c (адрес байта памяти – это шестнадцатеричное число).
при 0<m<n по формулам:
= 
= 1, 
+ 