Задачи на рекурсию

Важность: 5

Напишите функцию sumTo(n), которая для данного n вычисляет сумму чисел от 1 до n, например:

sumTo(1) = 1
sumTo(2) = 2 + 1 = 3

sumTo(3) = 3 + 2 + 1 = 6
sumTo(4) = 4 + 3 + 2 + 1 = 10

...
sumTo(100) = 100 + 99 + ... + 2 + 1 = 5050

Сделайте три варианта решения:

1. С использованием цикла.

2. Через рекурсию, т.к. sumTo(n) = n + sumTo(n-1) для n > 1.

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

Пример работы вашей функции:

function sumTo(n) { /*... ваш код ... */ }

alert( sumTo(100) ); // 5050

Какой вариант решения самый быстрый? Самый медленный? Почему?

Можно ли при помощи рекурсии посчитать sumTo(100000)? Если нет, то почему?

Решение

[Открыть задачу в новом окне]

Важность: 4

Факториа́л числа — это число, умноженное на «себя минус один», затем на «себя минус два» и так далее, до единицы. Обозначается 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

Последовательность чисел Фибоначчи имеет формулу F_n = F_n-1 + F_n-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;  }

u=0; x[1]=1; y[1]=1; r[x[1]][y[1]] = true; chessknight(1); alert(u);

function chessknight(k) {    if (k==n*n) {u++; }

   if  ((r[x[k]+1][y[k]+2]==false) && (x[k]+1<=n) && (y[k]+2<=n))    {       r[x[k]+1][y[k]+2] = true;       x[k+1] = x[k]+1;       y[k+1] = y[k]+2;       chessknight(k+1);    }    if  ((r[x[k]+2][y[k]+1]==false) && (x[k]+2<=n) && (y[k]+1<=n))    {       r[x[k]+2][y[k]+1] = true;       x[k+1] = x[k]+2;       y[k+1] = y[k]+1;       chessknight(k+1);    }    if  ((r[x[k]+2][y[k]-1]==false) && (x[k]+2<=n) && (y[k]-1>=1))    {       r[x[k]+2][y[k]-1] = true;       x[k+1] = x[k]+2;       y[k+1] = y[k]-1;       chessknight(k+1);    }    if  ((r[x[k]+1][y[k]-2]==false) && (x[k]+1<=n) && (y[k]-2>=1))    {       r[x[k]+1][y[k]-2] = true;       x[k+1] = x[k]+1;       y[k+1] = y[k]-2;       chessknight(k+1);    }    if  ((r[x[k]-1][y[k]-2]==false) && (x[k]-1>=1) && (y[k]-2>=1))    {       r[x[k]-1][y[k]-2] = true;       x[k+1] = x[k]-1;       y[k+1] = y[k]-2;       chessknight(k+1);    }    if  ((r[x[k]-2][y[k]-1]==false) && (x[k]-2>=1) && (y[k]-1>=1))    {       r[x[k]-2][y[k]-1] = true;       x[k+1] = x[k]-2;       y[k+1] = y[k]-1;       chessknight(k+1);    }    if  ((r[x[k]-2][y[k]+1]==false) && (x[k]-2>=1) && (y[k]+1<=n))    {       r[x[k]-2][y[k]+1] = true;       x[k+1] = x[k]-2;       y[k+1] = y[k]+1;       chessknight(k+1);    }    if  ((r[x[k]-1][y[k]+2]==false) && (x[k]-1>=1) && (y[k]+2<=n))    {       r[x[k]-1][y[k]+2] = true;       x[k+1] = x[k]-1;       y[k+1] = y[k]+2;       chessknight(k+1);    }    r[x[k]][y[k]] = false;    x[k] = 0;    y[k] = 0; }

</script>

partizan

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

Но враги не дремлют и постоянно ведут подрывную работу. А именно, пытаются получить доступ к несуществующему элементу массива 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 знака, но все же работает, и работает в десятки раз быстрее 

Илья Кантор

Функция работает неправильно, но зато быстро? :)

• Мне нравится!

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.

• Мне нравится!

• Ответить