DRAKON.SU
https://forum.drakon.su/

Попытка нарисовать рекурсию
https://forum.drakon.su/viewtopic.php?f=62&t=2026
Страница 1 из 3

Автор:  Владимир Паронджанов [ Воскресенье, 08 Ноябрь, 2009 16:40 ]
Заголовок сообщения:  Попытка нарисовать рекурсию

Вопрос. Как выбрать графические средства для отображения рекурсии?
Ответ. Предлагается использовать две иконы комментарий. Первая икона устанавливается до начала рекурсии. В иконе большими буквами пишут «Начало рекурсии».
Вторая икона устанавливается после конца рекурсии. В иконе большими буквами пишут «Конец рекурсии».

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

___________________________________________

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

Часть 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 КБ | Просмотров: 18694 ]

Автор:  Рэйлвэй Каген [ Воскресенье, 08 Ноябрь, 2009 19:12 ]
Заголовок сообщения:  Re: Попытка нарисовать рекурсию

На картинке подправить бы:
f=n!=n*(n-1)!
и
f:=n*f(n-1)

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

Автор:  Владимир Паронджанов [ Воскресенье, 08 Ноябрь, 2009 20:37 ]
Заголовок сообщения:  Re: Попытка нарисовать рекурсию

Формулы исправил. Спасибо.
Остальной текст, к сожалению, не понял.

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

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

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

Автор:  Рэйлвэй Каген [ Воскресенье, 08 Ноябрь, 2009 21:14 ]
Заголовок сообщения:  Re: Попытка нарисовать рекурсию

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

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

Автор:  Дмитрий Колосов [ Понедельник, 09 Ноябрь, 2009 09:58 ]
Заголовок сообщения:  Логика изложения темы "Рекурсия"

Преподавание, иногда, позволяет уяснить суть затруднений. Известно, например, что полиглот из Венгрии Като Ломб для изучения очередного языка устраивалась в университете его преподавателем. Впрочем, положительная динамика не гарантируется.

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

  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 ]
Заголовок сообщения:  Re: Логика изложения темы "Рекурсия"

Дмитрий Колосов писал(а):
Четвёртый уровень (Овладение)

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

Автор:  Дмитрий Колосов [ Понедельник, 09 Ноябрь, 2009 10:13 ]
Заголовок сообщения:  Re: Попытка нарисовать рекурсию

Владимир Паронджанов писал(а):
Вопрос. Как выбрать графические средства для отображения рекурсии?


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

Автор:  Владимир Паронджанов [ Понедельник, 09 Ноябрь, 2009 12:17 ]
Заголовок сообщения:  Re: Попытка нарисовать рекурсию

Рэйлвэй Каген писал(а):
На картинке подправить бы:
f=n!=n*(n-1)!
и
f:=n*f(n-1)

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


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

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

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

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

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

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


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

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

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

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


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

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

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

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

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


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

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

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

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


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

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

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


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

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

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

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

Автор:  Владимир Паронджанов [ Понедельник, 09 Ноябрь, 2009 13:58 ]
Заголовок сообщения:  Re: Попытка нарисовать рекурсию

Я начал эту тему с вопроса:
Как выбрать графические средства для отображения рекурсии?

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

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

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

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

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

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

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

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

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

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

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

Автор:  Рэйлвэй Каген [ Понедельник, 09 Ноябрь, 2009 15:36 ]
Заголовок сообщения:  Re: Попытка нарисовать рекурсию

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

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

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

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

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

Автор:  Valery Solovey [ Понедельник, 09 Ноябрь, 2009 16:52 ]
Заголовок сообщения:  Re: Попытка нарисовать рекурсию

С помощью конечного автомата нельзя изобразить рекурсию.

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

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

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

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

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

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

Автор:  Рэйлвэй Каген [ Понедельник, 09 Ноябрь, 2009 19:11 ]
Заголовок сообщения:  Re: Попытка нарисовать рекурсию

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

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

Автор:  Илья Ермаков [ Понедельник, 09 Ноябрь, 2009 19:52 ]
Заголовок сообщения:  Re: Попытка нарисовать рекурсию

Не, а зачем обязательно рисовать?

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

Автор:  Рэйлвэй Каген [ Понедельник, 09 Ноябрь, 2009 20:04 ]
Заголовок сообщения:  Re: Попытка нарисовать рекурсию

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

Автор:  Илья Ермаков [ Понедельник, 09 Ноябрь, 2009 20:07 ]
Заголовок сообщения:  Re: Попытка нарисовать рекурсию

Ну дык эта... Чувство меры надо иметь.
А то можно далеко зайти. И получить вместо сбалансированного клинка что-то совсем странное.

Автор:  adva [ Понедельник, 09 Ноябрь, 2009 20:19 ]
Заголовок сообщения:  Re: Попытка нарисовать рекурсию

А может быть такое решение (по аналогии с переходом на ветки правее)?
1) Темный низ/верх у иконы "Вставка"
2) Темный верх/низ у иконы "Заголовок

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

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

Автор:  Рэйлвэй Каген [ Понедельник, 09 Ноябрь, 2009 20:20 ]
Заголовок сообщения:  Re: Попытка нарисовать рекурсию

Илья Ермаков писал(а):
..получить вместо сбалансированного клинка что-то совсем странное.
Сюрикен, да? :)

Автор:  Илья Ермаков [ Понедельник, 09 Ноябрь, 2009 20:26 ]
Заголовок сообщения:  Re: Попытка нарисовать рекурсию

"Испортим харошую вэщь...." (С)

Страница 1 из 3 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/