Рекурсив маълумотлар тузилмаси

Рекурсив объектларга мисоллар

• Серпинский учбурчаги

• Рекур
• сив
• три
• ада

• параметризация қилиш – масала шартини таснифлаш ва уни ҳал этиш учун параметрлар аниқланади;
• рекурсия базаси (асоси) – масала ечими аниқ бўлган тривиал ҳолат аниқланади, яъни бу ҳолатда функцияни ўзига мурожаат қилиши талаб этилмайди;
• декомпозиция – умумий ҳолатни нисбатан анча оддий бўлган ўзгарган параметрли қисм масалалар орқали ифодалайди.

• Изоҳ

• Рекурсив ёки итерацион усул самарадорлиги берилган масалани ҳал қилувчи дастурни турли бошланғич қийматларда таҳлил этиш орқали аниқланади.

• Изоҳ

• Рекурсив алгоритмларни самарадорлигини ошириш кўпинча триада босқичларини қайта кўриб чиқиш натижасида амалга ошиши мумкин.

• Факториални хисоблаш:
• n!=1*2*…*n=n*(n-1)!
• int i,m,N; double long fact;
• void factorial(int m);
• void main()
• {
• clrscr();
• cin>>N;
• fact=1; factorial(N);
• }
• void factorial(int m)
• { if(m==1)
• {cout<
• getch();
• exit(1); }
• fact*=m* factorial(m-1); }

• Рекурсив триада:
• Параметризация:
• n – номанфий бутун сон.
• Рекурсия базаси:
• n =0 ва n =1 учун факториал 1 га тенг.
• Декомпозиция:
• n!=(n-1)!*n.

Дарахт тушунчаси

• Дарахт – бу чизиқсиз боғланган маълумотлар тузилмасидир.
• Дарахт ўзининг қуйидаги белгилари билан таснифланади:
• дарахтда шундай битта элемент борки, унга бошқа элементлардан мурожаат йўқ. Мазкур элементга дарахт илдизи дейилади;
• дарахтда ихтиёрий элементга чекли сондаги кўрсаткичлар ёрдамида мурожаат қилиш мумкин;
• дарахтнинг ҳар бир элементи фақатгина ўзидан олдинги келган битта элемент билан боғланган. Дарахтнинг ҳар бир тугуни оралиқ ёки терминал (барг) бўлиши мумкин.

• Def.2.

• Дарахт босқичлари сонига дарахт баландлиги дейилади.

• Def.3.

• Тугунлардан чиқаётган шоҳлар сони тугундан чиқиш даражаси дейилади.

• 0-чи босқич

• 1-чи босқич

• 2-чи босқич

• Чиқиш даражалари

• 3

• 1

• 2