Đệ quy (Recursion)

def recursive_function(parameters):
    # 1. BASE CASE - Điều kiện dừng
    if <base_condition>:
        return <base_value>
 
    # 2. RECURSIVE CASE - Gọi chính nó với input nhỏ hơn
    return recursive_function(<smaller_input>)

def countdown(n):
    # Base case: dừng khi n = 0
    if n == 0:
        print("Done!")
        return
 
    # Recursive case
    print(n)
    countdown(n - 1)  # Gọi chính nó với n nhỏ hơn
 
# Test
countdown(5)
# Output:
# 5
# 4
# 3
# 2
# 1
# Done!

def factorial(n):
    """
    n! = n * (n-1) * (n-2) * ... * 1
    5! = 5 * 4 * 3 * 2 * 1 = 120
    """
    # Base case
    if n == 0 or n == 1:
        return 1
 
    # Recursive case
    return n * factorial(n - 1)
 
# Test
print(factorial(5))  # 120
print(factorial(0))  # 1

factorial(5)
= 5 * factorial(4)
= 5 * (4 * factorial(3))
= 5 * (4 * (3 * factorial(2)))
= 5 * (4 * (3 * (2 * factorial(1))))
= 5 * (4 * (3 * (2 * 1)))
= 5 * (4 * (3 * 2))
= 5 * (4 * 6)
= 5 * 24
= 120

def sum_to_n(n):
    # Base case
    if n == 0:
        return 0
 
    # Recursive case
    return n + sum_to_n(n - 1)
 
# Test
print(sum_to_n(5))  # 1+2+3+4+5 = 15

def power(base, exponent):
    """
    Tính base^exponent
    2^3 = 2 * 2 * 2 = 8
    """
    # Base case
    if exponent == 0:
        return 1
 
    # Recursive case
    return base * power(base, exponent - 1)
 
# Test
print(power(2, 3))   # 8
print(power(5, 2))   # 25

# Đệ quy
def factorial_recursive(n):
    if n <= 1:
        return 1
    return n * factorial_recursive(n - 1)
 
# Vòng lặp
def factorial_iterative(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result
 
# Cả hai đều cho kết quả giống nhau
print(factorial_recursive(5))  # 120
print(factorial_iterative(5))  # 120

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

def fibonacci(n):
    # Base cases
    if n == 0:
        return 0
    if n == 1:
        return 1
 
    # Recursive case
    return fibonacci(n - 1) + fibonacci(n - 2)
 
# Test
for i in range(10):
    print(f"fib({i}) = {fibonacci(i)}")
 
# Output:
# fib(0) = 0
# fib(1) = 1
# fib(2) = 1
# fib(3) = 2
# fib(4) = 3
# fib(5) = 5
# ...

def sum_list(lst):
    # Base case: list rỗng
    if not lst:
        return 0
 
    # Recursive case: phần tử đầu + tổng phần còn lại
    return lst[0] + sum_list(lst[1:])
 
# Test
print(sum_list([1, 2, 3, 4, 5]))  # 15

def find_max(lst):
    # Base case: chỉ 1 phần tử
    if len(lst) == 1:
        return lst[0]
 
    # Recursive case
    max_of_rest = find_max(lst[1:])
    return lst[0] if lst[0] > max_of_rest else max_of_rest
 
# Test
print(find_max([3, 7, 2, 9, 1]))  # 9

def reverse_list(lst):
    # Base case
    if len(lst) <= 1:
        return lst
 
    # Recursive case: phần tử cuối + đảo ngược phần còn lại
    return [lst[-1]] + reverse_list(lst[:-1])
 
# Test
print(reverse_list([1, 2, 3, 4, 5]))
# [5, 4, 3, 2, 1]

def reverse_string(s):
    # Base case
    if len(s) <= 1:
        return s
 
    # Recursive case
    return s[-1] + reverse_string(s[:-1])
 
# Test
print(reverse_string("hello"))  # "olleh"

def is_palindrome(s):
    # Base case: chuỗi rỗng hoặc 1 ký tự
    if len(s) <= 1:
        return True
 
    # Recursive case: kiểm tra đầu và cuối
    if s[0] != s[-1]:
        return False
 
    return is_palindrome(s[1:-1])
 
# Test
print(is_palindrome("radar"))   # True
print(is_palindrome("hello"))   # False

def count_char(s, char):
    # Base case
    if not s:
        return 0
 
    # Recursive case
    count = 1 if s[0] == char else 0
    return count + count_char(s[1:], char)
 
# Test
print(count_char("hello", "l"))  # 2

def sum_nested(lst):
    total = 0
    for item in lst:
        if isinstance(item, list):
            # Nếu là list, gọi đệ quy
            total += sum_nested(item)
        else:
            # Nếu là số, cộng vào
            total += item
    return total
 
# Test
nested = [1, [2, 3, [4, 5]], 6, [7, [8, 9]]]
print(sum_nested(nested))  # 45

def flatten(lst):
    result = []
    for item in lst:
        if isinstance(item, list):
            # Đệ quy flatten sublist
            result.extend(flatten(item))
        else:
            result.append(item)
    return result
 
# Test
nested = [1, [2, [3, 4], 5], 6]
print(flatten(nested))  # [1, 2, 3, 4, 5, 6]

def binary_search(lst, target, left=0, right=None):
    if right is None:
        right = len(lst) - 1
 
    # Base case: không tìm thấy
    if left > right:
        return -1
 
    # Tìm giữa
    mid = (left + right) // 2
 
    # Base case: tìm thấy
    if lst[mid] == target:
        return mid
 
    # Recursive cases
    if lst[mid] < target:
        # Tìm bên phải
        return binary_search(lst, target, mid + 1, right)
    else:
        # Tìm bên trái
        return binary_search(lst, target, left, mid - 1)
 
# Test
numbers = [1, 3, 5, 7, 9, 11, 13, 15]
print(binary_search(numbers, 7))   # 3
print(binary_search(numbers, 10))  # -1

# ❌ SAI - Không có điều kiện dừng!
def infinite_recursion(n):
    return n + infinite_recursion(n - 1)
    # RecursionError: maximum recursion depth exceeded

# ❌ SAI - Base case không bao giờ đạt được
def wrong_base(n):
    if n == 0:  # Nhưng n luôn dương!
        return 0
    return n + wrong_base(n + 1)  # n tăng, không giảm!

# ❌ SAI - Input không giảm
def not_progressing(n):
    if n == 0:
        return 0
    return n + not_progressing(n)  # n không đổi!

# Chậm - tính lại nhiều lần
def fib_slow(n):
    if n <= 1:
        return n
    return fib_slow(n - 1) + fib_slow(n - 2)
 
# fib(5) = fib(4) + fib(3)
#        = (fib(3) + fib(2)) + (fib(2) + fib(1))
#        = ((fib(2) + fib(1)) + ...) + ...
# fib(2) được tính nhiều lần!

def fib_memo(n, memo={}):
    # Kiểm tra cache
    if n in memo:
        return memo[n]
 
    # Base cases
    if n <= 1:
        return n
 
    # Tính và lưu vào cache
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]
 
# Test - Nhanh hơn nhiều!
print(fib_memo(50))

# ✅ TỐT
def good_recursion(n):
    if n == 0:  # Clear base case
        return 1
    return n * good_recursion(n - 1)

# ✅ TỐT - n giảm dần về 0
def countdown(n):
    if n == 0:
        return
    print(n)
    countdown(n - 1)  # n giảm

# Nếu đệ quy quá phức tạp, dùng vòng lặp
def iterative_factorial(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

from functools import lru_cache
 
@lru_cache(maxsize=None)
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)