Алгоритмы реализации сложной рекурсии на языке программирования С++

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

Рубрика Программирование, компьютеры и кибернетика
Вид лекция
Язык русский
Дата добавления 16.03.2022
Размер файла 328,0 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

Алгоритмы реализации сложной рекурсии на языке программирования С++

Возможна чуть более сложная схема: функция A вызывает функцию B, а та в свою очередь вызывает A. Это называется сложной рекурсией. При этом оказывается, что описываемая первой процедура должна вызывать еще не описанную. Чтобы это было возможно, требуется использовать описание функции B до ее использования.

Пример: вычислить значение выражения:

#include <iostream>

using namespace std;

int pow(int, int); // описание сигнатуры

double calc(int x, int n)

{

return (double)pow(x, n) / n; // вызов функции pow

}

int pow(int x, int n)

{

if (n == 1) return x;

return x*calc(x, n - 1); // вызов функции calc

}

int main()

{

int n, x;

cout << "n = "; cin >> n;

cout << "x = "; cin >> x;

double a = calc(x, n); // вызов рекурсивной функции

cout << a;

cin.get(); cin.get();

return 0;

}

Результат выполнения:

n=2

x=3

4.5

Префиксная и постфиксная форма записи

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

Рис. 1

Рекуррентные соотношения

Во многих случаях в основе рекурсии лежат рекуррентные соотношения.

Рекуррентное соотношение -- это соотношение вида:

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

выражающее каждый член последовательности an через p предыдущих членов.

Вычисление требуемого элемента последовательности будет состоять в повторяющемся обновлении значений этой последовательности.

Каждое такое обновление называется итерацией, а процесс повторения итераций - итерированием.

Рекурсия или итерирование

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

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

Рис. 2

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

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

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

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

Стандартная библиотека математических функций.

Математические функции хранятся в стандартной библиотеке math.h. Аргументы большинства математических функций имеют тип double. Возвращаемое значение также имеет тип double.

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

математический факториал итерация рекурсивный

Рис. 3

Размещено на Allbest.ru


Подобные документы

  • Использование рекурсии в предметных областях. Рекурсивные процедуры и функции в программировании. Создание алгоритмов для рисования графических изображений с использованием рекурсии в среде программирования Pascal ABC. Примеры рекурсии в графике.

    творческая работа [6,7 M], добавлен 01.02.2014

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

    презентация [396,3 K], добавлен 12.11.2012

  • Исследование понятия рекурсии в программировании. Описание метода, который позволяет разбить задачу на части все меньшего и меньшего размера. Изучение схемы работы рекурсивной процедуры. Способы изображения древовидных структур. Избавление от рекурсии.

    презентация [486,1 K], добавлен 22.10.2013

  • Структура языка Паскаль, встроенные процедуры и функции. Составление алгоритма решения уравнения, описывающего работу кривошипно-шатунного механизма, с помошью метода итерации, метода Гаусса и метода Зейделя. Блок-схемы алгоритмов и текст программы.

    курсовая работа [64,6 K], добавлен 07.05.2011

  • Анализ затрат и прибыли. Создание программного проекта для решения задачи о прибыли и убытках на языке программирования C#. Использование функций и переменных, компиляция программы. Алгоритмы и структуры данных. Тестирование программного обеспечения.

    курсовая работа [1,2 M], добавлен 03.01.2015

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

    лабораторная работа [27,8 K], добавлен 28.05.2012

  • Сущность языка программирования, идентификатора, структуры данных. Хранение информации, алгоритмы их обработки и особенности запоминающих устройств. Классификация структур данных и алгоритмов. Операции над структурами данных и технология программирования.

    контрольная работа [19,6 K], добавлен 11.12.2011

  • Рассмотрение составляющих элементов стандартной библиотеки (программирование функций, глобальные переменные, шаблоны, макросы, классы), основных компонентов (контейнер, итератор, адаптер, функциональный объект) и алгоритмов языка программирования С++.

    реферат [19,8 K], добавлен 06.02.2010

  • Особенности программирования на языке Паскаль в среде Турбо Паскаль. Линейные алгоритмы, процедуры и функции. Структура данных: массивы, строки, записи. Модульное программирование, прямая и косвенная рекурсия. Бинарный поиск, организация списков.

    отчет по практике [913,8 K], добавлен 21.07.2012

  • Теоретическая и практическая реализация комплексной арифметики на языке программирования Си. Разработка программы, производящей арифметические действия с комплексными числами. Автоматизации решения комплексных чисел. Матричная и стандартная модель.

    курсовая работа [495,4 K], добавлен 21.01.2012

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.