Распечатка 2 иллюстрирует, как машинный учитель направляет программирование рекурсивной функции типа факториала какого-то числа — это одна из первых задач урока 7. Хотя у студента возникают некоторые трудности с синтаксисом условного теста в строках 1 и 2, в основном он верно указывает проверку условия окончания рекурсии.
Распечатка 2. Диалог, возникающий при определении функции fact для вычисления факториала числа
Определите функцию tact, имеющую один аргумент п н вычисляющую факториал n, который по определению есть результат умножения n х n-fxn—2...х1. Например, (fact 3)=3x2xl=6. По определению факториал 0 равен 1.
1. (defun fact(n)
(cond
((equal)
<ДЕЙСТВИЕ>)
<РЕКУРСИВНЫЙ-СЛУЧАЙ>))
Мне представляется, что вы пытаетесь проверить, не равен ли аргумент числу нуль. Для проверки эквивалентности нулю имеете специальная функция. Попробуйте воспользоваться ею вместо equal.
Какую программу вы можете написать для проверки выполнен условия завершения? Попробуйте использовать для этого нскоторый предикат.
2. (defun fact (n)
(cond
((zего<ДЕЙСТВИЕ>)
<РЕКУРСИВНЫЙ-СЛУЧАЙ>))
Может быть, вы имели в виду zerop (да или нет)? да
3. (defun fact (n)
(cond ((zerop n)l
>
<РЕКУРСИВНЫЙ-СЛУЧАЙ>))
Как вычисляется значение факториала в рекурсивных случаях?
|
НАЖМИТЕ ЕСЛИ ВЫ ХОТИТЕ | |
|
1 |
Путем рекурсивного обращения к функции fact с n |
|
2 |
Умножением n на faсt от n минус 1 |
|
3 |
Получая 1 2 ... и затем перемножая их |
|
4 |
Предоставить выбор учителю. |
Ваш выбор: 3
Это разумный способ вычисления факториала, но он не годится в качестве плана для рекурсивной функции. Поскольку у вас, очевидно, возникают трудности в рекурсивных случаях, просмотрим несколько примеров, чтобы выяснить, какими должны быть условия и действия для каждого из этих случаев.
Рекурсивное отношение — это отношение между функцией fact, вызванной с аргументом n, и fact, вызванной с аргументом:
|
НАЖМИТЕ ЕСЛИ ВЫ ХОТИТЕ | |
|
1 |
1 n минус 1. |
|
2 |
n равное 0. |
|
3 |
n плюс 1. |
|
4 |
Предоставить выбор учителю |
Ваш выбор: 1
Рассмотрим несколько конкретных примеров. Охарактеризуем рекурсивное отношение между fact, вызванной с 1. и функцией fact, вызванной с 0.
Каково значение (fact 1)? Ответ: 1
Каково значение (fact 0)? Ответ: 1
ПРИМЕРЫ
fact (n)
fact (n-1)
A. (fact
1)=1 (fact 0)=1
Рассмотрим другие конкретные примеры. Охарактеризуем рекурсивное отношение между fact, вызванной с аргументом 3, и fact, вызванной с аргументом 2.
Каково значение (fact 3)?
Ответ: 6
Каково значение (fact 2)?
Ответ: 2
ПРИМЕРЫ
fact
(n)
fact (n-1)
A. (fact 1)=l (fact
0)=1
В. (fact 3)=6 (fact 2)=2
Поскольку имеется только один рекурсивный случай, охарактеризованный рассмотренными выше примерами, условие в этом случае может быть просто взято в виде Т. Охарактеризуем действие в этом случае.
Что вы должны сделать в примерах А и В, чтобы получить результат для функции fact, вызванной с аргументом n?
|
НАЖМИТЕ ЕСЛИ ВЫ ХОТИТЕ | |
|
1 |
Умножить n на n без единицы. |
|
2 |
Умножить n на fact от n без единицы |
|
3 |
Добавить и к результату, даваемому fact, вызванной от n без единицы. |
|
4 |
Предоставить выбор учителю. |
Ваш выбор: 2
Мы проработали ряд примеров, которые иллюстрируют рекурсивное соотношение. Теперь вернемся к задаче построения программы на Лиспе, задающей такое рекурсивное соотношение.
4. (defun fact (n)
(cond ((zcrop n)
1)
(t(fact)))
В
какой-то момент вам потребуется fact, но сейчас вы хотите умножать.
5. (defun fact (n)
(cond
((zerop n)
1)
(t(times<ЧИСЛО> <ЧИСЛО 2>))))
С чего вы хотите начать?
|
НАЖМИТЕ ЕСЛИ ВЫ ХОТИТЕ | |
|
1 |
Написать программу для получения числового аргумента. |
|
2 |
Написать программу для получения рекурсивной части |
Ваш выбор: 1
6. (defun fact (n)
(cond
((zerop n)
1)
(t (times n(fact n)))))
В этом месте вы не можете просто поместить n. Что вам
нужно сделать, это отнять от n единицу.
7. (defun fact (n)
(cond
((zerop n)
I)
(t (times n (fact (difference))))))
Функция difference будет работать в этом
случае, но более уместно воспользоваться функцией subl, когда вы вычитаете 1 из
числа.
8. (defun fact (n)
(cond
((zerop n) I)
(t
(times n (fact (subl n))))))
Как правило, студенты не испытывают особых затруднений с условиями окончания, но сталкиваются с большими трудностями при организации рекурсии. Диалог после строки 3 показывает, как учитель руководит студентом при построении рекурсивной функции. Учитель подводит его к конструированию примеров отношений между fact(n) и fact(n-l), а затем просит студента выделить общее отношение. Перед строкой 4 в распечатке 2 на экране дисплея появляется следующая информация:
Что вы должны сделать в примерах А и В, чтобы получить результат для функции fact, вызванной с аргументом n?
|
НАЖМИТЕ ЕСЛИ ВЫ ХОТИТЕ | |
|
1 |
Умножить n на n без единицы. |
|
2 |
Умножить n на fact от n без единицы. |
|
3 |
Добавить n к результату, который даст fact, вызванная от n без единицы |
|
4 |
Предоставить выбор учителю. |
Ваш выбор: 2
ПРОГРАММА ДЛЯ
(defun fact (n)
(cond ((zerop
n)
1)
<РЕКУРСИВНЫЙ-СЛУЧАЙ>))
ПРИМЕРЫ
fact
(n)
fact (n-1)
A. (fact 1)=l (fact
0)=1
B. (fact 3)=6 (fact 2)=2
Диалог, идущий после этого, показывает две классические ошибки, которые допускают студенты при определении рекурсивных функций. Первая ошибка (в строке 4) состоит в непосредственном обращении к функции, без объединения рекурсивного обращения с другими элементами. Вторая ошибка (в строке 6) — рекурсивное обращение с тем же значением аргумента, а не с более простым.
Закончив этап программирования функции, студент переходит к окну Лиспа и экспериментирует с полученной функцией. Трассировка функции показывает вложенные рекурсивные вызовы и их результаты. В конце диалога, изложенного в распечатке 2, на экране дисплея возникает такая информация (вверху показана сама программа, внизу— результат ее трассировки).
...ЗАДАНИЕ ВЫПОЛНЕНО. НАПЕЧАТАЙТЕ NEXT, ЧТОБЫ ПРОДОЛЖИТЬ...
...ПРОВЕРКА ФУНКЦИЙ, КОТОРЫЕ ВЫ ОПРЕДЕЛИЛИ...
(defun fact
(n)
(cond ((zerop
n)
0
(t (times n (fact (subl n))))))
ОКНО ЛИСПА
= >(trace fact) (fact)
= >(fact 3)
1
<Вход> fact (3)
I 2
<Вход> fact (2)
I
3 <Вход> fact (1)
I 4
<Вход> fact
(0)
I 4
<Выход> fact 1
I 3
<Выход> fact 1
I 2 <Выход>
fact 2
1 <Выход> fact 6
6
