Реализация рекурсии на разных языках программирования

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

Реализация рекурсии на разных языках программирования

Рабданова Венера Владимировна,

В статье рассматриваются реализация рекурсивных алгоритмов на разных языках программирования. Дана классификация языков программирования. В статье приведен пример решения задачи нахождения суммы цифр целого числа с использованием рекурсии. Задача решена на следующих языках программирования: С++, C#, Python, F#, LISP.

The article deals with the implementation of recursive algorithms in different programming languages. The classification of programming languages is given. The article provides an example of solving the problem offinding the sum of digits of an integer using recursion. The problem was solved in the following programming languages: С++, C#, Python, F#, LISP.

Keywords: recursion, programming languages, program, algorithm, functional programming, algorithmic and declarative programming languages.

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

В данной работе приведены примеры реализации рекурсии на разных языках программирования. Вообще языки программирования подразделяются на алгоритмические и декларативные. К алгоритмическим языкам относятся такие языки как C++, C# и т.п.

C++ принадлежит к семейству языков с C - подобным синтаксисом. Он является мультипарадигмальным, объектно-ориентированным языком программирования со статической типизацией данных. Язык программирования C++ назывался «С с классами» и был создан в начале 1980 годов Бьерном Страуструпом. Изначально, это был усовершенствованный язык С, в который была добавлена возможность работы с классами и объектами, в результате чего было объединено возможность более быстрого написания программ, с использованием классов и возможность написания быстро-действенных программ за счет основы в виде языка С. Постепенно «С с классами» дополнялся новыми возможностями, такими как перегрузка функций и операторов, использование ссылок и констант. С 1985 года язык «С с классами», официально был переименован в С++.

Рисунок 1. Код рекурсивной программы на языке программирования

C#, также как с C++ принадлежит к семейству языков с C - подобным синтаксисом. C# является объектно-ориентированным языком программирования, на который во многом повлияли такие языки программирования как C++, Delphi и Java. Разработка такого языка как C# началась в 1998 году под кодовым названием COOL (C-style Object Oriented Language). Официально же, первая доступная версия была объявлена в 2000 году. Хотя C# и заимствовал у Java и C++ большую часть своих функций, компания Microsoft, переосмыслила некоторые возможности языка, так, в C# не была добавлена возможность множественного наследования классов. При этом, в отличии от Java, были перенесены такие возможности C++, как беззнаковые типы данных, ограниченная перегрузка операторов и ограниченная работа с указателями, там, где было отмечена возможность работы с небезопасным кодом, посредством ключевого слово «unsafe» и указании опции компилятору.

Рисунок 2. Код рекурсивной программы на языке программирования С#

К декларативным языкам относится ЛИСП, F#, которые являются языками функциональными программирования. Сюда же можно отнести Python.

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

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

F# - принадлежащий к .NET семейству и имеет открытый исходный код и распространяется по лицензии Apache Software License 2.0, которая одобрена OSI. Данный язык был создан в 2005 году подразделением компании Microsoft, Microsoft Research, главным разработчиком которого был Дон Сайм, а в данный момент его разработку ведет компания F Sharp Software Foundation, созданная непосредственно для разработки и ведения языка F#.

F# имеет строгую типизацию и является безопасным в отношении типов языком программирования. Подобное отношение к типизации позволяет исключать ошибки при приведении типов. Несмотря на то, что в большинстве языков программирования переменные при объявлении являются изменяемыми, в F# же, они будут являться константами, что требует обозначения переменной как изменяемой, словом «mutable.

Многие языки программирования компилируют код только в одном из режимов, или при запуске программы, то есть немедленно, или отложено, то есть в процессе выполнения программы. F# же позволяет программисту самому указать, каким образом компилятор и интерпретатор будут выполнять свои функции.

Рисунок 3. Код рекурсивной программы на языке программирования F#

Python - мультипарадигмальных язык программирования высокого уровня. Он разработан Гвидо Ван Россумом и поддерживается компанией Python Software Foundation, во главе с ним. Разработка данного языка была начата в 1989 году и создавался он в первую очередь как расширение для Amueba (открытая распределенная операционная система) и в последствии язык начал активно развиваться за счет его автора и работ сообщества. 3 декабря 2008 года была выпущенная версия Python 3.0, которая устранила множество недостатков, при этом имея частичную обратную совместимость с прошлыми версиями. Язык разрабатывался как интерпретируемый язык с динамической типизацией. Также он имел встроенный сборщик мусора и динамическое разрешение имен. Не маловажным условием при разработке языка было также то, что он должен быть максимально прост в работе и противопоставлял свою концепцию, которая подразумевала один очевидный путь для достижения цели, концепции языка Perl, который звучал так: «There's More Than One Way To Do It» или «Есть несколько способов сделать это».

Рисунок 4. Рекурсивная программа на языке программирования Python

За счет своей модульности, Python будет одинаково работать в разных системах, однако для интерпретации он будет требовать установку набора инструментов для своей интерпретации (рис. 4).

Лисп (LISP, от англ. LISt Processing language - «язык обработки списков»; современное написание: Lisp) - семейство языков программирования, программы в которых, представляют собой набор линейных списков и символов, называющихся атомами. Созданный Джоном Маккарти язык программирования Lisp, в первую очередь предназначался для работы с искусственным интеллектом и на данный момент все еще остается основным инструментом для работ в данной области. Хотя данный язык и нельзя назвать популярным, помимо использования его в искусственном интеллекте, его также применяют и для промышленного программирования, создания скриптов и крупных веб приложений.

Lisp является одним из наиболее старых языков программирования, на ряду с Фортраном и Коболом, который используется до сих пор, при этом являясь высокоуровневым языком программирования. Помимо этого, он также является первым, из сохранившихся языков, способным автоматически управлять памятью и сбором мусора.

Типизация в Lisp реализована динамически, что расширяет возможности программирования, освобождая программиста от ручной типизации переменных. С ранних версий Lisp приобрел некоторые черты императивности, несмотря на то что является функциональным языком программирования, помимо этого он способен обрабатывать символы и обладает средствами, необходимыми для реализации объектно - ориентированных программ. Примером такой реализации является платформа CLOS.

Рисунок 5. Код рекурсивной программы на языке программирования LISP

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

Литература

рекурсивный алгоритм язык программирования

1. Баррон Д. Рекурсивные методы в программировании - М.: Вильямс, 2017. - 221 с.

2. Грин Д., Кнут Д. Математические методы анализа алгоритмов - М.: Вильямс , 2015. - 398 с.

3. Коротков М.А., Степанов Е.О. Основы теории алгоритмов - М.: Вильямс, 2016. - 174 с.

4. Колмогоров А.Н. Теория информации и теория алгоритмов - М.: Вильямс, 2017. - 240 с.

5. Мальцев, А.И. Алгоритмы и рекурсивные функции: моногр. / А.И. Мальцев. - М.: Вильямс, 2016. - 346 с.

6. Рекурсивные функции - Библиотека MSDN, 2015. [Электронный ресурс] URL:https://msdn.microsoft.com/ru-ru/library/4bftz997.aspx дата обращения 04.09.22

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