Лекция №13. Рекурсия

Строки, массивы и структуры в качестве параметров функций

Рассмотрим передачу строк и массивов в качестве параметров функций.

Можно передавать массивы параметрам функции, а функции могут возвращать массивы в программу:

void Print_String(char string[])

{ printf(string);}

main()

{. . . . . char MyStr[]="С++ - язык для профессионалов";

. . . . .Print_String (MyStr);. . . . .}

В функцию передается не сам массив, а только адрес его первого эле­мента, связанный с именем массива. Другими словами, символы строки, яв­ляющейся аргументом функции (в данном случае MyStr для функции Print_String), не передаются через стек.

При передаче символьных строк функциям следует помнить о том, что в случае объявления #define MAXLEN 128;могут запоминаться только (MAXLEN-1) символов и завершающий нулевой байт.

Borland C передает функциям адреса строк и массивов, что существенно экономит стековое пространство. Вследствие такой передачи (по ссылке) вызываемая функция может изменять значения элементов массива непосредственно в тех ячейках памяти, где он располагается. Если нужно запретить изменять значения элементов массива, следует объявить его как массив констант.

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

Можно объявить функцию:

void SomeFunc (int arr[rows][cols]);

или

void SomeFunc (int arr[][cols]);

причем второй вариант более предпочтителен.

Но объявление

void SomeFunc (int arr [rows][]);

скомпилировано не будет, как и объявление

void SomeFunc(int arr[][]);

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

Рекурсия означает возврат. Рекурсивной называется функция, вызывающая сама себя. Рекурсивные функции, которые прямо вызывают сами себя, называются включительно рекурсивными. Если две функции рекурсивно вызывают друг друга, они называются взаимно рекурсивными.

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

Каждый вызов рекурсивной функции называется рекурсивным вызовом, или шагом рекурсии.

Существует много задач, рекурсивных по своей природе: n!, аⁿ, числа Фибоначчи и др.

Пример. Рекурсивное вычисление факториала. n!=n*(n-l)*(n-2)*. . .*2*1, причем 0!=1, 1!=1 - по определению факториала.

Рекурсивное решение заключается в многократном вызове функции вычисления факториала из самой этой функции. Рассмотрим для примера вычисление 5!: 5!=5*4! 4!=4*3! 3!=3*2! 2!=2*1! 1!=1

Вычисление 1! - базовая задача, а также признак завершения рекурсии.

l!=l -возвращает 1; 2!=2*l!=2*l=2 - возвращает 2;

3!=3*2!=3*2=6 - возвращает 6; 4!=4*3!=4*6=24 - возвращает 24;

5!=5*4!=5*24=120-возвращает 120.

// Рекурсивная функция факториала:

unsigned long fact(unsigned long);

main()

{ printf("5!=%d", fact(5));

return 0;}

// Рекурсивное описание функции факториала:

unsigned long fact(unsigned long i_dat)

{ if(i_dat<=1) return 1;

else return i_dat*fact(i_dat-1);}

Пример. Рекурсивное вычисление степенной функции xⁿ = x*x*x* ... *x

long power(int number, int x);

main()

{printf("4 в 5-й степени = %d", power(5,4));

return 0;}

// Рекурсивное описание степенной функции:

long power(int number,int x)

{ if (number=0) return 1;

else return x*power(number-1 ,x);}

Если рекурсивная функция объявляет какие-либо локальные переменные, то эти переменные повторно создаются на каждом уровне рекурсии.

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

Обычно рекурсивные решения используются лишь в тех случаях, когда они поддаются отладке легче, чем нерекурсивные.