คำนวณจำนวนครั้งที่เรียกใช้ฟังก์ชัน

ลองมาดูตัวอย่างคลาสสิกของ recursion กัน นั่นคือลำดับฟีโบนักชี ซึ่งประกอบด้วยจำนวนเต็มที่ไม่ติดลบโดยเริ่มจาก 0 โดยที่แต่ละสมาชิก \(F(n)\) มีค่าเท่ากับผลรวมของสองสมาชิกก่อนหน้า ได้แก่ 0, 1, 1, 2, 3, 5, 8, 13, 21, ... ฟังก์ชันด้านล่างนี้จะคืนค่า tuple ที่ประกอบด้วยสมาชิกลำดับที่ \(n\) ของลำดับ และจำนวนครั้งที่เรียกใช้ fib():

def fib(n):

  if n < 2:
    return (n, 1)

  fib1 = fib(n-1)
  fib2 = fib(n-2)

  return (fib1[0] + fib2[0], fib1[1] + fib2[1] + 1)

ต้องเรียกใช้ fib() กี่ครั้งในการคำนวณสมาชิกลำดับที่ \(15\) และลำดับที่ \(20\) ของลำดับนี้?