เหตุใดหางนี้จึงเกิดซ้ำ

ตรวจสอบรหัสสกาล่านี้:

def rec(n: Int) {
  if (n > 1) {
    val d = n / 2
    rec(d)
//    if (d > 1)  // abort loop
      rec(n/d)
  }
}

รหัสนี้จะส่งผลให้เกิดการวนซ้ำไม่รู้จบ เนื่องจากการเพิ่มประสิทธิภาพแบบเรียกซ้ำแบบหางฉันจึงไม่ได้รับ StackOverflowError

ถอดรหัสด้วย jad ฉันได้รับโค้ด Java นี้:

public void rec(int n)
{
    int d;
    for(; n > 1; n /= d)
    {
        int i = n;
        d = i / 2;
        rec(d);
    }
}

ในบรรทัดสุดท้ายของลูปเมธอดจะเรียกตัวเอง ดังนั้นฉันจึงไม่เข้าใจตำแหน่งการเรียกส่วนท้าย ใครสามารถอธิบายเรื่องนี้ได้บ้าง?


scala tail-recursion
person kiritsuku    schedule 17.03.2011    source แหล่งที่มา
comment
ซึ่งจะเป็นประโยชน์ 1.cs. wayne.edu/~artem/main/teaching/csc3200ss2006/slides/ 2.stackoverflow.com/questions/105834/   -  person Dead Programmer    schedule 17.03.2011

คำตอบ (2)


arrow_upward
9
arrow_downward

ไม่มีการเรียกหางในกรณีของ rec(d) สำหรับ rec(N) (โดยที่ N > 1) สแต็กจะไม่เพิ่มขึ้นอีกต่อไปหลังจากการเรียก log2(N) (เพราะหลังจากนั้น n จะเท่ากับ 2 หรือ 3 ตลอดไป และ d คือ 1) หลังจากนั้นมันเป็นเพียงการวนซ้ำไม่สิ้นสุดพร้อมกับการเรียก rec(1) ภายในซึ่งจะส่งคืนในแต่ละครั้งทันที นั่นเป็นสาเหตุที่ไม่มีสแต็กโอเวอร์โฟลว์

person hoha    schedule 17.03.2011

arrow_upward
3
arrow_downward

ในรูปแบบการเรียกซ้ำของวิธีการของคุณ คุณจะมีการเรียกซ้ำสองครั้ง StackOverflowError เกิดจากสิ่งสุดท้าย

เนื่องจากการเพิ่มประสิทธิภาพการเรียกซ้ำส่วนท้าย การเรียกครั้งล่าสุดนั้นจะกลายเป็นการวนซ้ำ (ในขณะที่การเรียกครั้งแรกยังคงเป็นการเรียกซ้ำ) ดังนั้นคุณจึงมีการวนซ้ำไม่สิ้นสุดแทนที่จะเป็นการเรียกซ้ำแบบไม่สิ้นสุด และ StackOverflowError จะไม่เกิดขึ้น

person axtavt    schedule 17.03.2011