Понятие рекурсии. Механизм рекурсии. Пример рекурсивной функции.

Ответ:

Рекурсия - способ вызова, при котором функция обращается к самой себе.

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

int fact (int n) { int t, answer=1; for (t=1; t<=n; t++) answer = answer * t; return(answer); }

int fact(int n) { if (n==0) return 1; n = n * fact(n-1); return n; }

<- Условие остановки (базовый случай) <- Условие продолжения (шаг рекурсии)

Механизм рекурсии.

intF(intN) { if (N == 0) return 1; else return (N * F(N-1)); }

Возможные проблемы:

· Самая распространенная ошибка при организации рекурсии – бесконечная последовательность "само- вызовов".

· При написании рекурсивной функции необходимо начинать с организация выхода!

· При большой глубине рекурсии возможно переполнение стека.

На этапе отладки целесообразно использовать printf(...)для вывода отладочной информации о текущем шаге:

int fac(int n)

{

printf("Function fuc(), n=%d\n", n);

if (n==0)    

return 1;

n = n*fac(n-1);

printf("Function fuc(), n=%d\n", n);

return n;

       }

Рекурсия.

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

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

· Примеры задач, для которых рекурсия будет наиболее простым и естественным способом решения: поиск в по дереву, обход графа, быстрые сортировки и др.

Рекомендации:

· Свести исходную задачу к одной или нескольким подзадачам, из решения которых можно построить решение исходной задачи.

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

· Явный ответ надо давать, когда исходная задача уже не сводится к подзадачам.

24.Что такое комбинированный/составной тип данных? Способы описания (примеры). Способы обращения к компонентам структуры. Примеры.

Ответ:

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

Для работы со структурой необходимо решить следующие задачи:

· Разработать и объявить формат (компоновку) структуры;

· Объявить переменную (или переменные), соответствующую данной структуре;

· Обеспечить доступ к индивидуальным компонентам переменной типа структуры.

Объявление структуры

Объявление структуры – общее описание, показывающее из каких частей (членов, полей) состоит структура.

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

Объявление заканчивается точкой с запятой.При объявлении структуры память не выделяется.

Фактически объявление структуры определяет новый тип с именем структуры

struct addr { char name[30]; char street [40]; char city[20]; char state[3]; unsigned long int zip; };

// addr – метка структуры (структурный тип)   // память не выделяется

Создание переменной типа структуры

Для хранения данных необходимо выделить память.Выделение памяти происходит при объявлении переменной типа структуры.При объявлении типа структуры обязательно использование слова struct перед именем структуры (если не используется typedef).

struct addr

{

char name[30];

char street [40];

char city[20];

char state[3];

unsigned long int zip;

};     // памятьневыделяется

// памятьвыделяется

structaddraddr _ info;

// памятьвыделяетсяподкаждуюпеременную

structaddrabook _ city, abook _ corp;

При объявлении структуры можно одновременно объявить одну или несколько переменных:

struct addr

{

char name[30];

char street[40];

char city[20];

char state[3];

unsigned long int zip;

}

addr _ info, binfo, cinfo;

Допускается (не рекомендуется) объявление структуры без имени типа – только для однократного объявления переменных.

struct

{

char name[30];

char street[40];

char city[20];

char state[3];

unsigned long int zip;

}

addr _ info;

Доступ к полям структуры

Доступ к полям структуры осуществляется с помощью оператора «.»:

имя_переменной.имя_члена

Где

имя_переменной – имя переменной типа структуры

addr_info.zip = 12345;                  printf("%ld", addr_info.zip); gets(addr_infо.name);                                                for (t=0; addr_info.name[t]; ++t) putchar (addr_info.name[t]);

// переменная addr_info имеет тип структуры addr // addr_info.zip имеет тип long int   // addr_info.name имеет тип char