Рекурсивын тухай.
Энэ нь өөрөө өөрийгөө дуудаж чаддаг функц юм. Жишээгээр ойлгомжтой байх болов уу? Жишээ нь бид 1 ээс N хүртэл хэвлэмээр байлаа. Мэдээж үүнийг хийхэд амархан. Бид while, эсвэл for ашиглаад үүнийг шийдэж болно. Харин Рекурсив ашиглаад үүнийг хийвэл хэрхэн хийгдэх талаар.
Энэ нь өөрөө өөрийгөө дуудаж чаддаг функц юм. Жишээгээр ойлгомжтой байх болов уу? Жишээ нь бид 1 ээс N хүртэл хэвлэмээр байлаа. Мэдээж үүнийг хийхэд амархан. Бид while, эсвэл for ашиглаад үүнийг шийдэж болно. Харин Рекурсив ашиглаад үүнийг хийвэл хэрхэн хийгдэх талаар.
- Бид 1 гэсэн тоог хэвлээд дараа нь 2 гэсэн тоог хэвлэнэ. харин дараа нь 3 гэх мэт энэ нь N хүрээд зогсоно. Тэгвэл рекурсивийн зогсох нөхцөл нь N гэсэн үг ба бид N-ээс ялгаатай K гэсэн тоог хэвлэсэн тохиолдолд 1-ээс K хүртэл бүх тоог хэвлэсэн гэсэн үг ба K < N бага тул K+1 гэсэн тоог хэвлэх ёстой ба. Үргэлжлүүлэн хэвлэх ёстой гэсэн үг юм. Харин K == N нөхцөл биелбэл бид N хүртэлх бүх тоог хэвлэсэн гэсэн үг юм. Тиймээс үүгээр зогсоно.
- Бид N гэсэн тоог N-1 хүртэлх тоо хэвлэгдсэн гэж үзвэл үүний ард N гэсэн тоогоо хэвлэхэд хангалттай гэсэн үг юм. Тэгвэл N хүртэл хэвлэхийн тулд N-1 хүртэл хэвлэсэн байх ёстой. N-1-ыг хэвлэхийн тулд N-2 хүртэл хэвлэсэн байх ёстой гэх мэт 2 гэсэн тоог хэвлэхийн тулд 1 гэсэн тоог хэвлэх хэрэгтэй юм. Харин 1 гэсэн тоог хэвлэхийн тулд 0 хүртэл хэвлэх хэрэгтэй ба бид 0-ийг хэвлэх ёсгүй тул энэ хүрээд зогсоно. Харин одоо 0 хүртэл хэвлэсэн. Иймээс 1-ийг хэвлэнэ. Ингэснээр 1 хүртэл хэвлэсэн. Иймээс 2-ыг хэвлэнэ. Ингэснээр 2 хүртэл хэвлэсэн. Энэ мэд бид N хүртэл хэвлэх юм.
Өөрийгөө дуудсаны дараа бичсэн юм нь тэр дуудсан хэсгийг зогсох буюу бодоод дууссаны дараа хийгдэнэ гэсэн үг юм. Тэгээд өөрсдөө бодлого зохиож, эсвэл давталтын оронд ашиглаж туршлагажих хэрэгтэй. Анх бол би ангайж байлаа. Энэ бодлогыг арайх гэж бодож ойлгож байсандаа. Доорхи код энэ хаяг дээр байгаа.
- //recursive
- #include <iostream>
- using namespace std;
- void rec1( int now, int n ) {
- // одоо явж байгаа тоо нь n гэсэн тооноос бага буюу тэнцүү нь
- // үнэн ба now-1 тоо хүртэл хэвлэсэн нь ч үнэн. Тиймээс now
- // гэсэн тоогоо хэвлэнэ.
- cout << now << " ";
- if( now == n ) {
- // энэд одоо явж байгаа тоо нь n тоотой тэнцүү тул
- // n+1 гэсэн тоог хэвлэх шаардлагагүй тул энэ хүрээд
- // зогсох ёстой.
- return;
- }
- // үгүй бол рекурсив үргэлжлэх ёстой. ба now+1 гэсэн тоог
- // хэвлэх ёстой.
- rec1( now+1, n );
- }
- void rec2( int now, int x ) {
- if( now == 0 ) {
- // одоо байгаа тоо нь 0 гэсэн тул бид 0 хүртэл хэвлэсэн
- // гэж үзэх тул энэ хүрээд зогсоно.
- return;
- }
- // эсрэг тохиолдолд now нь 1-ээс их буюу тэнцүү ба бид өмнөх
- // тоонуудыг хэвлэх ёстой тул now-1 гэж дуудна.
- rec2( now-1, x );
- // энэ тохиолдолд бид now-1 хүртэл хэвлэсний дараа энэ
- // үйлдэл хийгдэх. тиймээс одоо now гэсэн тоогоо нэмж
- // хэвлэнэ гэсэн үг юм.
- cout << now << " ";
- }
- int main() {
- /*
- Рекурсив гэж юу вэ? Энэ нь өөрөө өөрийгөө дуудаж чаддаг функц юм. Жишээгээр
- ойлгомжтой байх болов уу? Жишээ нь бид 1 ээс N хүртэл хэвлэмээр байлаа.
- Мэдээж үүнийг хийхэд амархан. Бид while, эсвэл for ашиглаад үүнийг шийдэж
- болно. Харин Рекурсив ашиглаад үүнийг хийвэл хэрхэн хийгдэх талаар.
- 1. Бид 1 гэсэн тоог хэвлээд дараа нь 2 гэсэн тоог хэвлэнэ. харин дараа нь
- 3 гэх мэт энэ нь N хүрээд зогсоно. Тэгвэл рекурсивийн зогсох нөхцөл нь
- N гэсэн үг ба бид N-ээс ялгаатай K гэсэн тоог хэвлэсэн тохиолдолд 1-ээс
- K хүртэл бүх тоог хэвлэсэн гэсэн үг ба K < N бага тул K+1 гэсэн тоог
- хэвлэх ёстой ба. Үргэлжлүүлэн хэвлэх ёстой гэсэн үг юм. Харин K == N
- нөхцөл биелбэл бид N хүртэлх бүх тоог хэвлэсэн гэсэн үг юм. Тиймээс
- үүгээр зогсоно.
- 2. Бид N гэсэн тоог N-1 хүртэлх тоо хэвлэгдсэн гэж үзвэл үүний ард N гэсэн
- тоогоо хэвлэхэд хангалттай гэсэн үг юм. Тэгвэл N хүртэл хэвлэхийн тулд
- N-1 хүртэл хэвлэсэн байх ёстой. N-1-ыг хэвлэхийн тулд N-2 хүртэл хэвлэсэн
- байх ёстой гэх мэт 2 гэсэн тоог хэвлэхийн тулд 1 гэсэн тоог хэвлэх хэрэгтэй
- юм. Харин 1 гэсэн тоог хэвлэхийн тулд 0 хүртэл хэвлэх хэрэгтэй ба бид 0-ийг
- хэвлэх ёсгүй тул энэ хүрээд зогсоно. Харин одоо 0 хүртэл хэвлэсэн. Иймээс
- 1-ийг хэвлэнэ. Ингэснээр 1 хүртэл хэвлэсэн. Иймээс 2-ыг хэвлэнэ. Ингэснээр
- 2 хүртэл хэвлэсэн. Энэ мэд бид N хүртэл хэвлэх юм.
- Ер нь бол өөрийгөө дуудсаны дараа бичсэн юм нь тэр дуудсан хэсгийг зогсох буюу
- бодоод дууссаны дараа хийгдэнэ гэсэн үг юм
- */
- int n; cin >> n;
- rec1( 1, n ); cout << endl;
- rec2( n, n ); cout << endl;
- return 0;
- }
wooow дажгүй шүү.
ReplyDelete