Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
End Function
Private Sub Command1_Click() Debug.Print Factorial(3) End Sub Что самое удивительное - функция работает! Несмотря на то, что в программе нигде не употребляется оператор цикла. Вся соль программы в том, что функция Factorial вместо этого включает в себя вызов самой себя - Factorial(N-1). : Что же происходит в компьютере во время выполнения программы? Механизм происходящего в точности соответствует нашему путешествию по ступенькам:
Все начинается с того, что мы щелкаем по кнопке и Visual Basic пробует выполнить строку Debug.Print Factorial(3). Для этого он вызывает функцию Factorial. Выполнение подпрограммы начинается с того, что в памяти отводится место для всех параметров и локальных переменных, а значит и для нашего параметра N. Затем число 3 подставляется на место параметра N, то есть в память в ячейку N посылается 3. Затем выполняется тело функции. Так как 3> 1, то Visual Basic пытается выполнить умножение 3* Factorial(3-1) и сталкивается с необходимостью знать значение функции Factorial(2), для чего вызывает ее, то есть отправляется ее выполнять, недовыполнив Factorial(3), но предварительно запомнив, куда возвращаться.
Спускаюсь на ступеньку ниже. В соседнем месте памяти отводится место для N. Это уже другое N, путать их нельзя! В эту ячейку N посылается 2. Затем выполняется тело функции. Пусть вас не смущает, что Visual Basic второй раз выполняет тело функции, не закончив его выполнять в первый раз. Так как 2> 1, то Visual Basic пытается выполнить умножение 2* Factorial(2-1) и сталкивается с необходимостью знать значение функции Factorial(1), для чего вызывает ее.
Спускаюсь еще на ступеньку. В соседнем месте памяти отводится место еще для одного N. В эту ячейку N посылается 1. Затем выполняется тело функции. Так как 1=1, то Visual Basic вычисляет Factorial=1. Вот - впервые конкретное число. Затем Visual Basic пытается выполнить следующую строку if N> 1 then Factorial = N* Factorial(N-1). Поскольку нельзя сказать, что 1> 1, то строка не выполняется и выполнение тела функции закончено. Значит можно подниматься.
Поднимаюсь на одну ступеньку. Visual Basic возвращается внутрь тела функции (той, где N=2) и успешно выполняет умножение - Factorial =2*1=2.
Поднимаюсь еще на ступеньку. Visual Basic возвращается внутрь тела функции (той, где N=3) и успешно выполняет умножение - Factorial =3*2=6. Задача решена.
Итак, рекурсией в программировании называется вызов подпрограммы из тела самой подпрограммы. Чем хорош рекурсивный стиль программирования? В нашей программе о факториале мы как бы и не программировали вовсе, а просто обяснили компьютеру, что такое факториал. Как бы перешли на новый уровень общения с компьютером: вместо программирования - постановка задачи. Чем плох рекурсивный стиль программирования? Если мы для решения той же задачи напишем программу не с рекурсией, а с обычным циклом, то такая программа будет выполняться быстрее и потребует меньше памяти.
Задание 131: Напишите рекурсивную функцию fib для вычисления чисел Фибоначчи.
|