Рекурсивные функции, базовая задача, рекурсивный вызов, шаг рекурсии.

вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция {\displaystyle A} A вызывает функцию {\displaystyle B} B, а функция {\displaystyle B} B — функцию {\displaystyle A} A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии. Рекурсивная программа позволяет описать повторяющееся или даже потенциально бесконечное вычисление, причём без явных повторений частей программы и использования циклов.

 

Рекурсивная задача в общем случае разбивается на ряд этапов. Для решения задачи вызывается рекурсивная функция. Эта функция знает, как решать только простейшую часть задачи – так называемую базовую задачу (или несколько таких задач). Если эта функция вызывается для решения базовой задачи, она просто возвращает результат. Если функция вызывается для решения более сложной задачи, она делит эту задачу на две части: одну часть, которую функция умеет решать, и другую, которую функция решать не умеет. Чтобы сделать рекурсию выполнимой, последняя часть должна быть похожа на исходную задачу, но быть по сравнению с ней несколько проще или несколько меньше. Поскольку эта новая задача подобна исходной, функция вызывает новую копию самой себя, чтобы начать работать над меньшей проблемой – это называется рекурсивным вызовом, или шагом рекурсии. Шаг рекурсии включает ключевое слово return, так как в дальнейшем его результат будет объединен с той частью задачи, которую функция умеет решать, и сформируется конечный результат, который будет передан обратно в исходное место вызова.

 

рекурсивный вызов — прямой или опосредованный вызов функцией самой себя.

 

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

<имя определяемого предиката>:- [<подцели>], [<условие выхода из рекурсии>], [<подцели>], <имя определяемого предиката>, [<подцели>].

Предикат в программировании — выражение, использующее одну или более величину с результатом булева типа.

Примеры использования рекурсии.

Классический пример: рекурсивно -определённый факториал целого неотрицательного числа: n!

Рекурсия и итерация.

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

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

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

Понятие структурного типа данных.

Описание структуры.

Трактовка имени структуры.

Доступ к элементам структуры.

Инициализация структур. Структуры и функции.

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

http://cppstudio.com/post/7008/

Поля бит в структурах.

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

Синтаксис объявления битового поля

struct <имя> { <тип> <имя>: <размер>;...}

Объединения.

http://www.c-cpp.ru/books/obedineniya

Линейные списки.

Линейный однонаправленный список — это структура данных, состоящая из элементов одного типа, связанных между собой последовательно посредством указателей. Каждый элемент списка имеет указатель на следующий элемент. Последний элемент списка указывает на NULL. Элемент, на который нет указателя, является первым (головным) элементом списка. Здесь ссылка в каждом узле указывает на следующий узел в списке. В односвязном списке можно передвигаться только в сторону конца списка. Узнать адрес предыдущего элемента, опираясь на содержимое текущего узла, невозможно.