Рекурсия

Проблем

Колко подредби има?

На рафта има 5 книги. По колко начина можеш да ги подредиш? За първото място има 5 избора, за второто 4, после 3, 2 и 1: 5 · 4 · 3 · 2 · 1 = 120. Това е факториел, пише се 5!.

С цикъл вече го можеш:

function factorialLoop(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) {
    result *= i;
  }
  return result;
}

console.log(factorialLoop(5));

Изход

120

Погледни го и така: 5! = 5 · 4!. А 4! = 4 · 3!. Задачата се решава чрез същата задача, само по-малка. Може ли функцията да каже точно това?

Идеята

Функция, която вика себе си

Може. Функция, която вика сама себе си, се казва рекурсивна, а подходът е рекурсия.

function factorial(n) {
  if (n === 1) {
    return 1;
  }
  return n * factorial(n - 1);
}

console.log(factorial(5));

Изход

120

Две неща я правят да работи:

• Дъно. Случай, който се решава направо, без ново извикване. Тук: 1! = 1.
• По-малка задача. Всяко извикване вика себе си с число, по-близо до дъното: n - 1.

Виж го

Купчината от извиквания

function factorial(n) {
  if (n === 1) {
    return 1;
  }
  return n * factorial(n - 1);
}

console.log(factorial(3));  // 6

Стъпка по стъпка, с думи

1. Програмата вика factorial(3).
2. Нова памет за factorial с n = 3.
3. 3 не е 1, затова функцията вика factorial(2) и чака отговора.
4. Същото: factorial(2) вика factorial(1). Всяко извикване има свое n.
5. n е 1: това е дъното. Връща 1, без да вика повече.
6. Отговорът слиза надолу: 2 * 1 = 2.
7. И пак: 3 * 2 = 6.
8. factorial(3) връща 6 и програмата го отпечатва.

Всяко извикване получава своя памет със свое n. Те се трупат едно над друго и чакат. Тази купчина се казва стек от извиквания (call stack). Когато дъното върне 1, отговорите слизат надолу един по един и купчината се разтуря.

Пробвай

Слизане и качване

Какво ще отпечата програмата?

function steps(n) {
  if (n === 0) {
    return;
  }
  console.log(`слизам ${n}`);
  steps(n - 1);
  console.log(`качвам ${n}`);
}

steps(2);

Отговор

слизам 2
качвам 2
слизам 1
качвам 1

слизам 2
слизам 1
качвам 2
качвам 1

слизам 2
слизам 1
качвам 1
качвам 2

Провери

Пробвай

Намери грешката

sumTo(4) трябва да върне 1 + 2 + 3 + 4 = 10. Вместо това програмата спира с RangeError: Maximum call stack size exceeded. На кой ред е грешката?

Избери реда с грешката.

1function sumTo(n) {2 if (n === 1) {3 return 1;4 }5 return n + sumTo(n);6}

Провери

Идеята

Рекурсия или цикъл?

Факториелът става и с цикъл, и с рекурсия. Цикълът тук е по-добрият избор: не трупа памет за всяко извикване, а за 100 000 извиквания стекът няма да стигне.

Рекурсията е естествена там, където нещото съдържа по-малки неща от същия вид: папка с папки вътре, категория с подкатегории, разклонение с разклонения. Такива задачи ще срещнеш по-нататък в курса. Там цикълът става тромав, а рекурсивната функция остава кратка.

По-точно, за любопитните

• Факториелът често се пише с дъно 0! = 1 (if (n === 0)). Тогава работи и за 0.

• В JavaScript всяко число е дробно (double), а големите цели числа се пазят приблизително. До 22! резултатът е точен, а 23! вече е закръглен. За точни цели числа без граница има BigInt: число с n накрая (23n):

function factorial(n) {
  if (n === 1) {
    return 1;
  }
  return n * factorial(n - 1);
}

function factorialBig(n) {
  if (n === 1n) {
    return 1n;
  }
  return n * factorialBig(n - 1n);
}

console.log(factorial(23));
console.log(factorialBig(23n));

Изход

2.585201673888498e+22
25852016738884976640000n

Пробвай

Подреди редовете

Функцията трябва да смята степен: power(2, 10) е 1024. Подреди редовете ѝ.

1. }↑↓
2. function power(base, exp) {↑↓
3. }↑↓
4. if (exp === 0) {↑↓
5. return base * power(base, exp - 1);↑↓
6. return 1;↑↓

Провери

Упражнение

Рекурсивни задачи

1. Факториел по два начина. Напиши factorialLoop(n) с цикъл for и factorial(n) с рекурсия. Прочети число и отпечатай резултата и от двете функции.

Вход

5

Изход

Факториел на 5 е 120
Факториел на 5 е 120

2. Сума на цифрите. sumDigits(n): последната цифра (n % 10) плюс сумата на цифрите на останалото (Math.trunc(n / 10)). Дъното е едноцифрено число.

3. Фибоначи. Всяко число е сумата на предишните две: 0, 1, 1, 2, 3, 5, 8… fib(n) връща n-тото число. Пробвай с 10, а после с 45. Защо е толкова бавно? Подсказка: колко пъти се смята всяко число?

4. Палиндром. isPalindrome(s): първата и последната буква са еднакви и средата е палиндром. Дъното е дума с 0 или 1 букви.

Извикване

sumDigits(2024)
fib(10)
isPalindrome("капак")
isPalindrome("АБВГД")

Изход

8
55
true
false

Тест

Провери се

1. Какво е рекурсия?

Функция, която вика сама себе сиЦикъл вътре във функцияДве функции с едно и също име

2. Защо рекурсивната функция има нужда от дъно?

За да работи по-бързоЗа да може да връща резултатЗа да спре да вика себе си

3. factorial(3) вика factorial(2), тя вика factorial(1). Колко променливи n има в паметта точно преди factorial(1) да върне?

Нито еднаТриЕдна

4. Какво става, ако дъното никога не се стигне?

Програмата се върти безкрайно, без грешкаФункцията връща 0Стекът се препълва и програмата спира с RangeError

Провери

Започни урока отначало