DRAKON.SU

Текущее время: Понедельник, 23 Июль, 2018 01:23

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 53 ]  На страницу 1, 2, 3  След.
Автор Сообщение
 Заголовок сообщения: Попытка нарисовать рекурсию
СообщениеДобавлено: Воскресенье, 08 Ноябрь, 2009 16:40 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 3757
Откуда: Москва
Вопрос. Как выбрать графические средства для отображения рекурсии?
Ответ. Предлагается использовать две иконы комментарий. Первая икона устанавливается до начала рекурсии. В иконе большими буквами пишут «Начало рекурсии».
Вторая икона устанавливается после конца рекурсии. В иконе большими буквами пишут «Конец рекурсии».

Мое предложение может быть неудачным или ошибочным.
Просьба исправить мои ошибки и предложить удовлетворительное решение.

___________________________________________

Далее следуют две части.

Часть 1 — это просто цитата из сети.
Часть 2 — это рисунок, который я предлагаю в качестве решения.

Примечание. Часть 2 опирается на Часть 1.

ЧАСТЬ 1

Цитата:
По правилам языка Паскаль, задающим область действия определений, тело подпрограммы может содержать вызовы подпрограмм, заголовки которых записаны выше в тексте программы.
Отсюда вытекает, что подпрограмма может содержать вызовы самой себя – рекурсивные вызовы.

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

Пример 6
Напишем рекурсивную функцию f по такому определению функции факториал:
n!=n*(n-1)! при n>1, 1!=1 (считается, что n>0).

function f(n:integer):integer;
begin
if n=1 then f:=1
else f:=n*f(n-1)
end;

http://works.tarefer.ru/69/100896/index.html


ЧАСТЬ 2


Вложения:
Комментарий к файлу: Рекурсивная функция "Вычисление факториала"
. Рекурсия Факториал.png
. Рекурсия Факториал.png [ 28.01 КБ | Просмотров: 5286 ]


Последний раз редактировалось Владимир Паронджанов Вторник, 10 Ноябрь, 2009 14:47, всего редактировалось 4 раз(а).
Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Попытка нарисовать рекурсию
СообщениеДобавлено: Воскресенье, 08 Ноябрь, 2009 19:12 

Зарегистрирован: Воскресенье, 04 Ноябрь, 2007 23:01
Сообщения: 512
На картинке подправить бы:
f=n!=n*(n-1)!
и
f:=n*f(n-1)

В рамках процедурной парадигмы, по-моему, гораздо большего внимания, чем рекурсия, заслуживает вопрос повторных вхождений(reentrant functions). Как вариант, предлагаю вызов "f:=n*f(n-1)" оформить вставкой и заголовок "вычисление факториала f" соединять с нижней иконой несколькими вертикальными линиями, а не одной. Это позволит не загромождать алгоритм комментариями, но при этом графически отметить существенные особенности реализации.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Попытка нарисовать рекурсию
СообщениеДобавлено: Воскресенье, 08 Ноябрь, 2009 20:37 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 3757
Откуда: Москва
Формулы исправил. Спасибо.
Остальной текст, к сожалению, не понял.

Я не понял Вашу идею. Вы хотите убрать комментарии? Но тогда мы будем проигрывать
в понятности.
Или, может быть, Вы хотите ввести графическое изображение для реентерабельных
функций? Если да, я не понял, как это можно сделать.

Неколько вертикальных линий мне не очень понравились. Что они должны выражать?
Кроме того, не понял, какие иконы должны соединять эти вертикальные линии.

Большое спасибо за Ваши замечания


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Попытка нарисовать рекурсию
СообщениеДобавлено: Воскресенье, 08 Ноябрь, 2009 21:14 

Зарегистрирован: Воскресенье, 04 Ноябрь, 2007 23:01
Сообщения: 512
Вложение:
fact_mod.png
fact_mod.png [ 8.19 КБ | Просмотров: 5429 ]
Использовать при этом комментарии или нет - дело вкуса и принятых соглашений о стиле. Вертикальные линии после заголовка могли бы обозначать,что функция спроектирована с учётом возможности повторных вхождений.

недостаток: используемые обозначения, равно как и комментарии, трудно применить для автоматической верификации. А если та же рекурсия "размазана" на две или более процедуры, то и вообще бесполезны


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Логика изложения темы "Рекурсия"
СообщениеДобавлено: Понедельник, 09 Ноябрь, 2009 09:58 

Зарегистрирован: Понедельник, 23 Март, 2009 10:35
Сообщения: 12
Откуда: Ханты-Мансийск
Преподавание, иногда, позволяет уяснить суть затруднений. Известно, например, что полиглот из Венгрии Като Ломб для изучения очередного языка устраивалась в университете его преподавателем. Впрочем, положительная динамика не гарантируется.

Вариант последовательности изложения темы "Рекурсия" внутри темы "Вспомогательный алгоритм" выглядит примерно так.

  1. Первый уровень (Знакомство)
    Приводится пример "дурной" рекурсии:
    Код:
    алг звёздочка
    нач
    ... опустить_перо
    ... вперёд(10)
    ... поворот(170)
    ... звёздочка
    кон

    Обратите внимание - поведение Исполнителя "изображает" рекурсию.
  2. Второй уровень (Понимание)
    В алгоритм добавляется проверка условий. Показывается принципиальное достижение конца самовызовов.
    Рекурсию иллюстрируют вписыванием текста в текст.
  3. Третий уровень (Усвоение)
    Алгоритм вычисления факториала в трёх вариантах.
    Для факториала третьим показывается вариант с выведением функции из формулы (с накоплением результата, без откладывания операций).
    Код:
    цел алг FP(цел N, R)
    нач
    ... если N = 0
    ..... то знач := R
    ..... иначе знач := FP(N -1, R * N )
    ... всё
    кон

    FP(3,1) = FP(2, 3*1) = FP(1, 2*3) = FP(0, 6) = 6
    В методе накапливающего параметра есть важная аналогия с инвариантом цикла: аргумент N и накопитель R меняются согласованно.
  4. Четвёртый уровень (Овладение)
    Система самовызовов, образующая дерево.
    Задача. Вычислить сумму элементов таблицы, не пользуясь циклами.
    Идея метода. Разбивать таблицу на примерно равные части вплоть до части из одного элемента и только тогда суммировать.
    Код:
    вещ алг сумма(цел L, P)
    дано ! вещ таб A[1:N]
    надо ! R = сумма элементов от A[L] до A[P] включительно
    цел C
    нач
    ... если L = P
    ..... то знач := A[L]
    ..... иначе
    ....... C := INT((L+P) / 2)
    ....... знач := сумма(L, C) + сумма(C+1, P)
    ... всё
    кон
По Бочкин А.И. Методика преподавания информатики. - Мн.: Вышэйшая школа, 1998.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 09 Ноябрь, 2009 10:10 
Аватара пользователя

Зарегистрирован: Среда, 29 Март, 2006 12:09
Сообщения: 15
Дмитрий Колосов писал(а):
Четвёртый уровень (Овладение)

Haskell просматривается и вообще ФП.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Попытка нарисовать рекурсию
СообщениеДобавлено: Понедельник, 09 Ноябрь, 2009 10:13 

Зарегистрирован: Понедельник, 23 Март, 2009 10:35
Сообщения: 12
Откуда: Ханты-Мансийск
Владимир Паронджанов писал(а):
Вопрос. Как выбрать графические средства для отображения рекурсии?


Может быть, затруднение носит принципиальный характер: графическая демонстрация идеи хранимой программы?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Попытка нарисовать рекурсию
СообщениеДобавлено: Понедельник, 09 Ноябрь, 2009 12:17 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 3757
Откуда: Москва
Рэйлвэй Каген писал(а):
На картинке подправить бы:
f=n!=n*(n-1)!
и
f:=n*f(n-1)

...Как вариант, предлагаю вызов "f:=n*f(n-1)" оформить вставкой ...


Да, конечно, здесь должна быть икона "вставка" (а не действие)

Я исправил в рисунке все, что выделено в цитате.

Рисунок исправлен в двух местах:

1. В моем первом сообщении

2. Исправления в рисунке продублированы для удобства в данном сообщении

Вложение:
. Рекурсия Факториал.png
. Рекурсия Факториал.png [ 28.01 КБ | Просмотров: 5287 ]


Уважаемый Рэйлвэй Каген!

С Вашего разрешения попробую обосновать свою позицию
(без претензий на четкость доказательств).

:!: 1. Ваш тезис.

Цитата:
Вы пишете «Вертикальные линии после заголовка могли
бы обозначать, что функция спроектирована с учётом возможности
повторных вхождений»


Понимаю Вас. Да, действительно предлагаемые Вами вертикальные
линии говорят о повторных вхождениях.

Мое возражение: Вы вводите в графический алфавит НОВЫЙ символ —
4 вертикальные линии, которые используются только в очень
узкой сфере применения — для учета возможности повторных
вхождений.

Моя позиция такова: не хорошо вводить новый символ для узкой
сферы применения. Гораздо лучше использовать
УНИВЕРСАЛЬНУЮ (и всем понятную) икону комментарий,
как показано на рисунке.

:!: 2. Ваш тезис.

Цитата:
Вы пишете «Использовать при этом комментарии или нет -
дело вкуса и принятых соглашений о стиле».


Мое возражение. Если использование иконы «комментарий»
позволяет уменьшить длину графического алфавита (и не вводить
новый символ — 4 вертикальные линии, которые используются
только в очень УЗКОЙ сфере применения), то комментарий лучше,
чем новый символ.

:idea: ОБСУЖДЕНИЕ НЕДОСТАТКА :idea:

:!: 3. Ваш тезис.

Цитата:
Вы пишете: недостаток: используемые обозначения, равно
как и комментарии, трудно применить для автоматической
верификации.


Мой вопрос. Можно ли устранить или ослабить этот недостаток. Если да,
как это сделать? Каковы Ваши предложения?

:!: 4. Ваш тезис.

Цитата:
Вы пишете: «А если та же рекурсия "размазана" на две или более
процедуры, то и вообще бесполезны».


Моя просьба. Из-за недостатка знаний мне трудно представить себе ситуацию,
описанную в Вашем 4-м тезисе.

У меня большая просьба. Если Вас не очень затруднит, пожалуйста,
нарисуйте дракон-схему, в которой рекурсия "размазана"
на две или более процедуры.

Такой рисунок полезен тем, что он наглядно покажет, что
«меры борьбы» в данном случае «вообще бесполезны».

А вдруг что-нибудь получится (хотя бы частично?)


Последний раз редактировалось Владимир Паронджанов Вторник, 10 Ноябрь, 2009 14:58, всего редактировалось 2 раз(а).

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Попытка нарисовать рекурсию
СообщениеДобавлено: Понедельник, 09 Ноябрь, 2009 13:58 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 3757
Откуда: Москва
Я начал эту тему с вопроса:
Как выбрать графические средства для отображения рекурсии?

Почему меня интересует этот вопрос?
Ответить не трудно.

Когда я делал доклад на кафедре прикладной математики МЭИ,
мне задали вопрос:
Как изобразить рекурсию на Драконе?

Уменя не было готового ответа.
Я никогда раньше об этом не думал.

И я ответил так. На языке дракон рекурсия отображается как обычно --
в текстовом виде.

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

Появление таких вопросов говорит о том, что
ЛЮДИ ЖДУТ, ЧТО ВИЗУАЛЬНЫЙ ЯЗЫК ДРАКОН ДОЛЖЕН ИМЕТЬ
ГРАФИЧЕСКИЕ СРЕДСТВА ДЯ ИЗОБРАЖЕНИЯ РЕКУРСИИ.

Конечно, можно проигнорировать такие вопросы.
Но мне кажется, что графическое изображение рекурсии
было бы полезно.

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

Я благодарен Рэйлвэю Кагену, который указал на ошибки.
Я благодарен также Илье Ермакову, который также указал на ошибки.

Но вопрос еще не закрыт. Мой рисунок отражает мою позицию.
Рэйлвэй Каген и Илья Ермаков имеют несколько иную позицию.

Еще раз всем большое спасибо за критику. Мой рисунок не претендует
на исчерпывающее решение. Пока что это всего лишь проба пера.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Попытка нарисовать рекурсию
СообщениеДобавлено: Понедельник, 09 Ноябрь, 2009 15:36 

Зарегистрирован: Воскресенье, 04 Ноябрь, 2007 23:01
Сообщения: 512
Если попроще, то приблизительно такое встретилось в рефдесах одной уважаемой фирмы(конечно, не Дракон-схема, а идея..). Смысл был в том, что устройство может исполнять некий командный файл, строки которого, в свою очередь, могут являться вызовами других командных файлов. В принципе, с такой штукой даже "Булава" может не полететь :)
Вложение:
cmd_parser_mod.png
cmd_parser_mod.png [ 16.76 КБ | Просмотров: 5360 ]
Если откомментировать по Вашему варианту, то получится вроде как две(?) рекурсии. Наверное, это неправильно. Поскольку это два проявления одной и той же сущности.

Чуть посложнее - разбор EBNF рекурсивным спуском от Евгения Темиргалеева.

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

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

Где же всё-таки искать ответ на Ваш вопрос? Думаю, что в преобразовании Дракон-схема<->граф-схема.
Вложение:
Комментарий к файлу: (упрощённо)
cmd_parser_t.png
cmd_parser_t.png [ 4.43 КБ | Просмотров: 5348 ]


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Попытка нарисовать рекурсию
СообщениеДобавлено: Понедельник, 09 Ноябрь, 2009 16:52 

Зарегистрирован: Понедельник, 30 Июль, 2007 10:53
Сообщения: 112
Откуда: Беларусь, Минск
С помощью конечного автомата нельзя изобразить рекурсию.

Обычным способом.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Попытка нарисовать рекурсию
СообщениеДобавлено: Понедельник, 09 Ноябрь, 2009 18:48 

Зарегистрирован: Среда, 30 Сентябрь, 2009 14:45
Сообщения: 10
1. Маленькое замечание. В операторе выбора надо писать не "n:= 1", a "n=1".
2. Сомнение. Возможно основной вариант это "n>1", хотя это не принципиально.
3. Дополнение в тему. Рекурсия может содержать также 2 и более взаимных вызовов, и такой вариант тоже должен быть учтен.
4. Рассуждение. По смыслу, рекурсия - это прерывание вычисления кода, запоминание состояния и повторное вычисление при некоторой модификации данных, пока некоторый параметр не достигнет конечного значения (в данном случае, пока n не станет равным 1).
Таким образом, для визуального восприятия требуется:
а) показать повторный вход (стрелку назад?) на часть охватываемую рекурсией;
б) показать множественность состояний... (возможно наложением прямоугольников со сдвигом).
Вообще говоря, рекурсия должна графически быть похожа на итерацию, но отличаться намеком на стек... (в котором хранятся состояния).


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Попытка нарисовать рекурсию
СообщениеДобавлено: Понедельник, 09 Ноябрь, 2009 18:55 
Аватара пользователя

Зарегистрирован: Среда, 29 Март, 2006 12:09
Сообщения: 15
Виктор О писал(а):
Вообще говоря, рекурсия должна графически быть похожа на итерацию, но отличаться намеком на стек... (в котором хранятся состояния).

Может вставка с параметрами, как у иконы "начало" (если я правильно все помню)? Ведь это же, фактически, вызов процедуры. Ну вот пусть это и будет честным вызовом процедуры. Там же только параметры другие по отношению к коду самой процедуры.
Или слово "процедура" в данном контексте не используется принципиально?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Попытка нарисовать рекурсию
СообщениеДобавлено: Понедельник, 09 Ноябрь, 2009 19:11 

Зарегистрирован: Воскресенье, 04 Ноябрь, 2007 23:01
Сообщения: 512
2 Виктор О, Димыч:
Может и пойдёт для прямой рекурсии, где функция сама себя вызывает. Но чаще встречается косвенная рекурсия, да ещё и база рекурсии (набор параметров) динамической может быть..

В Стэнфорде рекурсию рисуют так: http://www-formal.stanford.edu/jmc/recursive/node6.html


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Попытка нарисовать рекурсию
СообщениеДобавлено: Понедельник, 09 Ноябрь, 2009 19:52 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 631
Откуда: Россия, Орёл
Не, а зачем обязательно рисовать?

Чем текстовая связанность, по имени вызова, не устраивает?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Попытка нарисовать рекурсию
СообщениеДобавлено: Понедельник, 09 Ноябрь, 2009 20:04 

Зарегистрирован: Воскресенье, 04 Ноябрь, 2007 23:01
Сообщения: 512
Видать назрело противоречие между декларированной визуальной доступностью маршрутной информации и необходимостью вчитываться в вызовы, чтобы усвоить дополнительную текстовую связность.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Попытка нарисовать рекурсию
СообщениеДобавлено: Понедельник, 09 Ноябрь, 2009 20:07 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 631
Откуда: Россия, Орёл
Ну дык эта... Чувство меры надо иметь.
А то можно далеко зайти. И получить вместо сбалансированного клинка что-то совсем странное.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Попытка нарисовать рекурсию
СообщениеДобавлено: Понедельник, 09 Ноябрь, 2009 20:19 

Зарегистрирован: Суббота, 16 Февраль, 2008 07:58
Сообщения: 230
Откуда: Россия, Стерлитамак
А может быть такое решение (по аналогии с переходом на ветки правее)?
1) Темный низ/верх у иконы "Вставка"
2) Темный верх/низ у иконы "Заголовок

Чисто для того, чтобы выделить, что рекурсивный вызов. Можно еще какие-либо отличия применить именно к этим двум иконам.

Таким образом, при взгляде на обе иконы сразу будет понятно, что рекурсия, ну и соответственно читать надо будет, только чтобы маршрут определить (для веток правее, которые образуют цикл, точно также получается)


Последний раз редактировалось adva Понедельник, 09 Ноябрь, 2009 20:29, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Попытка нарисовать рекурсию
СообщениеДобавлено: Понедельник, 09 Ноябрь, 2009 20:20 

Зарегистрирован: Воскресенье, 04 Ноябрь, 2007 23:01
Сообщения: 512
Илья Ермаков писал(а):
..получить вместо сбалансированного клинка что-то совсем странное.
Сюрикен, да? :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Попытка нарисовать рекурсию
СообщениеДобавлено: Понедельник, 09 Ноябрь, 2009 20:26 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 631
Откуда: Россия, Орёл
"Испортим харошую вэщь...." (С)


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 53 ]  На страницу 1, 2, 3  След.

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2008-2018, участники конференции «DRAKON.SU», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB