Recursion คืออะไร?

ฝึกทำโจทย์สัมภาษณ์งานเขียนโค้ดด้วย Python

Kirill Smirnov

Data Science Consultant, Altran

นิยาม

Recursion คือกระบวนการนิยามปัญหาโดยอ้างอิงตัวเอง
Recursion คือกระบวนการที่ฟังก์ชันเรียกตัวเองเป็น subroutine

ตัวอย่าง: แฟกทอเรียล $n!$

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

$n = 4$:

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

4! = 24

แฟกทอเรียล - แนวทาง Iterative

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

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

วิธีแบบ Iterative:

# 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$

แฟกทอเรียล - แนวทาง Recursive

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

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

โค้ดนี้มีปัญหาอะไร?

fact_rec(4)

RecursionError

ต้องกำหนด base case ด้วย!

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

เงื่อนไขหยุด / base case: $1! = 1$

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

fact_rec(4)

สรุป

ฟังก์ชัน recursive มีองค์ประกอบหลัก 2 ส่วน:

การเรียกตัวเองซ้ำด้วยปัญหาที่เล็กลง
base case ที่ป้องกันการเรียกซ้ำแบบไม่สิ้นสุด

ตัวอย่าง - Decision Trees

Decision Tree

การจำแนกประเภทด้วย decision tree

การท่องผ่าน Decision Tree

การท่องผ่าน decision tree

x - ตัวอย่างใหม่ $(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)

การท่องผ่าน Decision Tree

การพยากรณ์ด้วย decision tree

x - ตัวอย่างใหม่ $(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

มาฝึกกันเถอะ!

ฝึกทำโจทย์สัมภาษณ์งานเขียนโค้ดด้วย Python