n! = n × (n − 1)! гэж function өөрийгөө дуудаж боддог. Recursion ашигласан хамгийн энгийн жишээ.

Pre-IntermediateХугацаа: O(n)Санах ой: O(n) (дуудлагын стек)
HackerRank дээр бодох

Эхлээд жижиг бодлого

fact(3) хэд вэ? fact(3) нь 3 × fact(2) гэж бодно. fact(2) нь 2 × fact(1). fact(1) бол base case, шууд 1 буцаана.

Хариу доороос дээш буцна: fact(2) = 2 × 1 = 2, fact(3) = 3 × 2 = 6. Function нийт 3 удаа дуудагдлаа.

Энгийн аргаас санаа руу

Мэдээж loop ашиглан 1-ээс n хүртэл үржүүлж болно. Гэвч олон бодлогыг "том бодлого = жижиг бодлого + нэг алхам" гэж харвал илүү амар бичдэг. n! = n × (n − 1)! бол яг ийм.

Recursion-д хоёр зүйл заавал хэрэгтэй. Нэгдүгээрт, base case: хариу нь шууд мэдэгдэх хамгийн жижиг тохиолдол. Хоёрдугаарт, дуудлага бүр base case рүү ойртох ёстой. Энд n нэгээр багассаар 1 хүрнэ.

Нэр томьёо ба тэмдэглэгээ

recursion
Function өөрийгөө дуудах арга.
base case
Цааш дуудахгүйгээр хариугаа шууд өгдөг тохиолдол. Энд n <= 1.
Call stack
Хариугаа хүлээж буй дуудлагууд хадгалагддаг газар. fact(4) үед 4 давхар болно.
long long
9·10¹⁸ хүртэлх бүхэл тоо хадгалдаг төрөл. 20! хүртэл багтана.
n = 4
Call stack
хоосон

4! = 4 × 3 × 2 × 1. Үүнийг recursion ашиглан бодъё: fact(n) = n × fact(n − 1). Function өөрийгөө дуудна.

Алхам 1 / 9
Хурд
  • Ажиллаж буй дуудлага
  • Хариу хүлээж буй
  • Base case
  • Хариугаа өгсөн
Слайд 1 / 6

Өөрийгөө дуудах function

4! = 4 × 3 × 2 × 1 = 24. Үүнийг 4! = 4 × 3! гэж бас бичиж болно. Тэгэхээр fact function өөрийгөө дуудаж бодож чадна.

factorial-recursion.cpp
#include <bits/stdc++.h>
using namespace std;
long long fact(int n) {
if (n <= 1) return 1;
long long r = n * fact(n - 1);
return r;
}
int main() {
int n;
cin >> n;
cout << fact(n) << '\n';
return 0;
}

Юунд хэрэгтэй вэ?

n! = 1 × 2 × … × n-ийг recursion ашиглан олно. Function өөрийгөө хэрхэн дууддаг, base case юунд хэрэгтэйг ойлгоно.

Яаж ажилладаг вэ?

1. fact(n) дуудагдахад эхлээд n ≤ 1 эсэхийг шалгана. Тийм бол 1 буцаана. Энэ бол base case. 2. Үгүй бол fact(n − 1)-ийг дуудаад хариуг нь хүлээнэ. 3. Хариу ирэхэд r = n × fact(n − 1) болгоод буцаана. 4. Хүлээж буй дуудлагууд Call stack-д овоологдож, доороос дээш нэг нэгээрээ хариугаа өгнө. Оролт: нэг тоо n. n ≤ 20 бол хариу long long-д багтана.

Яагаад зөв, хэр хурдан бэ?

fact(1) = 1 зөв. fact(n − 1) зөв бол fact(n) = n × fact(n − 1) мөн зөв. Ингэж 1-ээс эхлээд n хүртэл гинж шиг үнэн болно. Үүнийг математик индукц гэдэг.

fact(n) нь n удаа дуудагдаж, тус бүр нэг үржүүлэх үйлдэл хийнэ: хугацаа O(n). Call stack n давхар болдог тул санах ой O(n). n = 20 бол ердөө 20 дуудлага.

Түгээмэл алдаа

  • Base case-ийг мартах. Тэгвэл fact(0), fact(−1) гэж дуудсаар Call stack дүүрч програм унана.
  • int ашиглах. 13! нь int-ээс хэтэрнэ. 21! бол long long-оос ч хэтэрч, сөрөг тоо гарна.
  • Маш том n дээр recursion ашиглах. n = 1 000 000 үед Call stack хэтэрч болно. Тийм үед loop хэрэглэ.

Хязгаарын тохиолдол

  • n = 1: base case шууд 1 буцаана.
  • n = 0: 0! = 1. n <= 1 нөхцөл үүнийг ч зөв хариулна.
  • n = 20: 2432902008176640000, long long-д багтах хамгийн том factorial.

Өөрийгөө шалга

  1. fact(5)-ыг бодоход function хэдэн удаа дуудагдах вэ? Хариу нь хэд вэ?

    Хариу харах

    5 удаа: fact(5), fact(4), fact(3), fact(2), fact(1). Хариу 120.

  2. fact(4) ажиллаж байхад Call stack хамгийн ихдээ хэдэн давхар болох вэ?

    Хариу харах

    4 давхар. fact(1) ажиллаж байх үед fact(4), fact(3), fact(2), fact(1) бүгд Call stack-д байна.

  3. Яагаад n <= 1 гэж шалгадаг вэ, n == 1 биш?

    Хариу харах

    n = 0 орж ирсэн ч 1 буцаагаад зогсоно. n == 1 гэж шалгавал fact(0) дуудагдахад fact(−1), fact(−2)… гэж зогсолтгүй дуудна.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.fact(4)-ийн дуудлага, буцалтыг дарааллаар нь бич.

    Hint харах

    Эхлээд доош дуудаад, дараа нь дээш үржүүлж буцна.

    Хариу ба тайлбар

    fact(4) → fact(3) → fact(2) → fact(1) = 1. Буцахдаа 2 × 1 = 2, 3 × 2 = 6, 4 × 6 = 24.

  2. 2.n! mod 1 000 000 007-г recursion ашиглан ол. n нь 100 000 хүртэл байж болно.

    Hint харах

    Үржих бүрт mod ав. Гэхдээ 100 000 давхар Call stack эрсдэлтэй.

    Хариу ба тайлбар

    return n * fact(n - 1) % MOD; гэж бичнэ. n том учраас үүнийг loop болгосон нь дээр: r = r * i % MOD. Хугацаа O(n).

  3. 3.Тооны цифрүүдийн нийлбэрийг recursion ашиглан ол. sum(1234) = 10.

    Hint харах

    Сүүлийн цифр нь n % 10, үлдсэн нь n / 10.

    Хариу ба тайлбар

    int sum(int n) { if (n < 10) return n; return n % 10 + sum(n / 10); }. Base case нь нэг оронтой тоо.

Жишээ

Оролт

4

Гаралт

24

Одоо өөрөө бодоод үз

Бодлого

Хичээл

Энэ сэдвийн хичээл удахгүй нэмэгдэнэ.