# PyZ - đệ quy

## Đệ quy là gì?
Thứ tự thực hiện hàm:

def f(a,b):
    print('Xin chao f(',a,b,')')
    print(a * b)
    print('Tam biet f')

def g(x):
    print('Xin chao g(',x,')')
    f(x,2*x)
    print('Tam biet g')

g(10)

Đoạn code trên in ra:

Vậy: Hàm gọi sau, lại được thực hiện xong trước!

### Ví dụ cơ bản
Đoạn code sau tính $n!$, tích $n$ số đầu tiên

def f(n):
    print('Dang goi f(' + str(n) + ')')
    if n <= 1: return 1
    return n * f(n-1)

print(f(5))

Trong đoạn code trên, nếu không có dòng 3, hàm sẽ chạy vô tận và gặp lỗi như sau:

Kết quả in ra:

Dang goi f(5)
Dang goi f(4)
Dang goi f(3)
Dang goi f(2)
Dang goi f(1)
Dang goi f(0)
Dang goi f(-1)
Dang goi f(-2)
Dang goi f(-3)
Dang goi f(-4)
Dang goi f(-5)
Dang goi f(-6)
Dang goi f(-7)
Dang goi f(-8)
...
Dang goi f(-1003)
Dang goi f(-1004)
Dang goi f(-1005)
Dang goi f(-1006)
Dang goi f(-1007)
Traceback (most recent call last):
  File "E:\Algo\[J] LQD\dequy.py", line 21, in <module>
    print(f(5))
  File "E:\Algo\[J] LQD\dequy.py", line 19, in f
    return n * f(n-1)
  File "E:\Algo\[J] LQD\dequy.py", line 19, in f
    return n * f(n-1)
  File "E:\Algo\[J] LQD\dequy.py", line 19, in f
    return n * f(n-1)
  [Previous line repeated 1010 more times]
  File "E:\Algo\[J] LQD\dequy.py", line 17, in f
    print('Dang goi f(' + str(n) + ')')
RecursionError: maximum recursion depth exceeded while pickling an object

## Luôn nhớ: phải có điều kiện dừng.
Điều kiện dừng giúp hàm đệ quy không gọi vô tận, và được đặt ở **trên cùng** của hàm này.

## Các bài toán có thể dùng đệ quy
### Tính $a^b (\mod c)$
Dùng tính chất số học: $a^b + a^c = a^{b+c}$ (cùng cơ số, lấy tổng hai số mũ).
Nếu $b$ lẻ, ta tính $a^b$ từ $a^{b-1}$
Nếu $b$ chẵn, ta tính từ $a^{b/2}$

def lt(a,b,c):
    print('Dang tinh ', a, ' ^ ', b)
    if b == 0: return 1
    if b % 2 == 1:
        return a * lt(a,b-1,c) % c
    tam = lt(a, b//2, c)
    return tam * tam % c

Hàm trên chạy rất nhanh, vì sau tầm $2$ phép tính là số mũ $b$ giảm về $0$

Ví dụ với lời gọi hàm `lt(2,127)`

Dang tinh  2  ^  127
Dang tinh  2  ^  126
Dang tinh  2  ^  63
Dang tinh  2  ^  62
Dang tinh  2  ^  31
Dang tinh  2  ^  30
Dang tinh  2  ^  15
Dang tinh  2  ^  14
Dang tinh  2  ^  7
Dang tinh  2  ^  6
Dang tinh  2  ^  3
Dang tinh  2  ^  2
Dang tinh  2  ^  1
Dang tinh  2  ^  0

### Tháp Hà Nội
Tư tưởng rất hay của đệ quy: Giải bài toán bằng một bài toán tương tự, nhưng nhỏ hơn.
Tư duy giống quy nạp của toán: Giả sử tôi chuyển được $n-1$ đĩa thì tôi sẽ chuyển được $n$ đĩa