Факториа́л числа — это число, умноженное на «себя минус один», затем на «себя минус два» и так далее, до единицы. Обозначается n!
Определение факториала можно записать как:
n! = n*(n-1)*(n-2)*...*1
Примеры значений для разных n:
1! = 1
2! = 2*1 = 2
3! = 3*2*1 = 6
4! = 4*3*2*1 = 24
5! = 5*4*3*2*1 = 120
Задача — написать функцию factorial(n), которая возвращает факториал числа n!, используя рекурсивный вызов.
alert( factorial(5) ); // 120
Подсказка: обратите внимание, что n! можно записать как n * (n-1)!, например 3! = 3*2! = 3*2*1! = 6
Решение
[Открыть задачу в новом окне]
Важность: 5
Последовательность чисел Фибоначчи имеет формулу Fn = Fn-1 + Fn-2. То есть, следующее число получается как сумма двух предыдущих.
Первые два числа равны 1, затем 2(1+1), затем 3(1+2), 5(2+3) и так далее: 1, 1, 2, 3, 5, 8, 13, 21....
Числа Фибоначчи тесно связаны с золотым сечением и множеством природных явлений вокруг нас.
Напишите функцию fib(n), которая возвращает n-е число Фибоначчи. Пример работы:
function fib(n) { /* ваш код */ }
alert( fib(3) ); // 2
alert( fib(7) ); // 13
alert( fib(77)); // 5527939700884757
Все запуски функций из примера выше должны срабатывать быстро.
Вычисление рекурсией (медленное)
Последовательное вычисление (идея)
Последовательное вычисление (код)
[Открыть задачу в новом окне]
Существуют много областей применения рекурсивных вызовов, в частности — работа со структурами данных, такими как дерево документа. Мы обязательно встретимся с ними.
‹ Функции Методы и свойства ›
18.03.2012
Илья Кантор
Fomin
Подскажите, пожалуйста, почему не выполняется следующая за вызовом рекурсивной функции chessknight(k); инструкция alert(u); в коде. Если бы рекурсивная функция зациклилась, зависла, браузер бы предлагал остановить выполнение скрипта, но он не предлагает. Если бы в коде была синтаксическая ошибка, то alert(u); не выводил бы значение 0, если закомментировать //chessknight(k); Однако, если закомментировать //chessknight(k); то срабатывает alert(u); , в противном же случае ничего не происходит. В чём тут дело? <script type="text/javascript"> var n = 5; var x = new Array(); var y = new Array(); var r = new Array(); var u; for (var i = 1; i <= n*n; i++) x[i] = 0; for (var i = 1; i <= n*n; i++) y[i] = 0; for (var i = 1; i<=n; i++) { r[i] = new Array(); for (var j=1; j<=n; j++) r[i][j]=false; }
Этот чудесный код столь великолепно структурирован и интуитивно понятен что просто не может работать некорректно. Кстати, ты правильно сделал что отказался от комментариев.
Но враги не дремлют и постоянно ведут подрывную работу. А именно, пытаются получить доступ к несуществующему элементу массива r в выражении r[x[k]+1][y[k]+2] когда x[k] = 5 5 да 1 имеем 6, а r[6,.. уже ни в какие ворота не лезет. Интерпретатор героически бросился проверять допустимость диапазона x[k]+1<=n, но не успел, поскольку коварный фашист осуществил доступ ранше.
Делай проверку до обращения к массиву. Но будь на чеку! Враг хитёр и опасен!
Fomin
Ой, оказывается, может быть ошибка в коде функции chessknight(k) Консоль Mozilla сообщает TypeError: r[(x[k] + 1)] is undefined if ((r[x[k]+1][y[k]+2]==false) && (x[k]+1<=n) && (y[k]+2<=n)) Я неправильно использую двумерный массив?
exDruid
Факториал с помощью цикла:
function factorial(n) { var result = n; for(n = value; n > 1; n--) { result = result*(n-1); } return result; } alert(factorial(value));
Или пример с введением значения value (по аналогии с предыдущим уроком):
function factorial(n) { var result = n; for(n = value; n > 1; n--) { result = result*(n-1); } return result;}var value = prompt('Введите значение', ''); if (!( value%1 == 0) || value <= 1) { alert('Степень ' + value + 'не поддерживается, введите целую степень, большую 1' ); }else{ alert(factorial(value));}
Код немного длинней, чем с рекурсией, зато более читабелен. ИМХО - краткость кода не показатель его простоты, особенно если учесть то, что рекурсия имеет ряд недостатков. Принцип рекурсии я понял, но не могу понять в чем ее преимущество перед циклами? Просьба к автору продемонстрировать более практические примеры применения рекурсии. Фибоначчи меня не убедил :)
Gladkov Andrei
C использованием цикла:
function sumTo(n){ var a=n; for (i=1;i<=n;i++){ a= i+a-1 ; }; return a; }; alert(sumTo(100));
Арсений
У меня вопрос не по теме в js можно удобно создавать графику?
Александр Белец
что означает "удобно"?
Max Korzilov
Имхо, нужны более реалистичные примеры, из реально работающих сайтов, чтобы показать и заинтересовать учащегося в осмыслении рекурсии, а так же показать, что решение задач на нахождение чисел по формулам не является определяющим фактором в дальнейшем обучении.
Темболее, что показав функцию нахождения чисел фибонначи, ученик может подумать, что это лучший (наиболее быстрый) способ нахождения данных чисел (ведь ученик хочет верить, что автор преподносит наилучший материал), и если ему когда-нибудь понадобится использовать эту функцию, он возьмет отсюда, хотя на самом деле, в подобных функциях обходятся без рекурсии и без циклов, например: function fibonacci(n) { var sq5 = Math.sqrt(5); var a = (1 + sq5) / 2; var b = (1 - sq5) / 2; return (Math.pow(a, n) - Math.pow(b, n)) / sq5;}
(Изменено автором 2 месяцев назад)
Илья Кантор
Кстати, вы решили задачу на Фибоначчи неправильно. Читайте дальше.
Max Korzilov
Это не я решил, а нашел самое распространенное решение в интернете
и функция возвращает одинаковые результаты по сравнению с представленными в статье
(Изменено автором 2 месяцев назад)
Илья Кантор
Проверьте "самое распространенное решение в интернете" на значении 77 и сравните результат с представленным в статье.
(Изменено автором 2 месяцев назад)
Max Korzilov
признаю, функция грешит неточностью после 10 знака, но все же работает, и работает в десятки раз быстрее
Илья Кантор
Функция работает неправильно, но зато быстро? :)
o Мне нравится!
Dimitry Lapynow
Чуть голову не сломал с этим Фибоначчи, пока решал. А как можно прийти к этому рекурсией - вообще сложно понять. ..Хорошо хоть, что это и не нужно.)
(Изменено автором 2 месяцев назад)
Andrey Godservant
Это цветочки, друг, ягодки еще впереди :)) Еще встретится не одна возможность поломать голову :)
Dimitry Lapynow
Я надеюсь, что к тому времени у меня уже будет не голова, а крепостной таран, но пока же эти вложенности циклов и раскрывающиеся рекурсивные функции реально заставляют помучатся.
Alexey
А я сделал через массивчик: function fibonachiMember(n){ var a = new Array(); a[1] = 1; a[2] = 1; for(i=3;i<=n;i++){ a[i] = a[i-1]+a[i-2]; } return a[n]; } alert(fibonachiMember(77)); получилось вроде неплохо, с той лишь разницей что я могу вытащить любой член последовательности. Но массивы мы как бы еще не проходили, поэтому мой вариант не совсем актуален пока.
jsfighter
Где-то читал ,по-моему на этом же сайте, что рекурсия работает 1-2 раза медленне цикла, так как сам интерпретатор языка преобразует рекурсию сначало в цикл, потом вычисляет, а циклы выполняет сразу. Кто точно знает, отпишитесь?!
Hixer
Можно и так: http://learn.javascript.ru/pla... http://learn.javascript.ru/pla... http://learn.javascript.ru/pla...
Hixer
Что быстрее: var c = a + b; или c = a + b; ?
Илья Кантор
Обычно без разницы, хотя можно посмотреть код целиком. Лучше не забивайте себе голову, там разница в некоторых случаях есть, но очень небольшая.
Max Korzilov
быстрее и правильней будет var c = a + b; при втором варианте, браузер будет долго искать переменную c во всех доступных областях видимости, а затем создаст ее, если ничего не нашел, в глобальной области видимости, что так же, не очень хорошо
Andrei Glingeanu
рекурсия: function sumTo(n){ if(n>1){ return n+ sumTo(n-1) } return n
} alert(sumTo(200)); формула: function sumTo(n){ return (1+n)*n/2
} alert(sumTo(200));
Edik Trott
http://learn.javascript.ru/pla...
Edik Trott
Как сделать рекурсию в for, например http://learn.javascript.ru/pla... предложенный вариант выдавал 1 1 1 2 1 3 то есть чтобы открывались n for-ов и начиная с самого глубокого закрывались.
Andrfas
Доброго времени суток. Благодарю автора за уроки - очень полезные и качественные, как по мне. Объясните пожалуйста, чем отличаются +prompt и prompt? Почему они в некоторых случаях работают по разному?
·
Jeremen1
+ это жесткое преобразование к числу, то есть это значит что значения с prompt мы преобразуем к числу.
·
Andrfas
Благодарю за ответ.
Андрей Колесников
Я не понял, что должна возвращать функция по Фибоначчи, что значит n-е число?
visitor
Вам нужно создат функцию с n-ым числом, n это индекс чисел Фибоначчи. т.е. вот последовательность чисел : 1, 1, 2, 3, 5, 8, 13, 21 и т.д. Вам нужно, к примеру, вывести число Фибоначчи с индексом 4 , оно будет равно 3 . в уравнение это выглядит так : Фиб с индексом 4 = Фиб с предыдущим индексом(n-1) + Фиб с перепредыдущим индексом(n-2) , т.е. 1+2 =3 Я извиняюсь, но вы часом не тролль? Помойму все четко описано в этой теме.
Андрей Колесников
Нет, не беспокойтесь, я просто тупой, спасибо за подсказку))
(Изменено автором 5 назад)
Hixer
Умным учиться не́зачем, они ничего и не узна́ют никогда. Итак уже всё знают. То ли дело мы с Вами... :)
Андрей
Ничего не могу понять с рекурсией... Я не пойму, функция pow, она что встроенная? Как же она обращается к самой себе когда ее тело, код, который выполняется при ее вызове, не создан?..
Opener
функция pow обьявлена как
Function Declaration, а значит она создается еще до начала выполнения первой строки кода: http://learn.javascript.ru/fun...
eee
А кто-нибудь делал задание про формулу Бине? При n=77 у меня не совпали две последние цифры. Я думаю. это за счет округлений прии вычислении корней и делении.Может кому понадобится, корень из пяти - это Math.sqrt(5)? Нашла в Справочнике
Hixer
Надо бы включить этот момент в урок, отличное замечание!
Олег
первое задание как-то так сделал
function sumTo(n){ var result=n; for (var i=n; i>0; i--){ result+=(i-1); } return result; } var n=+prompt('Enter n', ''); alert (sumTo(n));
Jeremen1
Как не считаю вот в этом примере function pow(x, n) { return (n != 1) ? x*pow(x,n-1) : x; // пока n!=1 сводить к n-1 } получается 2 итерации...
Jeremen1
а понял. 3 итерация будет возвращаться x от последнего else.
