Рекурсия возникает в программах, в которых некоторая функция вызывает сама себя. Рекурсия кажется похожей на бесконечный цикл, но это не так.
Пример : рекурсия используется для вычисления факториала числа. Факториал числа определяется как произведение самого числа и всех предыдущих целых чисел. Например:
8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 40320
Необходимо внимательно выбирать тип данных, так как произведение растет очень быстро: факториал 15 равен 1307674368000.
#include <stdio.h>
double dfactorial(double danswer);
main()
{
double dnumber=15.0;
double dresuit;
dresult=dfactorial(dnumber);
printf("The factorial of %5.01f is: %15.01f\n",dnumber, dresuit);
return(0);
}
double dfactorial(double danswer)
{
if (danswer <= 1.0)
return(1.0);
else
return(danswer*dfactorial(danswer-1.0));
}
Возникает рекурсия, так как внутри функции dfactorial() имеется вызов ее самой. В функции printf() используется новый код форматирования для печати значения двойной длины: %...lf. Здесь "1" является модификатором формата f и обозначает тип double вместо float.
Динамическая память (heap- куча) — это просто свободная область памяти, с которой работают при помощи функций динамического выделения памяти malloc() и free().
При вызове функции malloc() выделяется непрерывный блок памяти для указанного объекта и возвращается указатель на начало этого блока. Функция free() возвращает выделенный блок обратно в динамическую область памяти для повторного использования.
Аргумент, передаваемый функции mа11ос(), представляет собой объем необходимой памяти в байтах. Если имеется свободная память, функция возвращает указатель типа void *, который можно преобразовать в любой необходимый тип указателя. Концепция указателей типа void распространяется на указатели неизвестного типа или родовые (generic) указатели. Любой указатель можно преобразовать в указатель типа void и наоборот, без потери информации.
В следующем фрагменте кода выделяется память для 300 чисел типа float:
Функции malloc() был сделан запрос на выделение памяти некоторого объема; этот объем определяется как 300, умноженное на действительный размер числа типа float, и выражается в байтах. Для того чтобы получить указатель типа float, использована операция приведения типа (float *). Каждый блок выделяемой памяти совершенно отделен и независим от любых других блоков памяти. О расположении блоков нельзя сделать абсолютно никаких предположений. Блоки обычно "помечаются" некоторыми признаками, позволяющими операционной системе управлять их положением и размером. Когда блок становится ненужным, его можно вернуть операционной системе, используя следующий оператор:
free ((void *) pf);
Имеющаяся память распределяется двумя способами. Когда объявляются переменные, они создаются в стеке, и при этом указатель стека сдвигается вниз. Когда область действия переменных заканчивается (например, когда локальная переменная больше не нужна), память для таких переменных автоматически освобождается путем смещения указателя стека вверх. Размер стековой памяти всегда должен быть известен при компиляции.
В программе возможно существование переменных, размер которых при компиляции неизвестен. Для них необходимо самостоятельно выделять память из свободной области. Свободная память занимает нижнюю часть памяти программы и растет снизу вверх, а стек занимает верхнюю часть и растет сверху вниз.
Программы могут в любой момент выделять и освобождать динамическую память. На переменные, память для которых выделена в динамической области, не распространяются правила области действия, которые справедливы для других переменных. Эти переменные действуют всегда; поэтому, если вы выделили динамическую область памяти, то не должны забывать о ее освобождении.
Для выделения и освобождения динамической памяти используются операторы new и delete. Для new аргументом является выражение, определяющее число выделяемых байт, а возвращаемое значение — это указатель на начало блока памяти. Аргументом для delete является начальный адрес освобождаемого блока памяти.
Пример:
#include <stdio.h>
#include <stdlib.h>
#define ISIZE 512
void main()
{
int *pimemory_buffer;
pimemory_buffer=malloc(ISIZE * sizeof(int));
if (pimemory_buffer == NULL)
printf("Insufficient memory\n"); /* Недостаточно памяти */
else
printf("Memory allocated\n"); /* Память выделена */
free(pimemory_buffer);
}
Структуры С и C++
Структурированные данные весьма распространены в повседневной жизни. Картотека, содержащая адреса знакомых, номера телефонов и прочую информацию, является структурой связанных атрибутов. Список любимых компакт-дисков или пластинок также является структурой; каталог диска — структура. Структуру буквально можно рассматривать как набор переменных различных типов, образующих единый объект. Этот отдельный объект и является структурой.
