Javascript.RU

Создать новую тему Ответ
 
Опции темы Искать в теме
  #11 (permalink)  
Старый 06.05.2012, 16:25
Новичок на форуме
Отправить личное сообщение для S.D.Maquis Посмотреть профиль Найти все сообщения от S.D.Maquis
 
Регистрация: 23.10.2011
Сообщений: 9

Ещё один совсем не большой вопрос:
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
как же будит выглядеть выражение при второй или я допустил ошибку в первой?
Ответить с цитированием
  #12 (permalink)  
Старый 06.05.2012, 16:35
Аватар для Gvozd
Матрос
Отправить личное сообщение для Gvozd Посмотреть профиль Найти все сообщения от Gvozd
 
Регистрация: 04.04.2008
Сообщений: 6,246

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
Ответить с цитированием
  #13 (permalink)  
Старый 06.05.2012, 17:06
sinistral
Посмотреть профиль Найти все сообщения от melky
 
Регистрация: 28.03.2011
Сообщений: 5,418

Сообщение от B@rmaley.e><e Посмотреть сообщение
Сами-то статью читали?
Быстро оглядел, но не вчитывался в код.

Мне он напомнил такой :
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); // хвостовая

я правильно понял?
очень тонкая граница
Ответить с цитированием
  #14 (permalink)  
Старый 06.05.2012, 18:52
Аватар для nerv_
junior
Отправить личное сообщение для nerv_ Посмотреть профиль Найти все сообщения от nerv_
 
Регистрация: 29.11.2011
Сообщений: 3,924

melky, я сам не понял Побуду кэп'ом:
Цитата:
Хвостовая рекурсия — специальный случай рекурсии, при котором рекурсивный вызов функцией самой себя является её последней операцией.
__________________
Чебурашка стал символом олимпийских игр. А чего достиг ты?
Тишина - самый громкий звук
Ответить с цитированием
  #15 (permalink)  
Старый 06.05.2012, 18:53
Аватар для B@rmaley.e><e
⊞ Развернуть
Отправить личное сообщение для B@rmaley.e><e Посмотреть профиль Найти все сообщения от B@rmaley.e><e
 
Регистрация: 11.01.2010
Сообщений: 1,810

Сообщение от melky
я правильно понял?
Да.
Как говорится в википедии, в этом (не хвостово-рекурсивном) случае придётся после возвращения значения из рекурсивного вызова применить ещё и операцию сложения, а для этого нужно будет отмотать стек на пару кадров назад (на самом деле, нужно будет пройтись по всем кадрам, созданным в процессе рекурсивного "погружения").

Последний раз редактировалось B@rmaley.e><e, 06.05.2012 в 18:56.
Ответить с цитированием
  #16 (permalink)  
Старый 06.05.2012, 20:49
Аспирант
Посмотреть профиль Найти все сообщения от adik7960
 
Регистрация: 11.03.2012
Сообщений: 58

function ale(n) {
  n++;
  return n;
}
alert(ale(3));
Ответить с цитированием
  #17 (permalink)  
Старый 02.04.2014, 02:41
Новичок на форуме
Отправить личное сообщение для muzima Посмотреть профиль Найти все сообщения от muzima
 
Регистрация: 02.04.2014
Сообщений: 1

РАссмотрим действие программы в рамках 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>

Последний раз редактировалось muzima, 02.04.2014 в 02:46.
Ответить с цитированием
  #18 (permalink)  
Старый 02.04.2014, 09:26
Аватар для ksa
ksa ksa вне форума
CacheVar
Отправить личное сообщение для ksa Посмотреть профиль Найти все сообщения от ksa
 
Регистрация: 19.08.2010
Сообщений: 14,118

Сообщение от DreamTheater
Ну во-первых писать в пределах функции более одного return это по меньшей мере признак дурного тона. Из-за этого возникает путаница.
Всегда интересовало, кто вообще задает этот "тон" с одним return?
Ответить с цитированием
  #19 (permalink)  
Старый 02.04.2014, 15:59
Профессор
Отправить личное сообщение для kostyanet Посмотреть профиль Найти все сообщения от kostyanet
 
Регистрация: 23.10.2010
Сообщений: 2,718

Кадры и зеркала стека кагбе намекают на длящееся правонарушение по статье "Падение нравственности".

Канонично вызов подпрограммы это прыжок (jump) процессора на команду расположенную по заданному компилятором адресу и обратный прыжок (jump) с того места, где подпрограмма кончается туда, откуда был осуществлен прыжок. Это самое место - адрес прыжка - и сохраняется в стеке, то есть специально выделенной под это дело памяти для хранения адресов команд возврата из подпрограммы. Правило использования стеком таково: последний адрес выбирается первым.

При рекурсивном вызове в стек пишется один и тот же адрес - адрес вызываемой подпрограммы, в современной терминологии - функции.

Нет никаких кадров и зеркал в стеке. Это не кино. В стеке - адреса и ничего кроме.
Ответить с цитированием
  #20 (permalink)  
Старый 02.04.2014, 16:13
Профессор
Отправить личное сообщение для kostyanet Посмотреть профиль Найти все сообщения от kostyanet
 
Регистрация: 23.10.2010
Сообщений: 2,718

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

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

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

Использование накопленных результатов происходит после вызова последней функции (или последнего вызова функции). То есть в фазу выборки стека.

Например

var res = one().two().three().four().five();

Это не рекурсия, конечно, а то начнут тут некоторые кадры в зеркала бросаться. Такой код выполняется справа налево. Ну так вот, можете и рекурсию предствлять себе как выполнение с конца.

Последний раз редактировалось kostyanet, 02.04.2014 в 16:17.
Ответить с цитированием
Ответ



Опции темы Искать в теме
Искать в теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Книга: JavaScript. Сильные стороны Magneto Учебные материалы 16 21.04.2013 15:28
Первый Moscow JavaScript Meetup korenyushkin Общие вопросы Javascript 0 26.07.2011 15:23
Последние книги по JavaScript! monolithed Учебные материалы 7 26.10.2010 19:40
Выдвет ошибку JavaScript Ромио Opera, Safari и др. 4 21.10.2010 20:34
JavaScript на Яндекс.Фотки - почему тормозит браузеры? ZavFirefox Javascript под браузер 23 27.09.2009 19:24