JavaScript Рекурсия
Всем Доброго времени суток !
Только недавно начал изучать ЯваСкрипт. Читал про рекурсию Вот пример:
function sumTo(n) {
if (n == 1) return 1;
return n + sumTo(n-1);
}
alert( sumTo(100) ); //5050
ретурн ведь возвращает значение обратно той функции которую вызывали, так почему когда функция доходит до значения 1 и она видит условие if: if (n == 1) return 1;она ведь должна возвратить 1 как написано по условию и тогда sumTo(100) будит равен 1 а не 5050. Приведу пример:
function sumTo(n) {
return 1;
}
alert( sumTo(4) );
Результат: 1 и не имеет значение какое число было в sumTo(число) Не могли бы вы объяснить как идёт процесс рекурсии пошагово, то есть всё подробно, куда retun передаёт значение, где хранятся значения когда функция запущена. |
Ну во-первых писать в пределах функции более одного return это по меньшей мере признак дурного тона. Из-за этого возникает путаница.
А во-вторых все верно, каждый вызов функции sumTo относится к предыдущему контексту, то есть образуется длинный ряд замыканий. В конце концов, когда рекурсия прерывается, попадая под условие выхода, все полученные ранее результаты выполнений всех итераций складываются. |
DreamTheater
Спасибо! Если у вас найдётся ссылочка по сабжу(мб в учебнике есть, я его весь не читал) буду очень рад! Просто хочется ещё более глубоко понимать данный вопрос, для созданий собственных функций такого типа. для меня просто это новая информация: все полученные ранее результаты выполнений всех итераций складываются. |
Цитата:
Тут же для каждого вызова создается новый кадр на стеке. Цитата:
Цитата:
|
Цитата:
Спасибо всем за помощь всё сало намного яснее ! |
Цитата:
|
Про один return на функцию это вы явно загнули.
|
немножко не из той оперы пример, но пусть будет
var num = 0;
function inc() {
return ++num;
}
alert( inc() + inc() + inc() );
|
Цитата:
nerv_, не понял |
Цитата:
|
Ещё один совсем не большой вопрос:
function pow(x, n) {
return (n != 1) ? x*pow(x,n-1) : x; // пока n!=1 сводить к n-1
}
alert( pow(2, 3) ); // 8
вот этот момент: x*pow(x,n-1) получается при первой инерации будит 2 * 2, 2 как же будит выглядеть выражение при второй или я допустил ошибку в первой? |
pow(2,3) = 2*pow(2,2)
pow(2,2) = 2*pow(2,1) pow(2,1) = 2 pow(2,3) = 2*pow(2,2) = 2*2*pow(2,1) = 2*2*2 |
Цитата:
Мне он напомнил такой :
var factorial = function factorial(i, a){
a = a || 1;
if(i < 2) {
return a;
}
return factorial(i - 1, a * i);
};
/*Д. Крокфорд, "JavaScript. Сильные стороны."*/
разница в : return n * factorial(n - 1); // обычная // vs return factorial(i - 1, a * i); // хвостовая я правильно понял? очень тонкая граница :) |
melky, я сам не понял :D Побуду кэп'ом:
Цитата:
|
Цитата:
Как говорится в википедии, в этом (не хвостово-рекурсивном) случае придётся после возвращения значения из рекурсивного вызова применить ещё и операцию сложения, а для этого нужно будет отмотать стек на пару кадров назад (на самом деле, нужно будет пройтись по всем кадрам, созданным в процессе рекурсивного "погружения"). |
function ale(n) {
n++;
return n;
}
alert(ale(3));
|
РАссмотрим действие программы в рамках 4 шагов
<script>
function sum(n) {
if(n == 1)
return 1;
else
return (n + sum(n-1));
//шаг 4. sum(4) = sum(3) + 4 = ??? Компьютер хочет решить sum(4),но для того чтобы его решить, нужно вызвать ту же функцию, но в шаге 3(sum3),
//шаг 3.sum(3) = sum(2) + 3 = 6 но для этого надо вызывать ту же функцию в шаге 2 (sum2)
//шаг 2.sum(2) = sum(1) + 2 = 3 , на шаге один зеркало в зеркале заканчивается, так как решение шага один однозначно указано и является 1( мы четко указали что sum(1) = 1 и никаких функций, чтобы его решить не нужно вызывать)
//, Итак, чтобы подсчитать результат 10, нужно решить функции со всеми n . Как зеркало в зеркале до определенного момента программа решает функции, одну рядом с другой(как бы одну вложенную в другую).Решив все шаги(вызвав все функции) до шага 1 компьютер возвращается к шагу 4 и выдает результат sum(4) = 10. Если бы sum(1) не был определен однозначно - зеркало в зеркале было бы бесконечно.
//теперь программа смогла решить, что sum(4) = sum(3) + 4 = 10
}
alert( sum(4) );
</script>
|
Цитата:
|
Кадры и зеркала стека кагбе намекают на длящееся правонарушение по статье "Падение нравственности".
Канонично вызов подпрограммы это прыжок (jump) процессора на команду расположенную по заданному компилятором адресу и обратный прыжок (jump) с того места, где подпрограмма кончается туда, откуда был осуществлен прыжок. Это самое место - адрес прыжка - и сохраняется в стеке, то есть специально выделенной под это дело памяти для хранения адресов команд возврата из подпрограммы. Правило использования стеком таково: последний адрес выбирается первым. При рекурсивном вызове в стек пишется один и тот же адрес - адрес вызываемой подпрограммы, в современной терминологии - функции. Нет никаких кадров и зеркал в стеке. Это не кино. В стеке - адреса и ничего кроме. |
Что касается технической реализации рекурсии, то надо же понимать что подпрограмма может "вернуть" результат своей работы только записав его в память по заранее известному адресу.
Вполне понятно что для каждого такого результата выделяется новая память, где данные хранятся вплоть до команды освобождения затребованной памяти. Следовательно в процессе вызова функции из функции - никакой разницы той же самой функции, или другой, которая хочет заюзать результат вызова предыдущей функции - результаты будут накапливаться и накапливаться пока функция вызывает функцию, в которой следует вызов функции и так далее. Это фаза заполнения стека. Использование накопленных результатов происходит после вызова последней функции (или последнего вызова функции). То есть в фазу выборки стека. Например var res = one().two().three().four().five(); Это не рекурсия, конечно, а то начнут тут некоторые кадры в зеркала бросаться. Такой код выполняется справа налево. Ну так вот, можете и рекурсию предствлять себе как выполнение с конца. |
Цитата:
--- По-русски на вике херная какая-то написана, читайте в оригинале http://en.wikipedia.org/wiki/Recursi...mputer_science |
| Часовой пояс GMT +3, время: 11:27. |