Программная реализация рекурсивных функций

 

МИНИСТЕРСТВО ОБРАЗОВАНИЯ  И НАУКИ, МОЛОДЁЖИ И СПОРТА УКРАИНЫ

Севастопольский национальный технический  университет

 

 

Кафедра радиотехники и телекоммуникаций

 

 

 

 

Отчёт

по лабораторной работе №1

«Программная реализация рекурсивных  функций»

по дисциплине

«Вычислительная техника и программирование»

 

 

 

 

                                                                    Выполнил: студент гр. Р-12д

                                                                  Иванищев Алексей Юрьевич

                                  Вариант №8

                                                             Защитил с оценкой:______

 

                                                                            Приняла:

                                      Редькина Е.А.

 

                                                   

г.Севастополь

2013г.

СОДЕРЖАНИЕ

1. Описание лабораторной  работы 3

1.1. Цель работы 3

1.2. Индивидуальное задание 3

1.3. Теоретические сведения 3

2. Выполнение лабораторной  работы 4

2.1. Структурная схема  алгоритма работы программы 4

2.2. Текст программы 5

2.3. Таблица переменных 6

2.4. Результаты выполнения  программы 6

ВЫВОДЫ 7

ПРИЛОЖЕНИЕ А. Проверка работы программы в приложении MathCAD 8

 

 

1. Описание лабораторной работы

1.1. Цель работы

Цель работы — изучение особенностей составления и использования рекурсивных функций в языках программирования С/С++. Получение практических навыков реализации алгоритмов, использующих рекурсивные функции, средствами языков программирования С/С++.

 

1.2. Индивидуальное задание

Вариант №8. Составить схему алгоритма и написать на языке С/С++ программу вычисления суммы n элементов ряда, полученного при разложении функции f(x), используя рекурсивные функции.

 

 

 

 

 

 

 

1.3. Теоретические сведения

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

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

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

 

2. Выполнение лабораторной работы

2.1. Структурная схема алгоритма работы программы

Структурная схема алгоритма решения задачи представлена на рис. 2.1, рис. 2.2 и рис. 2.3.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис. 2.1 — Структурная  схема алгоритма программы (функция main)

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис. 2.2 — Структурная  схема алгоритма программы 

(функции sum_of_series и term_of_series)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис. 2.3 — Структурная  схема алгоритма программы 

(функция factorial)

2.2. Текст программы

#include<conio.h>

#include<iostream.h>

#include<math.h>

double sum_of_series(double x, int k,int n);

double term_of_series(double x,int  k);

void main()

{

int n;

double x,

sum;

clrscr();

cout<<"Vvedite znachenie argumenta 'x': "; cin>>x;

cout<<"Vvedyte kolichestvo chlenov ryada 'n':";cin>>n;

sum=sum_of_series(x,1,n);

cout<<"Summa chlenov ryada:" <<sum<<endl;

cout<<"Funkciya:" <<x/(1-x)<<endl;

getch();

return;

}

double sum_of_series(double x, int k, int n)

{

if(k<=n)

{

return(term_of_series(x,k)+sum_of_series(x,k+1,n));

}

else

{

return 0;

}

}

double term_of_series(double x, int k)

{

double result=0;

result = (pow(x,pow(x,k-1)))/(1-pow(x,pow(2,k)));

cout<<"Chlen ryada: "<<k

<<"Znachenie :"<<result<<endl;

return result;

}

 

2.3. Таблица переменных

В программе использованы переменные, представленные в таблице 2.1.

 

Таблица 2.1 — Используемые переменные

Переменная	Тип	Значение
x	Double	Значение аргумента
k	Int	Порядковый номер
n	Int	Количество суммируемых  членов ряда
sum	Double	Сумма членов ряда

 

2.4. Результаты выполнения программы

Результат выполнения программы  изображен на рис. 2.4.

 

Рис. 2.4 — Изображения  окна UserScreen при выполнении программы

 

Выводы

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

Все функции языка С++ (кроме функции main) могут быть использованы для построения рекурсии.

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ПРИЛОЖЕНИЕ А.

Результаты вычисления функций, полученные в MathCAD

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис. А.1. График пересечений заданных функций