Đệ quy là gì?

Luyện tập câu hỏi phỏng vấn lập trình bằng Python

Kirill Smirnov

Data Science Consultant, Altran

Định nghĩa

Đệ quy: định nghĩa bài toán bằng chính nó
Đệ quy: hàm tự gọi chính nó như một thủ tục con

Ví dụ: Giai thừa $n!$

$n! = n\cdot(n-1)\cdot(n-2)\cdot...\cdot1$

$n = 4$:

$4! = 4\cdot3\cdot2\cdot1$

4! = 24

Giai thừa - Cách lặp

$n! = n\cdot(n-1)\cdot(n-2)\cdot...\cdot1 = $

$ = 1\cdot2\cdot3\cdot...\cdot n$

Cách lặp:

# iterative factorial
def fact_iter(n):
    result = 1
    # looping over numbers from 1 to n
    for num in range(1, n+1)
        result = num * result

    return result

$n = 4:$

result = 1

result = 1 * result(1) = 1
result = 2 * result(1) = 2
result = 3 * result(2) = 6
result = 4 * result(4) = 24

$4! = 1 \cdot 2 \cdot 3 \cdot 4 = 24$

Giai thừa - Cách đệ quy

$n!$ $=n\cdot(n-1)!$

def fact_rec(n):
    return n * fact_rec(n-1)

Sai ở đâu?

fact_rec(4)

RecursionError

Cần định nghĩa điều kiện dừng!

$n! = n\cdot(n-1)\cdot(n-2)\cdot...\cdot1$

Tiêu chí dừng / base case: $1! = 1$

def fact_rec(n):
    if n == 1:
        return 1
    return n * fact_rec(n-1)

fact_rec(4)

Tổng kết

Hàm đệ quy có hai thành phần chính:

lời gọi đệ quy cho một bài toán nhỏ hơn của chính nó
điều kiện dừng (base case) để tránh gọi vô hạn

Ví dụ - Cây quyết định

Cây quyết định

Phân loại bằng cây quyết định

Duyệt cây quyết định

x - mẫu mới $(x_1, x_2)$

# Pseudo algorithm for finding out the category:

category = pred(node, x):

  # Check if there is a split  
  if node.hasSplitting:

    # Check which child node to take
    if node.goToLeftChild(x):
      return pred(node.leftChild, x)   
    if node.goToRightChild(x):
      return pred(node.rightChild, x)

Duyệt cây quyết định

Dự đoán bằng cây quyết định

x - mẫu mới $(x_1, x_2)$

# Pseudo algorithm for finding out the category:

category = pred(node, x):

  # Check if there is a split  
  if node.hasSplitting:

    # Check which child node to take
    if node.goToLeftChild(x):
      return pred(node.leftChild, x) 
    if node.goToRightChild(x):
      return pred(node.rightChild, x)

  # Returning the category
  return node.category

Ayo berlatih!

Luyện tập câu hỏi phỏng vấn lập trình bằng Python