Bản sao của đệ quy_nocopy_ihwiqhtiqheithqehti.pdf

Python

1. (RECURSION) |

PE

28TECH.COMVN EC

2. 28TECH
Become A Better Developer

1. Cau tric dif liêu ngän xép:

gd} Ngan xép (stack) la mót cau trúc dir

UP (lau có quan hé mat thiét véi co ché
hoat dóng cúa dé quy. Dé hiéu duoc
cach ham dé quy hoat dóng, ta can
nam duoc cäch hoat dóng cúa cau
trúc dú liéu ngän xép,

Trong dé push giúp thêm 1 phan tú vao dinh ngán xép, pop giúp xóa
1 phan tur khôi dinh ngán xép. Ca 2 thao tac nay déu duoc thuc hién

O:: xép là mét cau tric dû liéu hó tro 2 thao tac push vá pop.
6 dinh ngán xép.

28TECH.COM.VN Ein

3. 28TECH
Become A Better Developer

1. Cau trúc dif liêu ngän xép:

imal Ngan xép hoat dóng theo nguyén tac viét tat lá LIFO (Last In First Out)
nghia lá vao cuôi thi ra dau. Cac phan tu vao cudi cung sé duoc ra dau tién.

>
m

TN
3.
ca 727] [72°
ayy) Ue

empty stack push push push pop

TN TN

(us) Trong chuong trinh tón tai möt bó nhó la bó nhó ngán xép, cach hoat dóng
cúa bó nhó nay tuong tu nhu cach hoat dóng cúa cau trúc dif liéu ngán xép.

28TECH.COM.VN Ein

4. 28TECH
Become A Better Developer

J Stack frame là môt kj

xuát hién trong mót só ngón ng lap trinh, no
có nhiém vu i ]

Có thé hiéu Stack frame lá mót tap hop tat ca \

các thóng tin lién quan dén mót chuong trinh
con (dugc tao ra khi xuät hién Idi goi ham)

Stack frame

t stack frame giúp các ngôn ngür
lap trinh hó tro dugc dugc chic nang dé quy
cho chuong trinh con.

5. 28TECH
Become A Better Developer

2. Stackframe lá gi ?

ia) Nhúng thanh phan cua stack frame
có thé ké dén nhu bién cuc bé, döi só, dia
chi tra vé cúa möt chuong trinh con.

Möi khi möt Idi goi ham duoc thuc hién,
stack frame chúa thong tin cla ham dé
duoc day váo bó nh6 stack va khi ham
dé két thúc thi stack frame nay dugc loai
bó khôi bó nhó stack.

28TECH.COM.VN E

6. 28TECH

Become A Better Developer
3. Ham dé quy:
& Ham dé quy là mót ham goi lai chinh nó.

recurse()

recurse();

if _name=="__main_':
recurse()

28TECH.COM.UN 5

7. 28TECH # Re x gui
Become À Better Developer Vi du vé ham dé quy

if _name__ =='"_ main Tra ve3+3=6
print (sun(3)) @

def sum(n)

Tra vé 2+1=3

n + sum(n - 1);

Tráve1+0=1

Tra vé 0

2BTECH.COMLUN Sc}

8. 28TECH
Become A Better Developer

i
1
1
1
1

¡Dé quy thuöng dua trén cóng thúc toán
‘hoc goi là cong thúc truy hói vá mót bai
¡toán con nhó nhát. Khi viét hám dé quy ta
ican xác dinh dugc bai toán con mhó nhát
¡dé lám diém dung cho hám dé quy vá
¡cóng thúc truy höi dé tim ra loi giái cúa bai
'todn lón hon thöng qua dap an cúa bai
¡toán nhó hon.

€u dé quy khóng có diem dirng,
hi só lugng ham dé quy goi du
| 16n sé lam bó nhó stack bi tran.

28TECH.COM.VN E

9. 28TECH

Become A Better Developer

Tinh tóng S(n)=1+2+3+..+n:
« Bai todn con nho nhat : S(0) = O khin =0 nn:
* Công thüc truy höi: Sn) = n + S(n- 1) khin >= 1 return n + sum(n - 1);

Tinh giai thira : F(n) = 1.2.3....n:
« Bai todn con nhó nhát : F(0) = 1 khin =0
, return 1;
+ Cóngthúc truy höi: F(n) =n * F(n- 1) khin >=1 return n * F(n - 1);

28TECH.COM.UN 5

10. 28TECH

Become A Better Developer

Tinh só Fibonacci:
Rau , … fibo(n):
+ Bai todn con nhó nhát : F(0) = 0, F(1) = 1

ifn Born 1

+ Cóngthúc truy höi: F(n) = F(n - 1) + F(n - 2) khi n >= 2 return n; .
. Brea gave . return fibo(n - 1) + fibo(n - 2);
+ Code nay chay rat cham, dó phúc tap lá 0(1.618*n)

Tinh tóng chü só cúa só nguyén duong n: SumDigit(n) cumpieit
* Bai todn con nhó nhat : SumDigit(n) = n nêu n < 10 Seay
+ Cóngthúc truy hoi : return nj

a un o return n % 10 + SumDigit(n / 10);
SumDigit(n) = n % 10 + SumDigit(n / 10) néu n >= 10

28TECH.COM.UN 5

11. 28TECH

Become A Better Developer

Möt sé vi du vé viéc xác dinh bai toán
con nhó nhát vá cóng thúc truy hoi

Tinh tó hop chap k cüa n: ee

Ck(n, k):
+ Bai toán con nhó nhát : C(n, k) = 0 néu k = 0 hoác n= k = nue cee he
+ Công thúc truy höi (Công thúc pascal) : ao 18

return nCk(n - 1, k - 1) + nCk(n - 1, k);
C(n, k) = C(n- 1,k- 1) + C(n- 1,k)

Tim uéc chung lón nhát bang dé quy gcd(a, b):
« Bai toán con nhó nhát gcd(a, b) = a khi b = 0 af D =

+ Công thúc truy hôi : gcd(a, b) = gcd(b, a % b) A 50)
return gc » Aah

28TECH.COM.UN 5

12. 28TECH

Become A Better Developer

def decToBin(n):
fi) 28
print(n, end

decToBin(n // 2)
print(n % 2, end

28TECH.COMN SE