ลองใช้ Recursive ในปัญหา Pascal Triangle

Published in

odds.team

3 min readOct 19, 2018

ลองเอาโจทย์ pascal triangle มาให้ทีมลองเล่นกันตอนทำ code kata รายละเอียดคือ ให้แสดง pascal triangle ตามความสูงที่กำหนด โดยหน้าตาของ pascal triangle จะเป็นแบบนี้

นั่นคือที่ความสูง 1 (h = 1) จะแสดงแค่ “1” ออกมาเฉย ๆ และเมื่อ h = 2 จะแสดงบรรทัดแรกเป็น “1” และบรรทัดที่ 2 เป็น “1 1” ส่วนบรรทัดที่เหลือ จะมีแค่ตัวแรก และตัวสุดท้ายเป็น 1 ส่วนตัวตรงกลาง จะเป็นผลบวกที่เกิดจาก 2 ตัวด้านบนของบรรทัดก่อนหน้ามาบวกกัน

ยกตัวอย่างจากในรูป ที่ h = 6 ในบรรทัดล่างสุดที่เป็นเลข 10 จะเกิดจาก 4 กับ 6 ที่อยู่ด้านบนมาบวกกันนั่นเอง

เล่นกับโจทย์ด้วยลูปธรรมดา

ทีนี้ถ้าเรามองโจทย์นี้แล้วมาเขียนลูปก็น่าจะออกมาประมาณนี้

func printPascalLoop(lines int) {
  arr := [][]int{}  for line := 0; line < lines; line++ {
    arr = append(arr, []int{})
    for i := 0; i <= line; i++ {
      if i == 0 || i == line {
        arr[line] = append(arr[line], 1)
      } else {
        arr[line] = append(arr[line], arr[line-1][i-1]+arr[line-1][i])
      }
      if i > 0 {
        fmt.Print(“ “)
      }
      fmt.Print(arr[line][i])
    }
    fmt.Println()
  }
}

เล่นกับโจทย์ด้วย recursive function

ทีนี้ ถ้าลองมองโจทย์นี้ทีละบรรทัด คือ มี function ที่บอกได้ว่า ที่บรรทัดที่ h ควรจะต้อง print ค่าอะไรออกมา นั่นคือ ตอนเราจะ print pascal triangle เราก็แค่วนลูปเรียกทีละบรรทัดนั่นเอง แบบนี้

func printPascal(lines int) {
  for i := 1; i <= lines; i++ {
    line := pascaltriangle.PascalLine(i)
    for j, n := 0, len(line); j < n; j++ {
      if j > 0 {
        fmt.Print(“ “)
      }
      fmt.Print(line[j])
    }
    fmt.Println()
  }
}

ดังนั้นประเด็นมันจะอยู่ที่ PascalLine จะต้องคืนค่าอะไรกลับมา จากนิยามของ pascal triangle เราจะเห็นลักษณะของ 2 บรรทัดแรก และลักษณะของบรรทัดที่ 3 เป็นต้นไป กับบรรทัดก่อนหน้า เราเลยสามารถเขียนเป็น recursive function ได้แบบนี้

func PascalLineRecursive(line int) []int {
  if line == 1 {
    return []int{1}
  }
  if line == 2 {
    return []int{1, 1}
  }

  prevLine := PascalLineRecursive(line — 1)
  result := []int{1}  for i, n := 0, len(prevLine)-1; i < n; i++ {
    result = append(result, prevLine[i]+prevLine[i+1])
  }  result = append(result, 1)
  return result
}

โดยมี line เป็น 1 และ 2 เป็น base case ส่วน line ตั้งแต่ 3 ขึ้นไปเป็น recursion ทีนี้ ถ้าเราสังเกตให้ดี เราจะเห็นว่าใน recursive นี้มี cost ที่สูงมาก เพราะที่บรรทัดที่ n มันจะต้องไปคำนวณค่าของบรรทัดที่ n-1 มาก่อน ทั้ง ๆ ที่บรรทัดก่อนหน้านี้มันได้เคยคำนวณไว้แล้ว

ใส่ cache

เทคนิคหนึ่งที่เราสามารถเอามาใช้ได้คือการใส่ cache เพื่อเพิ่มความเร็วในการคำนวณ เทคนิคนี้มีชื่ออย่างเป็นทางการว่า Memoization หรือ Tabling เป็นการทำ table หรือ array มาใช้ในการเก็บผลลัพธ์จากการคำนวณที่มี cost ในการคำนวณสูง ๆ เราจะได้ recursive ที่มี cache หน้าตาแบบนี้

var memoTable = map[int][]int{}func PascalLineMemo(line int) []int {
  if v, ok := memoTable[line]; ok {
    return v
  }  if line == 1 {
    return []int{1}
  }
  if line == 2 {
    return []int{1, 1}
  }  prevLine := PascalLineMemo(line — 1)
  result := []int{1}  for i, n := 0, len(prevLine)-1; i < n; i++ {
    result = append(result, prevLine[i]+prevLine[i+1])
  }  result = append(result, 1)  memoTable[line] = result  return result
}