CoE KKU

stack คือ ลิสต์ที่มีข้อจำกัดที่การดำเนินการเพิ่มและการลบโนดเกิดขึ้นได้ที่ตำแหน่งท้าย เพียงตำแหน่งเดียวเท่านั้นและจะเรียกว่า top การดำเนินการพื้นฐานที่เกิดขึ้นกับ stack คือ push ซึ่งก็คือการบรรจุ (insert) และ pop ซึ่งก็คือการลบ (delete) สมาชิกตัวสุดท้ายที่เพิ่งทำการบรรจุ เราสามารถตรวจค่าของสมาชิกตัวล่าสุดที่ได้บรรจุก่อนทำการ pop ได้ด้วยการทำงานฟังก์ชัน top โดยปกติแล้วการ top และ pop ที่ทำกับ stack ว่างนั้นถือเป็น error ใน stack ADT และการ push ลงใน stack ที่ไม่มีที่ว่างจะไม่ถือเป็น error แต่จะถือเป็นขีดจำกัดของการ implement

บางครั้งจะเรียกโครงสร้าง stack ว่าเป็นโครงสร้างลิสต์แบบ last in, first out (LIFO) รูปที่ 3.37 แสดงแบบจำลองที่เพียงแต่แสดงให้เห็นว่า push คือการ input และ pop และ top เป็นการ output การดำเนินการอื่นที่อาจมีเพิ่มเติมได้ดังเช่นการทำงานเพื่อทำให้มันเป็น stack ว่างหรือการทดสอบว่า stack นั้นเป็น stack ว่างหรือไม่ แต่การดำเนินการที่สำคัญที่ต้องมีเสมอคือ push และ pop รูปที่ 3.38 แสดงสถานะหนึ่งของ stack หลังจากมีการทำงานต่าง ๆ เกิดขึ้น และแบบจำลองทั่วไปคืออาจจะมีสามาชิกอยู่จำนวนหนึ่งแต่จะสามารถมองเห็นได้เฉพาะสมาชิกที่อยู่บนสุดของ stack เท่านั้น

3.3.2 Implementation of Stacks

เนื่องจาก stack เป็น list ดังนั้น implementation ใด ๆ ที่ใช้กับลิสต์ก็สามารถใช้กับ stack ได้ มีวิธีที่นิยมใช้ 2 วิธี คือ การใช้โครงสร้างแบบ linked structure และการใช้อะเรย์

Linked List Implementation of Stacks

เราจะใช้ singly linked list สำหรับวิธีนี้ เราจะทำงาน push โดยการบรรจุสมาชิกเข้าไปยังหัวลิสต์ การทำงานของ pop เป็นการลบสมาชิกที่อยู่ที่หัวลิสต์ และ top เป็นการทำงานการตรวจดูค่าที่หัวลิสต์และส่งค่าดังกล่าวกลับ บางกรณีอาจจะมีการทำงานที่เป็นการทำงานรวมกันของ top และ pop เป็นการทำงานเดียว รูปที่ 3.39 แสดงโครงร่างของคลาสโดยเราใช้ stack ที่ไม่ต้องใช้ header และ stack มีขนาดไม่จำกัด (ไม่มีวันเต็ม)

การทำงานของ push เป็นการบรรจุหน่วยข้อมูลลงที่หัวของลิสต์ซึ่งเป็นเสมือนกับส่วนบน (top) ของ stack (ดูรูปที่ 3.40)

ฟังก์ชัน top จะทำงานการตรวจสอบค่าที่อยู่ที่ตำแหน่งแรกของลิสต์ (ดูรูปที่ 3.41)

การทำงานของ pop จะเป็นการลบข้อมูลออกที่ตำแหน่งหัวของลิสต์ตามรูปที่ 3.42 ซึ่งเพียงแต่เลื่อน topOfStack ไปข้างหน้า และให้ถึงเป็น exception ถ้า stack ว่าง รูปที่ 3.43 แสดงฟังก์ชัน topAndPop ซึ่งให้ค่าที่มันอ้างอิงอยู่และจะลบออกจากโครงสร้างด้วยและให้ค่าเป็น null กรณีที่ stack ว่าง

public class StackLi 
{   public StackLi( )   { topOfStack = null; }
    public boolean isFull( )  { return false; }
    public boolean isEmpty( )  { return topOfStack == null; }
    public void makeEmpty( )  { topOfStack = null; }
    public void push( Object x )  { /* Figure 3.40 */}
    public Object top( )  { /*Figure 3.41 */ }
    public void pop( ) throws Underflow  {/*Figure 3.42 */ }
    public Object topAndPop( )  {/*Figure 3.43 */}
    private ListNode topOfStack;
}

รูปที่ 3.39 โครงร่างของคลาส stack ADT ที่ใช้ linked structure

public void push( Object x )  
{    topOfStack = new ListNode( x, topOfStack );   
} 

รูปที่ 3.40 ฟังก์ชัน push

public Object top( )
{   if( isEmpty( ) )
        return null;
    return topOfStack.element;
}

รูปที่ 3.41 ฟังก์ชัน top

public void pop( ) throws Underflow
{   if( isEmpty( ) )
        throw new Underflow( );
    topOfStack = topOfStack.next;
} 

รูปที่ 3.42 ฟังก์ชัน pop

public Object topAndPop( )
{   if( isEmpty( ) )
        return null;
    Object topItem = topOfStack.element;
    topOfStack = topOfStack.next;
    return topItem;
} 

รูปที่ 3.43 ฟังก์ชัน topAndPop

เห็นได้ชัดว่าการดำเนินการทั้งหมดใช้เวลาคงที่ เนื่องจากไม่มีส่วนไหนในคำสั่งที่เป็นการอ้างถึงขนาดของ stack เลย ข้อเสียที่มีของการใช้งาน stack ด้วยวิธีนี้คือ การเรียกใช้ new เป็นการทำงานที่เสียค่าใช้จ่ายสูง

Array Implementation of Stacks

การใช้ Stacks ด้วยการใช้อะเรย์เป็นทางเลือกในการหลีกเลี่ยงการใช้ pointers เป็นตัวเชื่อมต่อหน่วยข้อมูลและเป็นวิธีที่นิยมใช้กัน ข้อเสียประการเดียวของการใช้อะเรย์คือ เราจะต้องกำหนดขนาดของอะเรย์ล่วงหน้านั่นเอง อย่างไรก็ตามนี่ไม่ใช่ปัญหาในการใช้มันกับ stack ทั้งนี้เนื่องจากว่าปกติแล้วจำนวนสมาชิกใน stack มีจำนวนไม่มากนัก จึงง่ายที่จะกำหนดขนาดไว้ล่วงหน้าโดยไม่สูญเสียเนื้อที่มากนัก

การใช้อะเรย์ในกรณีนี้ไม่ได้มีความซับซ้อนใด ๆ ในแต่ละ stack ประกอบด้วย theArray และ topOfStack ซึ่งมีค่า -1 เมื่อ stack เป็น stack ว่าง และเป็นสถานะเริ่มต้นของมันด้วย ในการบรรจุ (push) สมาชิกใหม่ x ลงใน stack เราจะเพิ่มค่าของ topOfStack และกำหนดให้ theArray[topOfStack] มีค่า x การ pop เป็นการกำหนดของ theArray[topOfStack] ให้กับค่าที่จะส่งกลับและลดค่าของ topOfStack ลง

การทำงานที่กล่าวมาข้างบนใช้เวลาคงที่ที่เร็วมาก ในคอมพิวเตอร์บางแบบมันสามารถทำงานได้ใน 1 machine instruction ด้วยการทำงานใน register ที่เป็นแบบ auto-increment และ auto-decrement

โครงร่างของคลาส stack StackAr แสดงไว้ในรูปที่ 3.44 ส่วนฟังก์ชันอื่น ๆ ไม่ได้มีความซับซ้อนใด ๆ และแสดงไว้ในรูปที่ 3.45 ถึง 3.49

public class StackAr 
{   public StackAr( ) { /* Figure 3.45 */ }
    public StackAr( int capacity ) {/* Figure 3.45 */ }
    public boolean isEmpty( ) {return topOfStack == -1;}
    public boolean isFull( )  { return topOfStack == theArray.length - 1;}
    public void makeEmpty( ) { topOfStack = -1; }
    public void push( Object x ) throws Overflow  {/* Figure 3.46 */ }
    public Object top( ) {/* Figure 3.47 */ }
    public void pop( ) throws Underflow {/* Figure 3.48 */ }
    public Object topAndPop( )  {/* Figure 3.49 */ }
    private Object [ ] theArray;
    private int        topOfStack;
    static final int DEFAULT_CAPACITY = 10;
}

รูปที่ 3.44 โครงร่างของคลาส StackAr

public StackAr( )  {  this( DEFAULT_CAPACITY );   }
public StackAr( int capacity )
{   theArray = new Object[ capacity ];
    topOfStack = -1;
}

รูปที่ 3.45 Stack construction – array implementation

/* Insert a new item into the stack, if not already full.
 * @param x the item to insert.
 * @exception Overflow if stack is already full.     */
public void push( Object x ) throws Overflow
{   if( isFull( ) )
        throw new Overflow( );
    theArray[ ++topOfStack ] = x;
} 

รูปที่ 3.46 ฟังก์ชัน push

/* Get the most recently inserted item in the stack. Does not alter the stack.
 * @return the most recently inserted item in the stack, or null, if empty.  */
public Object top( )
{   if ( isEmpty( ) )
        return null;
    return theArray[ topOfStack ];
} 

รูปที่ 3.47 ฟังก์ชัน top

/* Remove the most recently inserted item from the stack.
 * @exception Underflow if stack is already empty.     */
public void pop( ) throws Underflow
{   if ( isEmpty( ) )
        throw new Underflow( );
    theArray[ topOfStack-- ] = null;
}

รูปที่ 3.48 ฟังก์ชัน pop

/** Return and remove most recently inserted item from the stack.
 * @return most recently inserted item, or null, if stack is empty. */
public Object topAndPop( )
{   if ( isEmpty( ) )
           return null;
    Object topItem = top( );
    theArray[ topOfStack-- ] = null;
    return topItem;
} 

รูปที่ 3.49 ฟังก์ชัน topAndPop

มีการนำ stack ไปประยุกต์ใช้งานได้หลากหลาย แต่ในที่นี้จะกล่าวถึงเพียง 4 ตัวอย่าง

Balancing Symbols

ในหัวข้อนี้จะได้กล่าวถึงการตรวจสอบการสมดุลของอักขระบางชนิดในสตริงที่จะต้องใช้เป็นคู่เช่นอักขระตัวเปิดต้องมีตัวที่เป็นตัวปิดคู่กันที่ถูกต้องตามลำดับมิฉะนั้นจะถือว่าผิด อักขระดังกล่าวเช่น parentheses, brackets, และ braces ที่ต้องใช้ร่วมกันเป็นคู่และมีลำดับของอักขระเปิดและปิดถูกต้องด้วย เช่นลำดับ [()] เช่นนี้ถูกต้อง แต่ลำดับ [(]) ผิดและในที่นี้จะละเลยอักขระอื่น ๆ ในสตริง

อัลกอริทึมอย่างง่ายที่ใช้มีดังนี้:

สร้าง empty stack และอ่านอักขระจนจบไฟล์

• ถ้าพบสัญลักษณ์ตัวเปิดก็จะ push ลงใน stack
• ถ้าสัญลักษณ์ที่อ่านมาเป็นตัวปิดและใน stack ยังว่างอยู่ก็ให้รายงานความผิดพลาด
  • แต่ถ้ามีสัญลักษณ์ใน stack ก็ให้ทำการ pop
    • ถ้าสัญลักษณ์ที่ pop มานั้นไม่ใช่สัญลักษณ์ตัวเปิดที่สอดคล้องกับตัวปิดที่อ่าน ก็ให้รายงานความผิดพลาด

เมื่อจบไฟล์แล้วยังมีสัญลักษณ์เหลือใน stack ก็ให้รายงานความผิดพลาด

Postfix Expressions

postfix expression เป็นลำดับของ operators และ operands ขณะจะทำงานตามตัว operator นั้น จะต้องรู้ค่าของ operands แล้วเสมอ การใช้ postfix expression ทำให้ไม่จำเป็นต้องรู้ precedence หรือ associativity ของ operator

ถ้าเราใช้เครื่องคำนวณแบบธรรมดาเพื่อคิดราคาค่าสินค้าจำนวน 3 รายการ โดยที่รายการแรกและรายการที่สามมีการคิดค่าภาษีด้วย 6% ส่วนรายการที่ 2 ไม่เสียภาษี และคำนวณราคาทั้งหมดด้วยการกดปุ่มทำงานตามลำดับการทำงาน ดังนี้

4.99 * 1.06 + 5.99 + 6.99 * 1.06 =

เครื่องคำนวณธรรมดาจะให้ผลที่ผิดได้ คือ 19.365 แต่ถ้าใช้เครื่องคำนวณวิทยาศาสตร์ (scientific calculator) ก็จะให้ผลตามต้องการคือ 18.69

ทั้งนี้เพราะเหตุว่าเครื่องคำนวณวิทยาศาสตร์รู้ลำดับความสำคัญของตัวดำเนินการนั่นเอง นอกจากนี้เครื่องคำนวณวิทยาศาสตร์ยังมีปุ่มวงเล็บให้เราสามารถจัดลำดับก่อนหลังของตัวดำเนินการได้ด้วย

ความจริงแล้วลำดับการคำนวณค่าของนิพจน์ข้างบนนี้คือ คูณ 4.99 และ 1.06 แล้วเก็บผลไว้เช่นใน A1 จากนั้นบวก 5.99 เข้ากับ A1 แล้วเก็บผลไว้ใน A1 จากนั้นคูณ 6.99 และ 1.06 เก็บผลไว้ใน A2 และจบด้วยการบวก A1 และ A2

เข้าด้วยกันเก็บผลไว้ใน A1 จะเห็นว่าเราสามารถเขียนเป็นลำดับการทำงานที่กล่าวมานี้ได้ดังนี้

4.99 1.06 * 5.99 + 6.99 1.06 * +

รูปแบบดังที่เขียนนี้เรียกว่า postfix หรือ reverse Polish notation และการคำนวณค่าก็เป็นไปตามลำดับที่กล่าวข้างบนแล้ว วิธีการคำนวณที่กล่าวนี้สามารถใช้ stack ช่วยในการทำงานได้

โดยถ้าตัวที่อ่านเป็นตัวเลข เราจะ push ลงใน stack ถ้าเป็น operator ก็จะ pop ตัวเลข 2 ตัวใน stack มาทำงานด้วย operator นั้น (สมมุติเป็น binary operators)

สำหรับ binary operators หน่วยข้อมูลที่ถูก pop ออกมาก่อนจะเป็น operand ตัวที่สอง และทำการ push ผลที่ได้กลับลงใน stack

จะเห็นว่าถ้าเราเขียนนิพจน์ให้อยู่ในรูปของ postfix expression การคำนวณผลตามลำดับก็จะได้ผลถูกต้องโดยไม่ต้องกังวลกับลำดับความสำคัญของ operator

ตัวอย่างของ postfix expression 6 5 2 3 + 8 * + 3 + * ซึ่งมีลำดับการทำงาน

• Push 6, Push 5, Push 2, Push 3
• พบ +, ให้ Pop 3, Pop 2, หาค่า 2 + 3, แล้ว Push ผลลัพธ์ 5
• Push 8
• พบ *, Pop 8, Pop 5, หาค่า 5 * 8, แล้ว Push ผลลัพธ์ 40
• พบ +, Pop 40, Pop 5, หาค่า 5 + 40, แล้ว Push ผลลัพธ์ 45
• Push 3
• พบ +, Pop 3, Pop 45, หาค่า 45 + 3, แล้ว Push ผลลัพธ์ 48
• พบ *, Pop 48, Pop 6, หาค่า 6 * 48, แล้ว Push ผลลัพธ์ 288

เมื่อจบนิพจน์แล้วใน stack จะเหลือข้อมูลตัวเดียวคือ คำตอบ ดังแสดงในรูปที่ 3.50

การเปลี่ยนจาก Infix ไปเป็น Postfix

นอกจากเราจะใช้ stack ในการหาค่าของนิพจน์แบบ postfix ได้แล้ว เรายังสามารถใช้ stack ในการเปลี่ยนรูปแบบของนิพจน์แบบ infix ไปเป็นแบบ postfix ได้ด้วย โดยในที่นี้จะจำกัดเฉพาะ operator +, *, (, ) และคงลำดับความสำคัญเหมือนเดิม เช่นต้องการเปลี่ยนรูปนิพจน์ infix:

a + b * c + ( d * e + f ) * g

เป็นรูปแบบ postfix ก็จะได้ a b c * + d e * f + g * + ซึ่งเราสามารถใช้โครงสร้างข้อมูลแบบ stack เป็นตัวช่วยเปลี่ยนนิพจน์ในรูปแบบ infix ไปเป็น postfix ได้

ขั้นตอนวิธีที่ใช้ คือ เริ่มต้นการทำงานด้วยการกำหนดให้มี stack ว่าง และเริ่มอ่านอักขระของนิพจน์จากตัวแรก ถ้าตัวที่อ่านเข้ามาเป็น operand ก็จะส่งออก output ทันที ถ้าพบ operator ก็จะถูก push ลงใน stack (วงเล็บเปิดก็เช่นกัน) ถ้าพบวงเล็บปิด เราจะทำการ pop สิ่งที่อยู่ใน stack แล้วเขียนออกจนกว่าจะพบกับวงเล็บเปิดที่สอดคล้องกันกับวงเล็บปิดที่อ่านเข้ามาก็จะ pop แต่ไม่ต้องส่งออกไปที่ output ในกรณีที่เป็นการ pop ตัว operator หลาย ๆ ตัวจาก stack นั้นจะเกิดขึ้นจนกระทั่งพบกับตัววงเล็บเปิดใน stack ก็จะหยุดการ pop นี้ สุดท้ายเมื่ออ่านอักขระของนิพจน์ตัวสุดท้ายแล้วก็ให้ pop สิ่งที่อยู่ใน stack จนหมด

รายละเอียดที่ยังไม่ได้กล่าวถึงก็คือเกณฑ์ที่ใช้ในการพิจารณาว่าจะทำการ pop ตัว operator จาก stack หรือไม่เมื่ออ่านอักขระของอินพุตเป็นตัว operator

การ Pop ตัว Operator ใน Stack

• ตัว operator ที่อยู่บนสุดของ stack จะถูก pop ออกและส่งออก output ถ้า precedence และ associativity rules แสดงให้เห็นว่ามันจะต้องทำงานก่อนตัว operator ที่อ่านมาในขณะนั้น กล่าวคือ
• ถ้า operator ตัวที่อ่านจากอินพุตเข้ามาในขณะนั้น มี precedence ต่ำกว่า operator ที่อยู่บน stack ก็ให้ pop ตัว operator นั้นออกจาก stack และถ้าหากการอ่านอินพุตตัวนี้เป็นการจบอินพุตแล้วก็ให้ทำการ pop จนกว่าจะหมด stack แล้วเขียนออก output
• Associativity ของ operator จะเป็นตัวตัดสินว่าจะทำอย่างไรในกรณีที่ operator ตัวที่อ่านมาจากอินพุตขณะนั้นมี precedence เท่ากับ operator ที่อยู่บน stack คือ
  • ถ้า operator เป็น left associative ก็ให้ pop ตัว operator ที่อยู่บน stack แล้วส่งออก output เช่น 4 – 4 – 4 ⇒ 4 4 – 4 –
  • ถ้า operators เป็น right associative ก็ไม่ต้อง pop ตัว operator ที่อยู่บน stack 2 ^ 2 ^ 3 ⇒ 2 2 3 ^ ^

ตัวอย่างข้างล่างแสดงให้เห็นขั้นตอนวิธีที่กล่าวมาข้างบนนี้เพื่อเปลี่ยนรูปนิพจน์ a + b * c + ( d * e + f ) * g ซึ่งอยู่ในรูปแบบ infix ให้เป็นรูปแบบ postfix

เริ่มต้นด้วยการอ่านอักขระ a และส่งออก output จากนั้นเป็นเครื่องหมาย + ก็จะ push ลงบน stack ตามด้วยอ่าน b และส่งออก output ซึ่งแสดงสถานการณ์ทำงานตามรูปข้างล่างนี้

จากนั้นอ่านอักขระ * รายการแรกของ stack คือ + ซึ่งมี precedence ต่ำกว่า * จึง push ตัว * ลงใน stack จากนั้นอ่านอักษร c จะได้ดังรูปข้างล่าง

อักขระตัวต่อไปคือเครื่องหมาย + ตรวจ stack พบว่าต้อง pop เครื่องหมาย * แล้วส่งออก output และต้อง pop เครื่องหมาย + ใน stack และส่งออก output เนื่องจากมันมี precedence เท่ากับเครื่องหมายที่อ่านอยู่ในขณะนี้ (+) จากนั้นจะ push เครื่องหมาย + ที่อ่านลงใน stack จะได้สถานการณ์ทำงานดังนี้

อ่านตัว ( ซึ่งเป็นตัวที่มี precedence สูงสุด push ลงใน stack จากนั้นอ่าน d และส่งออก output จะได้ดังรูปข้างล่าง

ตัวต่อไปที่อ่าน คือ * เนื่องจากวงเล็บเปิดที่อยู่ใน stack จะไม่ถูก pop จนกว่าจะเป็นขณะที่มีการอ่านตัววงเล็บปิดเท่านั้น ดังนั้นจึง push เครื่องหมาย * ที่อ่านนี้ลงใน stack จากนั้นเป็นการอ่านตัว e และส่งออก output จะได้ดังรูปข้างล่าง

ถัดไปอ่านเครื่องหมาย + ซึ่งต้อง pop เครื่องหมาย * ส่งออก output และ push เครื่องหมาย + จากนั้นอ่านตัว f จะได้ดังรูปข้างล่าง

ต่อไปเป็นการอ่านตัว ) ซึ่งทำให้ต้อง pop จนกระทั่งตัวเครื่องหมาย ( และส่งเครื่องหมาย + ออก output ดังรูปข้างล่างนี้

ต่อไปอ่านเครื่องหมาย * ซึ่งต้อง push ลงใน stack จากนั้นอ่าน g และส่งออก output ได้ดังรูป

ขณะนี้เป็นอันจบการอ่านอินพุตจากนี้จะเป็นการ pop สิ่งอยู่ใน stack ทั้งหมดออกมาและจะได้ output ดังรูป

ข้างล่างนี้เป็นอีกตัวอย่างหนึ่งที่แสดงให้เห็นการใช้ stack เพื่อเปลี่ยนรูปแบบ infix จาก 1-2^3^3-(4+5*6)*7 ไปเป็นรูปแบบ postfix ที่ได้คือ 1 2 3 3 ^ ^ - 4 5 6 * + 7 * - ตามลำดับการทำงานในรูปข้างล่างนี้

Method Calls

การทำงานการเรียกใช้ method ทั้งในภาษาที่เป็นแบบ procedural และแบบ object-oriented ก็มีลักษณะเดียวกับการทำงานการตรวจสมดุลของสัญลักษณ์ method call และ method return ก็เหมือนกันกับ open parenthesis และ closed parenthesis กล่าวคือ เมื่อมีการเรียกใช้ method ใหม่ ตัวแปรทั้งหมดที่เป็น local ของ routine ที่เป็นผู้เรียกจะต้องถูกจัดเก็บโดยระบบ

เนื่องจากฟังก์ชันใหม่ที่จะทำงานอาจจะทำการเขียนค่าทับค่าตัวแปรเดิมในตำแหน่งเดียวกันในหน่วยความจำ นอกจากนั้นตำแหน่งปัจจุบันใน routine ที่เป็นผู้เรียกใช้ method อื่นจะได้รับการจัดเก็บเพื่อว่า method ใหม่ที่ถูกเรียกใช้จะกลับมายังตำแหน่งเดิมได้เมื่อมันทำงานเสร็จ

การทำงานที่กล่าวมานี้ล้วนใช้ stack ในการทำงานรวมทั้งที่เป็น recursive ก็เช่นเดียวกัน สารสนเทศที่ถูกจัดเก็บดังกล่าวนั้น เรียกว่า activation record หรือ stack frame ตัวแปรสภาพแวดล้อมในขณะนั้น ๆ จะถูกจัดเก็บไว้ที่ส่วนบนสุดของ stack การจัดการ stack ใน register และหน่วยความจำนั้นนักศึกษาสามารถศึกษาได้จากหนังสือหรือเอกสารที่เกี่ยวกับฮาร์ดแวร์และซีพียูและเรื่องระบบปฏิบัติการของคอมพิวเตอร์ และเป็นเรื่องที่เป็นไปได้ที่เนื้อที่ใน stack อาจจะมีขนาดไม่พอเพียงได้ในกรณีที่มีการเรียกใช้ฟังก์ชันมากเกินไปและจะเกิดสิ่งที่เรียกว่า fatal error ซึ่งเป็นเรื่องปกติที่เกิดขึ้นได้เสมอ

อย่างไรก็ตามในภาวะปกติแล้วปัญหาดังกล่าวนี้มักไม่ค่อยเกิดขึ้น ถ้าจะเกิดปัญหาในลักษณะดังกล่าวนี้ขึ้นก็มักจะมีสาเหตุจากการใช้ recursion ที่ไม่มี base case เท่านั้น (runaway recursion) อย่างไรก็ตามโปรแกรมบางโปรแกรมที่เขียนขึ้นดูเหมือนจะทำงานได้ถูกต้องนั้นอาจจะก่อให้เกิดการใช้เนื้อที่ stack มากจนไม่พอเพียงก็ได้ รูปที่ 3.51 เป็นฟังก์ชันเพื่อการแสดงค่าของ linked list (โดยเริ่มต้นที่โนดใด ๆ โนดหนึ่ง) ซึ่งเป็นฟังก์ชันที่ถูกต้องสมบูรณ์ แต่โชคไม่ดีถ้าหากว่าลิสต์ของเรามีจำนวนสมาชิกมาก ๆ เช่น 20000 ตัว ที่จะต้องพิมพ์ออกมา หมายความว่าเราต้องใช้ stack ขนาด 20000 เพื่อจัดเก็บสารสนเทศในการเรียกใช้ฟังก์ชันในบรรทัดที่ 4 ซึ่งมีแนวโน้มที่จะเกิด stack overflow

public static void printList( ListNode p )
{
/*1*/     if (p == null)
/*2*/	    return;
/*3*/     System.out.println(p.element );
/*4*/     printList( p.next );
}

รูปที่ 3.51 การใช้ recursion ที่ไม่ดีเพื่อพิมพ์ค่าสมาชิกของ linked list

ตัวอย่างที่กล่าวมานี้เป็นตัวอย่างของการการเขียนโปรแกรมแบบ recursion ที่ไม่ดีที่เรียกว่าเป็นโปรแกรมแบบ tail recursion ซึ่งใช้เรียกโปรแกรมที่มีการเรียกใช้แบบ recursion อยู่ในตำแหน่งบรรทัดสุดท้าย เราสามารถขจัด tail recursion ออกได้ด้วยการใช้ iteration เช่นด้วยคำสั่ง while-loop และแทนที่ recursive call ด้วย assignment หนึ่งสำหรับ argument ของฟังก์ชัน และกลับขึ้นไปทำงานในตำแหน่งเริ่มต้น loop ได้ทันที เนื่องจาก recursive call เองไม่จำเป็นต้องจัดเก็บค่าใด ๆ ไว้ใช้งานเลยหลังการเรียก recursive call ดังกล่าวนี้ทำงานเสร็จสิ้นลง รูปที่ 3.52 แสดงฟังก์ชันที่ทำงานเช่นเดียวกับรูปที่ 3.51 แต่ได้ใช้ iteration แทน recursive call เพื่อขจัด tail recursion

public static void printList( ListNode p )
{
    while ( true )
    {
	    if ( p == null )
	        return;
        System.out.println(p.element );
        p =  p.next;
    }
 }

รูปที่ 3.52 ฟังก์ชันพิมพ์สมาชิกของลิสต์ที่ใช้ iteration แทน recursive call

ปกติแล้วเราสามารถใช้ iteration แทนที่การใช้ recursive call ได้เสมอเพียงแต่บางกรณีอาจจะต้องเขียนโปรแกรมที่ยุ่งยากมากแต่ทว่าการใช้ iteration จะทำให้โปรแกรมทำงานได้เร็วกว่าการใช้ recursive call อย่างไรก็ตาม การใช้ recursive call จะทำให้โปรแกรมมีความชัดเจนในแง่ที่สามารถแสดงออกถึงผลที่จะได้จากโปรแกรมได้มากกว่าการใช้ iteration