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

• Название: 1 Базовый процедурноориентированный алгоритмический язык
• Анкор: Алгоритм и структура данных
• Дата: 03.11.2022
• Размер: 1.16 Mb.
• Имя файла: Алгоритм и структура данных.docx
• Тип: Документы; #768957
• страница: 5 из 11

Псевдонимы типов в перегрузке функций

Поскольку объявление typedef (псевдонима типа) не создает новый тип данных, то следующие два объявления функции print() считаются идентичными:

1 2 3

typedef char *string; void print(string value); void print(char *value);

Рекурсия

В программировании рекурсия, или же рекурсивная функция — это такая функция, которая вызывает саму себя.

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

Не приведёт ли рекурсивная функция к бесконечному циклу?

Да, такой исход вполне возможен. Однако, как и у функции for или while, рекурсию можно прервать условием break, чтобы функция перестала вызывать саму себя.

Вот пример кода того, как можно реализовать функцию обратного отсчёта с использованием рекурсии:

function countDown(n){
console.log(n)if(n > 1){
countDown(n -1) // вызов рекурсии
} else {
return true // основное действие
}
}
countDown(5)// 5
// 4
// 3
// 2
// 1
countDown(-1)
// - 1 // true

Как прервать рекурсию:

Допустим, у нас имеется функция CountDown, которая принимает аргумент (n). Чтобы реализовать обратный отсчёт, нам следует повторить последовательность действий, понижающих значение параметра. Создадим условие вида:

Если (n) больше 1, то вызвать функцию CountDownи вернуться в начало цикла, затем вычесть единицу и снова проверить, выполняется ли условие (n) > 1.

По умолчанию нам нужно создать базовое условие функции, возвращающее значение true, чтобы предотвратить попадание в бесконечный цикл. Базовым условием функции здесь будет условие о том, что любое значение больше 1 не вызовет прерывание цикла.

Плюсы и минусы рекурсивных функций

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

Плюсы:

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

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

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

И всё же стоит отметить, что рекурсия не всегда выигрывает по скорости по сравнению с циклами.

• 
  Рекурсию легче отлаживать.
  

Многие согласятся, что эта причина очень важна. Рекурсия проста в отладке из-за того, что она не содержит сложных и длинных конструкций.