Муқаддима

Рекурсия як усулест, ки дар он функсия худро даъват мекунад. Чунин функсияҳоро функсияҳои рекурсивӣ меноманд.

Бар хилофи ҳалқаҳо, даъватҳои рекурсивӣ танҳо пайдарпай такрор намешаванд. Ба ҷои ин, ҳар як даъват як қабати нави корро эҷод мекунад, ва функсия ҳал кардани версияҳои хурдтари ҳамон масъалаҳоро идома медиҳад, то он даме ки ба як ҳолати соддае расад, ки онро мустақиман ҷавоб додан мумкин аст.

Ин ҳолати содда ҳолати асосӣ номида мешавад.

---

Факториал

Биёед аз функсияи факториал оғоз кунем.

Мо медонем, ки:

• $0! = 1$
• барои $n > 0$, дорем $n! = n \cdot (n-1)!$

Пас агар мо аллакай донем, ки чӣ гуна $(n-1)!$-ро ҳисоб кунем, он гоҳ метавонем $n!$-ро бо зарб кардани он ба $n$ ҳисоб кунем.

Ин табиатан ба як ҳалли рекурсивӣ меорад.

---

Ҷамъи ададҳо аз 1 то N

Акнун масъалаи ёфтани ҷамъи ҳамаи ададҳо аз $1$ то $N$-ро баррасӣ мекунем.

Мо метавонем онро рекурсивӣ муайян кунем:

• $sum(0) = 0$
• $sum(n) = n + sum(n - 1)$

Пас барои ҳисоб кардани ҷамм то $n$, мо аввал ҷамм то $n-1$-ро ҳисоб мекунем, баъд $n$-ро илова мекунем.

---

Ададҳои Фибоначчи

Пайдарпаии Фибоначчи чунин муайян мешавад:

• $F_0 = 0$
• $F_1 = 1$
• $F_n = F_{n-1} + F_{n-2}$ барои

Пас ҳар як қимат аз ду қимати қаблӣ вобаста аст. Ин таърифро метавон мустақиман ба рекурсия табдил дод.

---

Ба дараҷа бардоштан

Фарз мекунем мо мехоҳем $a^n$-ро ҳисоб кунем, ки дар он $a$ адади бутун аст ва $n$ адади бутуни ғайриманфӣ аст.

Таърифи мустақими рекурсивӣ чунин аст:

• $a^0 = 1$
• $a^n = a \cdot a^{n-1}$

Пас татбиқи рекурсивӣ чунин аст:

Ин дар вақти $O(n)$ кор мекунад.

---

Ба дараҷа бардоштани тез

Мо метавонем усули қаблиро беҳтар кунем.

Агар $n$ ҷуфт бошад, пас:

$$a^n = a^{n/2} \cdot a^{n/2}$$

Пас ба ҷои он ки ҳар дафъа нишондиҳандаро ба $1$ кам кунем, мо метавонем баъзан онро ба нисф кам кунем. Ин як ҳалли рекурсивии хеле тезтар медиҳад.

Мураккабии вақти ин версия $O(\log n)$ аст, зеро дар бисёр қадамҳо мо нишондиҳандаро ба $2$ тақсим мекунем ба ҷои он ки $1$ тарҳ кунем.