Тоже пятничная задачка :о)

← →
McSimm © (2007-05-05 00:09) [80]

> Вы не верите что если неопытному в программировании студенту
> показать итеративный вариант и рекурсивный вариант ему не
> будет понятнее итеративный?

Понятнее что ?

← →
Rouse_ © (2007-05-05 00:09) [81]

> Если бы программист, работающий у меня, применял рекурсию
> для вычисления факториала, я бы нанял кого-то другого.

Я вот сидел и долго думал, а вот в каком ракусе тогда можно применить рекурсивный алгоритм в плане обучения? Я вот сидел и долго думал, а вот в каком ракусе можно описить "мощность" рекурсионного алгоритма? Я вот сидел и долго думал, а вот сколько у тебя сейчас работает програмистов? :)

← →
default © (2007-05-05 00:11) [82]

Rouse_ © (05.05.07 00:09) [81]
в ракурсе, например, поиска выхода в лабиринте
McSimm © (05.05.07 00:09) [80]
понять как оно работает или хотя бы что оно делает

← →
Rouse_ © (2007-05-05 00:13) [83]

> ракурсе, например, поиска выхода в лабиринте

Вах как... Занимательно... Вот при таком прямолинейном брутфорсном подходе следует задуматься о квалификации...

← →
McSimm © (2007-05-05 00:14) [84]

> default © (05.05.07 00:11) [82]

совсем не читаете что вам пишут.

Попробую перефразировать.
Как с помощью более понятного итеративного алгоритма объяснить принципы рекурсии ?

Или вы считаете, что в книгах по программированию учат факториалы вычислять?

← →
McSimm © (2007-05-05 00:16) [85]

> рекурсивный вариант функции трудней для понимания (**чего?**),
> чем итеративный вариант:...

вот я и говорю - по ушам проехались.

← →
default © (2007-05-05 00:16) [86]

Rouse_ © (05.05.07 00:13) [83]
хм
у Вас есть сравнивая по понятности итеративная версия обхода лабиринта в поисках выхода?

← →
default © (2007-05-05 00:21) [87]

McSimm © (05.05.07 00:14) [84]
я всё понял
возможно тут автора обвинить в лёгком передёргивании, но вцелом он прав
не было бы никаких возмущений если бы в этих книгах говорилось, что это лишь как пример и что не стоит использовать такую рекурсию в реалных программах и почему и показывались всегда примеры того, где без рекурсии действительно сложно

← →
Rouse_ © (2007-05-05 00:21) [88]

> у Вас есть сравнивая по понятности итеративная версия обхода
> лабиринта в поисках выхода?

Конечно, это-же математическая модель... Зачем рукурсивно бить лбом поле в поисках выхода, если можно рассчитать нормали на основании векторов препятствий?

← →
default © (2007-05-05 00:25) [89]

Rouse_ © (05.05.07 00:21) [88]
и по понятности оно ничем не уступает?
но речь не об конкретике, может пример с лабиринтом и был не совсем удачным, вопрос в том чтобы показывать примеры рекурсии такие в которых без рекурсии было гораздо сложнее, непонятнее и тд

← →
Rouse_ © (2007-05-05 00:27) [90]

> вопрос в том чтобы показывать примеры рекурсии такие в которых
> без рекурсии было гораздо сложнее

Найти все *.avi на диске С - что может быть конкретней? :)

← →
default © (2007-05-05 00:30) [91]

Rouse_ © (05.05.07 00:27) [90]
вполне вариант, кто ж спорит
вот я спецом открыл щас одну книгу с разделом про рекурсию
там как раз Фибоначчи через рекурсию и итерацию
и сказано лишь, что с рекурсией - лаконичнее
так что Макконелл прав со своими обвинениями пусть и чуть-чуть перегибает

← →
Rouse_ © (2007-05-05 00:42) [92]

> Макконелл прав со своими обвинениями пусть и чуть-чуть перегибает

Рекурсия это билет в оба конца.

← →
Rouse_ © (2007-05-05 00:44) [93]

Да кстати, Сань, завязывай называть меня на Вы - чай не первый день на форуме :)

← →
Alx2 © (2007-05-05 01:11) [94]

Немного для мозга есть в другой в задачке:
Дан массив N чисел. Поставить меж этими числами знаки арифм. операций и скобки так, чтобы в результате получилось заранее заданное число M.

И что-б максимально просто и понятно. :)

← →
Зюзя (2007-05-05 04:11) [95]

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

Вычисление факториала с использованием рекурсии потому и учебный, что он легок для понимания. Так что, аргумент про "труднее" не принимается.

А насчет медленного выполнения и непредсказуемого использования, так это очень спорное утверждение.

Во-первых, потому что использование очень даже предсказуемое: для 64-битных вычислений максимальный результат при вычислении 65!, дальше - переполнение, что является ограничением для любого алгоритма (использование сверхбольших чисел и специальных алгоритмов не беру во внимание), а на 65 рекурсивных вызовах ничего непредсказуемого произойти не может.

А во-вторых, с такой позиции, увольнять надо любого, кто вообще для этого хоть какие-то алгоритмы использует, ибо для 65 чисел надо использовать заранее просчитанную табличку. И Range Check. И все. Никаких алгоритмов. И выполнение быстрое, и непредсказуемости никакой.

P.S. И запись в трудовой книжке: "Он не умел считать факториал"...

← →
Думкин © (2007-05-05 05:00) [96]

> для 64-битных вычислений максимальный результат при вычислении
> 65!,

Ни разу не так, обвал произойдет гораздо раньше.

← →
Зюзя (2007-05-05 05:19) [97]

Виндовый калькулятор работает с 8-байтными числами.
И функция факториала в нем есть.
Проверить можно.

← →
SerJaNT © (2007-05-05 07:44) [98]

<?php class chisla { var $num = array(); /** * Добавляем число * * @param integer $c */ function add( $c ) { if ( !is_float($c) ) { $this->num[] = $c; } } /** * Выводим * */ function show() { foreach ( array_reverse( $this->num ) AS $chislo) { if ( fmod( $chislo, 2) == 0 ) { print $chislo . "<br>"; } } } } $z = new chisla(); /** * Заполняем любыми числами */ $z->add(15); $z->add(5); $z->add(6); $z->add(-5.2); $z->add(7.88888); $z->add(0.9999); $z->add(1); $z->add(0.2); $z->add(-8); /** * Выводим числа по условию */ $z->show(); ?>

← →
GrayFace © (2007-05-05 11:20) [99]

То, что факториал в учебниках вычисляется с помощью рекурсии весьма вредно. После этого не задумываясь пишешь рекурсию когда нужен факториал и даже в голову не приходит сделать без нее. (так было на днях, правда, это было на олимпиаде, а там думать некогда, не до эффективности :) )

default © (04.05.07 19:57) [32]
рекурсия тут совсем ни к месту
keep it simple, stupid
а если брать стек и подобное, то уж лучше Insert в 0 позицию, что поймёт всяк и каждый
Зато рекурсия, в отличии от TStack, сохраняет эффективность проги.

Rouse_ c (05.05.07 00:21) [88]

> у Вас есть сравнивая по понятности итеративная версия обхода
> лабиринта в поисках выхода?

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

← →
GrayFace © (2007-05-05 11:22) [100]

Все зависит от того, что дальше с нормалями делать.

← →
Юрий Зотов © (2007-05-05 13:42) [101]

Вариант на PL/1. Прост до безобразия, потому что использует встроенные в сам язык стековые переменные. По той же причине не требует никаких дополнительных модулей, библиотек и т.п.

example: procedure options(main);
dcl I controlled;
on endfile(sysin)
begin
free(I);
goto L2;
end;
L1: allocate(I);
get list(I);
if I and 1 = 1 then free(I);
goto L1;
L2: do while(allocation(I));
put list(I);
free(I);
end;
end example;

Задачка в некоторой степени классическая и, имхо, довольно интересно посмотреть, как она решается разными средствами. Вариант [78] потряс меня своей лаконичностью, но что касается простоты - имхо, без бутылки в нем фиг разберешься.
:о)

← →
Думкин © (2007-05-06 05:05) [102]

> Зюзя (05.05.07 05:19) [97]

Ну так возьмите на себя труд и проверьте. :) Удивитесь.

> GrayFace © (05.05.07 11:20) [99]

Хотя я и знал, что "правильно" через рекурсию, но когда у меня на одном собеседовании возникла и эта задача, то я решил ее без оной. Что я читал не так? Видимо, читая надо видеть и еще что-то кроме фиги?
:)

> Юрий Зотов © (05.05.07 13:42) [101]

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

← →
GrayFace © (2007-05-07 01:25) [103]

Думкин © (06.05.07 5:05) [102]
Хотя я и знал, что "правильно" через рекурсию, но когда у меня на одном собеседовании возникла и эта задача, то я решил ее без оной.
Видимо на собеседовании была цель решить именно это задачу, а не побыстрее набить код чтоб работало.

← →
Думкин © (2007-05-07 05:32) [104]

> GrayFace © (07.05.07 01:25) [103]

Штука в том, что не факториал в учебниках вычисляют, а на его примере показывают суть рекурсии. Не более. Если это понимать, то проблем никаких не возникает.

> GrayFace © (07.05.07 01:25) [103]

Ведь есть классические задачи про трубы в которые втекает и вытекает и про лодки от города А до Б, но никто же не пользуется для реальных труб и транспортных средств подобными расчетами и ничего - Мир не рухнул.

Думкин, тут вопрос в том, что вычисление факториала через рекурсию мало что дает. Рекурсию-то он объясняет, но не объясняет ее возможностей и путей применения.
Это годится, как и бассейн с трубами, только для средних классов школы. Но никак не для серьезных учебников.

← →
mrco (2007-05-07 18:20) [108]

Что-то не видно моего любимого языка...

(print (reverse (loop while (numberp (setq r (read))) if (oddp r) collect r ) ) )

Сама задача абсурдная какая-то...
Читай ты данные в массив и выводи их с конца только четные.
А смысл данной задачи - за пределами моих умственных способностей.

> Romkin © (07.05.07 10:48) [106]

Ромкин, если дело ограничивается только факториалом - то другое дело. Но для ввода в понятие рекурсия - факториал вполне нормальный объект. В чем проблема? Я вот не пойму чем таким факториал перебежал дорогу рекурсии?

Тем, что факториал - концевая рекурсия. И легко разворачивается в цикл. И при этом создается впечатление, что рекурсия нафиг не нужна и заменяется циклом.
Почему не дать задачу, алгоритм с рекурсией для которой проще, чем без нее?

> Romkin © (08.05.07 11:35) [112]

А кто-то мешает потом и ее дать? Все-таки не вижу препятствий для иллюстрации ввода в рекурсивное через факториал. Но это уже по кругу.

> Почему не дать задачу, алгоритм с рекурсией для которой
> проще, чем без нее?

Это можно потом.
Наверное это тебе сейчас кажется все тривиальным. Хотя может ты и сразу вник. А я очень живо помню, как постигал рекурсию, как укладывал в своем представлении ее итерации. Это очень трудно в начале. И F(n)=n*F(n-1) мне очень помог, как и ряд других простых примеров, хорошо укладывающихся в воображении.

И ни капельки не помешал. Как только я прочувствовал этот метод (честно говоря я был восхищен им), начал испытывать его для совершенно разнообразных задач. (до сих пор помню свой восторг от простоты получившегося рекурсивного алгоритма решения ханойских башен из любого начального состояния.)

А уже понимание плюсов и минусов на порядок легче дается.

> А кто-то мешает потом и ее дать? Все-таки не вижу препятствий
> для иллюстрации ввода в рекурсивное через факториал. Но
> это уже по кругу.

Дык как правило не дают! :)

Тоже пятничная задачка :о) Найти похожие ветки