Поскольку речь пойдет о рекурсии, начну с конца — со списка использованной литературы:
1) Хорошая общая статья о рекурсии: habrahabr.ru/post/256351 (в ней автор говорит, что рекурсивный код легче для восприятия. Честно говоря, пока я не готов согласиться с таким выводом, именно поэтому появилась эта заметка).
2) Разбор работы рекурсии на “самом низком уровне”, тут много ассемблера, но всё достаточно понятно: club.shelek.ru/viewart.php?id=205 (особенно советую обратить внимание на тот момент, где идет речь об адресе возврата. Этот эпизод сильно облегчает понимание).
Лирическое отступление:
Данная статья настолько рекурсивная, что написана автором для самого автора, а также для тех пользователей, которые, как и автор, не уверены в стопроцентном понимании данной темы.
А теперь приступим.
Такой вот код генерации перестановок был найден мной на Stackovereflow. Памятуя о законе потери информации о том, что многие любят видеть всё в одной статье, перепечатаю код здесь (ссылка есть, алгоритм из учебника). На мой взгляд нижеприведенная конструкция имеет важную особенность – её очень легко понять и разобрать по кусочкам. Кроме того, скрипт можно значительно упростить, чтобы добраться до семечка – рекурсии. Начнём откусывать от кода.
Сам код:
function permute($str, $i, $n) { if ($i == $n) print "$str\n"; else { for ($j = $i; $j < $n; $j++) { swap($str, $i, $j); permute($str, $i + 1, $n); swap($str, $i, $j); // backtrack. } } } // function to swap the char at pos $i and $j of $str. function swap(&$str, $i, $j) { $temp = $str[$i]; $str[$i] = $str[$j]; $str[$j] = $temp; } $str = "0123"; permute($str, 0, strlen($str)); // call the function.
Время выполнения исходного скрипта для n = 9: 4.14418798685 .
Исходный код выводит перестановки почти в лексикографическом порядке, а хотелось бы строго в нём.
Приступим к декомпозиции.
Откусим второй вызов функции обмена – swap
Смысл второго вызова, в том, чтобы за один цикл сделать два обмена.
Но почему два счётчика, шеф?!
Количество циклов от этого не сокращается, только увеличивается количество операций.
Откусываем… и вдруг чудо! Вывод перестановок теперь в лексикографическом порядке.
А для одного вызова swap с тем же n = 9 время выполнения =2.76783800125.
Отмечу, что разница заметна даже для n = 8. Отлично!
Чего бы с какой бы стороны еще откусить?
Откусим вызов функции и отправим операции обмена прямо в цикл.
function permute($str,$i,$n) { if ($i == $n) print “$str<br/>”; else { for ($j = $i; $j < $n; $j++) { $temp = $str[$i]; $str[$i] = $str[$j]; $str[$j] = $temp; permute($str, $i+1, $n); } } } $str = “123”; permute($str,0,strlen($str)); Да как же ж так можно?! Да где же это видано, чтобы функции брали и откусывали?!
Если Вы когда-нибудь покупали подержанный автомобиль на рынке, то часто на свои замечания по поводу состояния машины могли слышать фразу: «Э, брат, на скорость не влияет!»
А вот и нет! Все-таки влияет. И пролить свет на это может статья по второй ссылке.
Результат времени выполнения нашего огрызка улучшился. 1.91801601648.
А код теперь совсем как на ладони.
Уберём единственную проверку из функции. Вывода станет заметно больше, (немножко припевов/повторов скрасит путь к рекурсии). При n = 9 с выводом в браузер уже возникают проблемы. И это всего лишь при 986409 циклах. Здесь уместно вызвать функцию напоминания напомнить про ссылку на первую статью.
Но мы добрались до главного, до нашего семечка — рекурсии. Посмотрим, какие значения принимают переменные i и j. К этому мы и подбирались.
Я думаю, момент с изменениями значений переменных и есть основная трудность в понимании рекурсивного алгоритма перестановок. Уберём вывод и обмен, сократим n до 2.
Но как же понять, что происходит с переменными?!
Напечатаем их в цикле. Добавим в цикл для наглядности вывод i и j:
function permute($str,$i,$n) { for ($j = $i; $j < $n; $j++) { echo ‘i=’.$i.’ j=’.$j.'<br/>’; permute($str, $i+1, $n); } } $str = “01”; permute($str,0,strlen($str)); Получим вот такой вывод:
i=0 j=0 i=1 j=1 i=0 j=1 i=1 j=1 В котором всё сразу становится понятно. Так и хочется назвать это таблицей истинности.
Наш взгляд, привыкший к циклическим выводам, “запутывается в листьях и ветках”.
Только веток у нас всего две, так что постараемся выбраться.
На самом деле все не просто, а очень просто: там где i =0 – это первая ветка, т.е. i =0 j=0 и i=0 j=1 – это первый вызов функции – наш ствол. Но поскольку вся программа рекурсивная, то при n = 2 вывод естественно через строчку.
А если n будет больше?
Тогда вначале мы увидим кусочек нашего ствола (i=0), а потом листья, листья, листья и где-то через n+x строчек снова мелькнет наш ствол. При выводе это может создать путаницу.
Заметим также в случае с перестановками, что поскольку в самом начале j принимает значение i, то на первых этапах выполнения программы видимой транспозиции элементов не происходит, хотя фактически обмен выполняется.
Какой же из всего этого вывод?
А вывод уже был в конце статьи, что по первой ссылке в начале этой заметки.: )
В итоге
Мы сумели осуществить несколько задач: сократить исходный скрипт, провести некоторые тесты скорости. Вернуть перестановкам истинный порядок. И, надеюсь, сумели разобраться с рекурсией. Можно было бы еще для наглядности нарисовать рекурсивное древо, но оставлю это на долю воображения читателя. Напоследок напомню про вторую ссылку в начале заметки, для совсем бесповоротного понимания рекурсивных перестановок можно данный код использовать в качестве примера при работе с указанной материалом.
ссылка на оригинал статьи http://habrahabr.ru/post/275331/
Добавить комментарий