Рекурсия, стек
Чтобы понять рекурсию, нужно понять рекурсию
Рекурсия это обращение функции к самой себе. У рекурсии нет точки выхода, поэтому нужно условие - ограничитель рекурсии.
Известный пример рекурсии - вычисление факториала.
function factorial(num){
while (num > 0) {
return num * factorial(num - 1);
}
return 1;
}
while (num > 0) {
return num * factorial(num - 1);
}
return 1;
}
factorial(5) // 120
Здесь у меня с последним return 1; проблема была. Потому что добавить я его добавила, но зачем толком сказать не могла. Напишу ещё раз, вдруг забуду
Считает функция факториал от 5
это 5 * на себя же от 4
а это 4 * на себя же от 3
а это 3 * на себя же от 2
а это 2 * на себя же от 1
а это 1 * на себя же от 0
а это уже return 1
А если бы я не указала чему равно значение функции если num = 0, то в вычисление попало бы неопределённое значение - undefined, и результат был бы NaN.
Значение, на котором рекурсия заканчивается, называется базисом рекурсии.
Ещё один пример - х в степени n рекурсией посчитать.
Считаем.
х в степени n это х умножить на х в степени (n - 1)
х в степени (n - 1) это х умножить на х в степени (n - 2)
х в степени (n - 2) это х умножить на х в степени (n - 3)
И самое последнее значение будет х в степени 0, которое, как известно, даёт единицу
Пишем
function pow(x, n) {
return (n > 0) ? x * pow(x, n - 1) : 1;
}
pow(2,3)
Красиво же? Красиво.
Эффективно? Не факт. И вот почему.
На каждом шаге рекурсии функция должна хранить в памяти что она хотела сосчитать раньше. Поэтому глубина рекурсии ограничена.
Ограничения в разных браузераx разные. В опере (12.00) и хроме это 16382, в Firefox (14.0.1) — 46141. Цифры эти были получены опытным путём источник
Цитата: Любая рекурсия может быть переделана в цикл. Как правило, вариант с циклом будет эффективнее.
Задача.
Попробуем вывести в модальном окне цифры от 0 до n
Вариант 1
function write(n) {
if (n >= 0) {
alert(n);
write(n - 1);
}
}
write(5) // 5, 4, 3, 2, 1, 0
Считает функция факториал от 5
это 5 * на себя же от 4
а это 4 * на себя же от 3
а это 3 * на себя же от 2
а это 2 * на себя же от 1
а это 1 * на себя же от 0
а это уже return 1
А если бы я не указала чему равно значение функции если num = 0, то в вычисление попало бы неопределённое значение - undefined, и результат был бы NaN.
Значение, на котором рекурсия заканчивается, называется базисом рекурсии.
Ещё один пример - х в степени n рекурсией посчитать.
Считаем.
х в степени n это х умножить на х в степени (n - 1)
х в степени (n - 1) это х умножить на х в степени (n - 2)
х в степени (n - 2) это х умножить на х в степени (n - 3)
И самое последнее значение будет х в степени 0, которое, как известно, даёт единицу
Пишем
function pow(x, n) {
return (n > 0) ? x * pow(x, n - 1) : 1;
}
pow(2,3)
Красиво же? Красиво.
Эффективно? Не факт. И вот почему.
На каждом шаге рекурсии функция должна хранить в памяти что она хотела сосчитать раньше. Поэтому глубина рекурсии ограничена.
Ограничения в разных браузераx разные. В опере (12.00) и хроме это 16382, в Firefox (14.0.1) — 46141. Цифры эти были получены опытным путём источник
Цитата: Любая рекурсия может быть переделана в цикл. Как правило, вариант с циклом будет эффективнее.
Задача.
Попробуем вывести в модальном окне цифры от 0 до n
Вариант 1
function write(n) {
if (n >= 0) {
alert(n);
write(n - 1);
}
}
write(5) // 5, 4, 3, 2, 1, 0
Вариант 2
function write(n) {
if (n >= 0) {
write(n - 1);
alert(n);
}
}
write(5) // 0, 1, 2, 3, 4, 5
Чем определяется порядок в каком выводятся числа в первом и во втором случае?
Первый вариант - обычный цикл. Функция вывела 5, уменьшила значение n на 1, вывела 4 и т.д до нуля
Второй случай - пример рекурсии. Функция ищет write(n - 1), потом
write(n - 2), потом write(n - 3) пока не дойдёт до 0 и уже начиная с него выводит числа в консоль.
Здесь мы сталкиваемся с понятием стека - области памяти в которой хранятся все вызовы функции. Стек работает по принципу: последний пришёл, первый ушёл. Таким образом последнее пришедшее в него значение - 0 выведется первым, затем предпоследнее значение - 1 и т.д
Задача
Напишите функцию sumTo(n), которая для данного n вычисляет сумму чисел от 1 до n
function sumTo(n) {
return (n > 1 ) ? (n + sumTo(n-1)) : 1;
}
sumTo(10) // 55
Задача.
Вывести последовательность чисел Фибоначчи
function fib(n) {
if (n > 2) {
return fib(n - 1) + fib(n - 2);
}
return 1;
}
fib(7) // 13
Сделала. Но такая задача для человека, впервые столкнувшегося с рекурсией, слишком сложная. Полностью согласна с автором комментария
Пример, который он приводит, действительно простой и элементарный
// Выводим числа от 10 до 1
var countFrom = function(n) {
if (n === 0) return; // Момент где наша рекурсия прекратится
console.log(n); // Выводим число
countFrom (n - 1); // Вызываем функцию с числом меньше предыдущего на единицу
}
countFrom(10); // 10, 9, 8, 7, ... 1
И о хорошем
function write(n) {
if (n >= 0) {
write(n - 1);
alert(n);
}
}
write(5) // 0, 1, 2, 3, 4, 5
Чем определяется порядок в каком выводятся числа в первом и во втором случае?
Первый вариант - обычный цикл. Функция вывела 5, уменьшила значение n на 1, вывела 4 и т.д до нуля
Второй случай - пример рекурсии. Функция ищет write(n - 1), потом
write(n - 2), потом write(n - 3) пока не дойдёт до 0 и уже начиная с него выводит числа в консоль.
Здесь мы сталкиваемся с понятием стека - области памяти в которой хранятся все вызовы функции. Стек работает по принципу: последний пришёл, первый ушёл. Таким образом последнее пришедшее в него значение - 0 выведется первым, затем предпоследнее значение - 1 и т.д
Задача
Напишите функцию sumTo(n), которая для данного n вычисляет сумму чисел от 1 до n
function sumTo(n) {
return (n > 1 ) ? (n + sumTo(n-1)) : 1;
}
sumTo(10) // 55
Задача.
Вывести последовательность чисел Фибоначчи
function fib(n) {
if (n > 2) {
return fib(n - 1) + fib(n - 2);
}
return 1;
}
fib(7) // 13
Сделала. Но такая задача для человека, впервые столкнувшегося с рекурсией, слишком сложная. Полностью согласна с автором комментария
// Выводим числа от 10 до 1
var countFrom = function(n) {
if (n === 0) return; // Момент где наша рекурсия прекратится
console.log(n); // Выводим число
countFrom (n - 1); // Вызываем функцию с числом меньше предыдущего на единицу
}
countFrom(10); // 10, 9, 8, 7, ... 1
Фибоначчи через tail recursion источник:
function fib(n) {
return function rec(n, a, b) {
return n > 0 ? rec(n - 1, b, a + b) : a;
}(n, 0, 1);
}
//теперь не подвиснет при рекурсии от 77
console.log(fib(77))
function fib(n) {
return function rec(n, a, b) {
return n > 0 ? rec(n - 1, b, a + b) : a;
}(n, 0, 1);
}
//теперь не подвиснет при рекурсии от 77
console.log(fib(77))
И о хорошем
