Recursion

Рекурсивын тухай. Функцын тухай бид өмнөх post дээр үзсэн билээ. Тэгвэл тухайн функц нь өөрөө өөрийгөө дуудвал юу болох вэ? Үүнийг рекурсив функц гэдэг. Жишээ нь

int sum(int a, int b) {
	return sum(a, b);
}

гэдэг функцийг харя. sum гэдэг нь 2 хувьсагч авдаг ба int-н утга буцаахнээ. Гэхдээ дотроо өөрийгөө дуудсан байгаа нь ба энэ юу болох бол? Мэдээж хязгааргүй ажиллах ба би лав ийм зүйлийг хүсэхгүй байна. Ер нь тэгхээр хэрэгтэйм болуудаа?

Жишээгээр ойлгомжтой байх болов уу? Жишээ нь бид 1 ээс N хүртэл хэвлэмээр байлаа. Мэдээж үүнийг хийхэд амархан. Бид while, эсвэл for ашиглаад үүнийг шийдэж болно. Харин Рекурсив ашиглаад үүнийг хийвэл хэрхэн хийх вэ?

• Бидэнд нэг функц байгаа ба тэр нь зөвхөн 1 л тоо хэвлэдэг байя. Тэгвэл олон тоо хэвлэхийн тулд яах вэ? Мэдээж бид өөрийгөө дахин дуудвал дахиад л тоо хэвлэх нь тодорхой. Гэхдээ хэзээ зогсох вэ? хэвлээд л байж болохгүй ээ. Тиймээс бид функцдээ нэг нь одоо хэвлэх тоо, дараагийх нь бидний тулах хязгаар гэсэн 2 хувьсагчтай болгы. Хэрвээ одоо хэвлэх тоо нь хязгаараас их буюу тэнцүү бол бид юу ч хийх шаардлагагүй, учир нь тэр хүртэл хэвлэсэн гэж үзнэ. Хэрвээ үгүй бол бид одоо байгаа тоогоо хэвлээд үүний дараа нь өөрийгөө дуудах ба ингэхдээ эхний утгыг нь 1-р нэмээд дуудахад болно.
• 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() {
	int n; cin >> n;
	
	rec1( 1, n ); cout << endl;
	rec2( n, n ); cout << endl;

	return 0;
}