Главная · Карта сайта · Поиск · Статьи · Компьютерные курсы · Обучающие программы · Открытые проекты · Веб-программирование · Создание интернет-сайта · Полезные ссылки · Глоссарий · Контакты · Декабрь 09 2016 20:17:58
Последнее опубликованное

Что такое Model-View-Controller
Pattern Model-View-Controller

Как создать свой веб-сайт
Как создать свой сайт в интернете

Разное
Статистика

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


Итерация свойственна человеку, рекурсия божественна.

L. Peter Deutsch

Содержание курса

Шаг 3. Рекурсивное вычисление факториала

Факториал числа N – это произведение всех натуральных чисел от 2 до N. Сама по себе задача вычисления факториала очень простая: достаточно одного цикла for от 2 до N и все. Но на этом примере я хочу вас познакомить с таким понятием, как рекурсия. С выделением фрагмента кода в отдельную функцию вы уже познакомились на предыдущем этапе. Сейчас мы также выделим часть вычислений в отдельную функцию, даже в две, причем вторая функция будет вызывать сама себя – это и называется рекурсией.

Описание алгоритма

Определим функцию Factorial, которая на вход получает натуральное число n, а ее результатом должен стать факториал числа n или n!. При линейном подходе к вычислению факториала нам следовало бы в теле функции разместить цикл for, о котором я уже упоминал выше, но мы поступим иначе. Определим отдельную реализацию функции (функцию с тем же именем, но другим набором параметров) Factorial, которая, помимо входного параметра n, будет также получать дополнительный параметр result, являющийся промежуточным результатом значения вычисляемого нами факториала. Если значение n на входе будет равно единице, то мы возвращаем значение result в качестве значения факториала. Если n больше единицы, то выполняем рекурсивный вызов функции Factorial, но в качестве параметра result передаем уже result * n, а в качестве n передаем значение n, уменьшенное на единицу. В C# уменьшение на единицу кратко записывается, как --n или n--. Разница в том, что происходит раньше: уменьшение значения или обращение к переменной. В нашем случае нам сначала нужно уменьшить значение n, а потом уже передать результат на вход функции, поэтому выбираем первый вариант. Операции ++ и -- называются инкремент и декремент соответственно. Вернемся к нашей функции. Чтобы объяснить, как работает алгоритм, я последовательно выпишу значения параметров, передаваемых второй реализации функции Factorial. Например, мы вычисляем факториал числа 5. Последуют следующие вызовы:

Factorial(5) =>Factorial(1, 5) => Factorial(5, 4) =>Factorial(20, 3) =>Factorial(60,2) => Factorial(120,1)

Таким образом, мы вычисляем факториал “с конца”: 5! = 5*4*3*2.

Фрагмент кода

C#:
    //Запуск рекурсии
    static long Factorial(int n)
    {
        return Factorial(1, n);
    }

    //Рекурсивное вычисление факториала
    static long Factorial(long result, int n)
    {
        if (n == 1)
            return result;

        return Factorial(result * n, --n);
    }
VB.NET:
Shared Function Factorial(ByVal n As Integer) As Long
    Return Factorial(1, n)
End Function

Shared Function Factorial(ByVal result As Integer, ByVal n As Integer) As Long
    If (n = 1) Then Return result

    result = result * n
    n = n - 1

    Return Factorial(result, n)
End Function

Полные версии алгоритмов

На языке C#.
На языке VB.NET.

Самостоятельно

Самостоятельно реализуйте вычисление факториала с использованием цикла for или while.

Далее: Умножение матрицы на вектор.



Компьютерные курсы и курсы программирования
Основы программирования

Курс для начинающих программистов на C# и VB.NET.

SQL 25™

Построение SQL запросов и работа с базой данных.

C# Quick Guide™

Программирование на C#. Краткое руководство.

RegEx

Применение регулярных выражений.

Plug-in архитектура

Примеры программной Plug-in архитектуры.

XML и его расширения

Язык разметки XML и его расширения с примерами.

HTML и разметка гипертекста

Языки HTML, XHTML и CSS с примерами разметки.

Основы веб-дизайна

Основы веб-дизайна: решения типовых задач верстки.

Программирование на PHP

Руководство по программированию на PHP для начинающих.

Справочные материалы

Шаблоны проектирования
Каталог шаблонов проектирования программных компонентов.

Рефакторинг кода
Каталог приемов рефакторинга программного кода.

Гость
Имя

Пароль



Забыли пароль?
Запросите новый здесь
.
Coding Craft. Все права защищены © 2011. Проект Инициативного Народного Фронта Образования - ИНФО-проект.