Размещено на http://www.Allbest.Ru/

Размещено на http://www.Allbest.Ru/

Размещено на http://www.Allbest.Ru/

Министерство образования и науки российской федерации

Федеральное государственное бюджетное образовательное учреждение высшего образования

Государственный университет

Институт прикладной математики и компьютерных наук

Кафедра вычислительной техники

Отчет по лабораторной работе

по дисциплине «Программирование»

Тема:

Рекурсия C#

Тула 2019

Цель работы

Изучить рекурсию в языке С#, научиться применять рекурсию для решения задач.

Теоретическая справка

Рекурсивным называют метод, если он вызывает сам себя в качестве вспомогательного. В основе рекурсивного метода лежит так называемое "рекурсивное определение" какого-либо понятия. Классическим примером рекурсивного метода является метод, вычисляющий факториал.

Метод с прямой рекурсией обычно содержит следующую структуру:

if (<условие>)

<оператор>;

else <вызов данного метода с другими параметрами>;

В качестве <условия> обычно записываются некоторые граничные случаи параметров, передаваемых рекурсивному методу, при которых результат его работы заранее известен, поэтому далее следует простой оператор или блок, а в ветви else происходит рекурсивный вызов данного метода с другими параметрами.

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

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

Любой рекурсивный метод можно преобразовать в обычный метод. И практически любой метод можно преобразовать в рекурсивный, если выявить рекуррентное соотношение между вычисляемыми в методе значениями. В общем случае рекурсивный метод включает в себя некоторое множество операторов и один или несколько операторов рекурсивного вызова. Действия могут выполняться после рекурсивного вызова, до рекурсивного вызова, а также и до, и после рекурсивного вызова существует еще и косвенная рекурсия, в которой метод вызывает себя в качестве вспомогательного не непосредственно, а через другой вспомогательный метод.

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

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

Например, рекурсивный метод подсчета n-ного члена последовательности Фибоначчи. Данный метод будет работать неэффективно. FbR(17) вычисляется в ней как FbR(16) + FbR(15). В свою очередь FbR(16) вычисляется в ней как FbR(15) + FbR(14). Таким образом, FbR(15) будет вычисляться 2 раза, FbR(14) - 3 раза, FbR(13) - 5 раз и т.д. Всего для вычисления FbR(17) потребуется выполнить более тысячи операций сложения. Для сравнения при вычислении Fb(17), т.е. используя не рекурсивный метод, потребуется всего лишь 15 операций сложения.

Задание 1

Разработать рекурсивный метод (возвращающий значение) для нахождения наибольшего общего делителя методом Евклида

Рисунок 1 - Программа 1

Задание 2

Разработка рекурсивных методов (не возвращающих значений):

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

1 (1 раз)

222 (3 раза)

33333 (5 раз)

… (n раз)

33333 (5 раз)

222 (3 раза)

1 (1 раз)

Рисунок 2 - Программа 2

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

Рисунок 3 - Программа 3

Листинг программы

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace Lab06

{

class Program

{

static int F(int n)

{

if (n < 0) return n;

return F(n - 4)-F(-1);

}

static void Main(string[] args)

{

Console.Write("w = ");

int w = int.Parse(Console.ReadLine());

Console.WriteLine($"F(w) = {F(w)}");

Console.ReadLine();

}

}

}

Листинг программы

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace Lab6_2

{

class Program

{

static int F(int n)

{

if (n <= 1) return n;

return F(n - 2) + F(n - 1);

}

static void Main(string[] args)

{

Console.Write("w = ");

int w = int.Parse(Console.ReadLine());

Console.WriteLine($"F(w) = {F(w)}");

Console.WriteLine(" " + F(w));

Console.ReadLine();

}

}

}

Результаты тестирования

Размещено на allbest.Ru