recursion.tx

\chapter{การเรียกตัวเอง}

การเรียกตัวเองเป็นแนวคิดที่ทรงพลังมาก
เราจะทำความเข้าใจกับแนวคิดดังกล่าวผ่านทางตัวอย่างและคำถาม
เราจะเริ่มจากปัญหาที่ง่ายและตรงไปตรงมาซึ่งสามารถแก้ไขได้ด้วยอัลกอริทึมแบบวนซ้ำทั่วไป
เราจะพิจารณาปัญหาที่ยากขึ้นในตอนท้ายของบทนี้
อย่างไรก็ตามแนวคิดของการเรียกตัวเองจะเป็นแนวคิดพื้นฐานในการทำความเข้าใจโครงสร้างข้อมูลที่เราจะศึกษาในบทอื่น ๆ ด้วย

% TODO: appendix functions
ในการทำความเข้าใจกับการเรียกตัวเองนั้น ต้องใช้ความรู้พื้นฐานเกี่ยวกับโปรแกรมย่อย
(function ในภาษา C++)
ผู้อ่านสามารถทบทวนได้ที่ภาคผนวก~\ref{appendix:functions}

เราจะเริ่มจากปัญหาเกี่ยวกับการคำนวณที่ข้อมูลป้อนเข้าเป็นจำนวนเต็ม
จากนั้นจะพิจารณาปัญหาที่ข้อมูลป้อนเข้ามีลักษณะเป็นรายการ เช่น ปัญหาการหาค่ามากที่สุด
และปัญหาการจัดเรียงข้อมูล 

\section{การคำนวณทางพีชคณิต}

เราจะเขียนโปรแกรมย่อยที่บวกจำนวนธรรมชาติสองจำนวน ตัวอย่างของโปรแกรมย่อยนี้แสดงดังด้านล่าง

---algt บวกจำนวนธรรมชาติ $A$ กับ $B$
* คำนวณค่า $A+B$ แล้วคืนผลลัพธ์
---

เมื่อเราเรียกใช้โปรแกรมย่อยดังกล่าวให้บวก 10 กับ 3 เราจะได้ผลลัพธ์เป็น 13
ลักษณะของการเรียกใช้ แสดงในรูป~\ref{rec:add-call}

\begin{figure}
\begin{center}
\epsfig{file=figures/recursion/add-call.eps, height=1in}
\end{center}
\caption{ตัวอย่างการเรียกใช้โปรแกรมย่อย}
\label{rec:add-call}
\end{figure}

เราจะปรับโปรแกรมย่อยดังกล่าว ให้เป็นโปรแกรมย่อยแบบเรียกตัวเอง
สมมติว่าเราทราบวิธีการเพิ่มค่าจำนวนธรรมชาติขึ้น 1 และลดค่าจำนวนธรรมชาติลง 1
พิจารณาวิธีการบวกจำนวนธรรมชาติ $A$ เข้ากับ $B$
ดังอัลกอริทึมที่~\ref{algo:rec-int-add}

\begin{figure}
---algt[algo:rec-int-add] บวกจำนวนธรรมชาติ $A$ กับ $B$
* IF $B=0$ THEN RETURN $A$ and EXIT
* ELSE
** LET $C\leftarrow B-1$
** ให้ $D$ เท่ากับผลบวกของ $A$ กับ $C$
** RETURN $D+1$
---
\end{figure}

นิยามข้างต้นมีลักษณะเหมือนงูกินหาง
เพราะว่าเรากำลังนิยามการบวกจำนวนธรรมชาติด้วยการบวกจำนวนธรรมชาติ อย่างไรก็ตาม
เราจะละความสงสัยดังกล่าวไว้ก่อนแล้วทดลองบวก 10 กับ 3 ดังนี้

---ui
* เนื่องจาก $3$ ไม่เท่ากับ $0$ เราจึงคำนวณค่า $3-1 = 2$
จากนั้นเราต้องการคำนวณหาผลบวกของ $10$ กับ $2$ เมื่อได้ผลบวกแล้ว เราจะเพิ่มค่าขึ้น
$1$ เพื่อได้ผลบวกของ $10$ กับ $3$ ตามต้องการ
---

\begin{figure}
\begin{center}
\epsfig{file=figures/recursion/add-2-calls.eps, height=1in}
\end{center}
\caption{ตัวอย่างการเรียกใช้โปรแกรมย่อยที่เรียกใช้โปรแกรมย่อยเพื่อคำนวณผลบวกของ 10 กับ 2}
\label{rec:add-2-calls}
\end{figure}


จากขั้นตอนด้านบน ถ้าเราทราบว่าผลบวกของ $10$ กับ $2$ คือ $12$ เมื่อเพิ่มค่าขึ้น $1$
เราจะได้ผลลัพธ์ของ $10$ กับ $3$ ซึ่งมีค่าเท่ากับ $13$ \ \ \
รูป~\ref{rec:add-2-calls} แสดงการทำงานของโปรแกรมย่อยดังกล่าว


---q 10 + 2
เราจะหาผลลัพธ์ของการบวก $10$ กับ $2$ ได้อย่างไร?
---

เราก็จะหาผลลัพธ์ด้วยวิธีเดียวกัน ซึ่งในการผลบวก เราจะต้องหาผลลัพธ์ของการบวก $10$ กับ
$1$ และจะเป็นเช่นนี้เป็นเรื่อย ๆ ดังตัวอย่างด้านล่าง (รูปที่~\ref{rec:add-rec-calls}
แสดงลักษณะการคำนวณ)


---ui
* เนื่องจาก $3$ ไม่เท่ากับ $0$ เราจึงคำนวณค่า $3-1 = 2$ จากนั้นเราต้องการคำนวณหาผลบวกของ $10$ กับ $2$ ในการคำนวณผลบวกดังกล่าว เราจะใช้วิธีการเดิม
** เนื่องจาก $2$ ไม่เท่ากับ $0$ เราจึงคำนวณค่า $2-1 = 1$ จากนั้นเราต้องการคำนวณหาผลบวกของ $10$ กับ $1$ ในการคำนวณผลบวกดังกล่าว เราจะใช้วิธีการเดิม
*** เนื่องจาก $1$ ไม่เท่ากับ $0$ เราจึงคำนวณค่า $1-1 = 0$ จากนั้นเราต้องการคำนวณหาผลบวกของ $10$ กับ $0$ ในการคำนวณผลบวกดังกล่าว เราจะใช้วิธีการเดิม
**** เนื่องจาก $0$ เท่ากับ $0$ ผลลัพธ์ของการบวก $10$ กับ $0$ คือ $10$
*** เมื่อเราได้ผลลัพธ์ของการบวก $10$ กับ $0$ แล้ว (คือ $10$) เราคำนวณ $10+1$ ได้ผลลัพธ์ $11$ ซึ่งเป็นผลลัพธ์ของการบวก $10$ กับ $1$
** เมื่อเราได้ผลลัพธ์ของการบวก $10$ กับ $1$ แล้ว (คือ $11$) เราคำนวณ $11+1$ ได้ผลลัพธ์ $12$ ซึ่งเป็นผลลัพธ์ของการบวก $10$ กับ $2$
* เมื่อเราได้ผลลัพธ์ของการบวก $10$ กับ $2$ แล้ว (คือ $12$) เราคำนวณ $12+1$ ได้ผลลัพธ์ $13$ ซึ่งเป็นผลลัพธ์ของการบวก $10$ กับ $3$
---


\begin{figure}
\begin{center}
\epsfig{file=figures/recursion/add-rec-calls.eps, width=6in}
\end{center}
\caption{ตัวอย่างการเรียกใช้โปรแกรมย่อยที่เรียกตัวเอง}
\label{rec:add-rec-calls}
\end{figure}


---q การลบ
เขียนขั้นตอนการลบจำนวนธรรมชาติ $A$ กับ $B$ ในรูปแบบเดียวกับการคำนวณผลบวก
---

---q การคูณ
เขียนขั้นตอนการคูณจำนวนธรรมชาติ $A$ กับ $B$ ในรูปแบบเดียวกับการคำนวณผลบวก
---

---q ศูนย์
ถ้าเราตัดบรรทัดแรกที่ระบุเงื่อนไขที่ทำงานเมื่อ $B=0$ ออก  เมื่อเราดำเนินการตามขั้นตอนวิธีดังกล่าว ผลลัพธ์จะเป็นเช่นใด
---

เราสามารถเขียนอัลกอริทึมดังกล่าวเป็นโปรแกรมได้ไม่ยากดังนี้

---src[cpp]
int add(int a, int b)
{
  if(b==0)
    return a;

  int c = b-1;
  return 1 + add(a,c);
}
---

\section{ค่าสูงสุด}

เราจะออกแบบอัลกอริทึมแบบเรียกตัวเองสำหรับการคำนวณค่าสูงสุด กล่าวคือ
ให้อาร์เรย์ $A$ ของจำนวนเต็ม $n$ จำนวน เราต้องการคำนวณค่าสูงสุด

กรณีที่เราสามารถตอบคำถามได้ง่าย คือกรณีที่ $n=1$
กล่าวคือเราสามารถตอบได้ทันทีว่าค่าสูงสุดเท่ากับ $A[0]$

---algt การคำนวนค่าสูงสุดของอาร์เรย์ $A$ ที่มีสมาชิก $n$ ตัว (ขั้นฐาน)
* IF $n=1$ THEN RETURN $A[0]$ and EXIT
* ELSE
** {\em จะต้องออกแบบต่อไป}
---

สำหรับบทนี้เพื่อความสะดวกในการเขียน
แทนที่เราจะเรียกข้อมูลในอาร์เรย์โดยเขียนในวงเล็บเหลี่ยม เช่น $A[4]$ หรือ $A[i]$
เราจะเขียนเป็นตัวห้อย เช่น $A_4$ หรือ $A_i$
และจะเขียนอาร์เรย์โดยระบุข้อมูลในอาร์เรย์ในวงเล็บเหลี่ยม เช่น อาร์เรย์
$[2,3,5,7,11]$ เป็นต้น

สำหรับกรณีทั่วไป เราจะเริ่มโดยพิจารณาปัญหาเมื่อข้อมูลนำเข้ามีขนาดเล็กลง โดยเราจะให้
\[
A' = [A_0,A_1,\ldots,A_{n-2}]
\]
นั่นคือ $A'$ คืออาร์เรย์ $A$ ที่ตัดข้อมูลตัวสุดท้ายทิ้งไป

ปัญหานี้เราจะเรียกว่า {\em ปัญหาย่อย} (subproblem)
เราจะสมมติว่าเราสามารถหาคำตอบของปัญหาได้ กล่าวคือ
ให้ $M$ คือค่าสูงสุดของอาร์เรย์ $A'$

---q ค่าสูงที่สุดจาก $M$
สมมติว่าเราทราบว่า $M$ คือค่าสูงสุดของอาร์เรย์ $A'= [A_0,A_1,\ldots,A_{n-2}]$
เราสามารถคำนวณค่าสูงสุดของอาร์เรย์ 
$A= [A_0,A_1,\ldots,A_{n-1}]$
ได้อย่างไร?

(คำใบ้: ถ้า $M$ ไม่ใช่ข้อมูลที่มีค่าสูงสุดของอาร์เรย์ ค่าอื่นที่เป็นไปได้คือค่าใด?)
---

เมื่อเราพิจารณาข้อมูลสูงสุดของอาร์เรย์ $A$ มีความเป็นไปได้สองกรณีคือ
กรณีที่ข้อมูลสูงที่สุดอยู่ในอาร์เรย์ $A'$ ในอีกกรณีหนึ่งคือข้อมูลสูงที่สุดคือ $x_n$
ถ้าเป็นในกรณีแรกค่าสูงสุดคือ $M$ ในอีกกรณีหนึ่งคือ ข้อมูลตัวสุดท้าย $A_{n-1}$ ใน $A$
ซึ่งเราสามารถเทียบข้อมูลทั้งสองเพื่อหาค่าสูงที่สุดได้ ดังอัลกอริทึมด้านล่าง

---algt[*] การคำนวนค่าสูงสุดของอาร์เรย์ $A$ ที่มีสมาชิก $n$ ตัว
* IF $n=1$ THEN RETURN $A[0]$ and EXIT
* ELSE
** ให้ $M$ คือค่าสูงสุดของอาร์เรย์ $A'$ ที่มีสมาชิก $n-1$ ตัว เมื่อ $A' = [A_0,A_1,\ldots,A_{n-2}]$
** IF $A_{n-1} > M$ THEN 
*** RETURN $A_{n-1}$
** ELSE
*** RETURN $M$
---

คำถามก็คือ ในขั้นตอนที่ 3 เราจะคำนวณหาค่า $M$ ได้อย่างไร?
สังเกตว่าปัญหาดังกล่าวก็คือปัญหาเดียวกับปัญหาเริ่มต้นที่เราต้องการจะแก้
แต่มีข้อมูลป้อนเข้าที่แตกต่างออกไป ดังนั้น ในการแก้ปัญหาดังกล่าว
เราก็จะเรียกฟังก์ชันที่เราเตรียมไว้สำหรับแก้ปัญหานั้น นั่นก็คือฟังก์ชันที่เรากำลังเขียนอยู่นั่นเอง

จากแนวคิดดังกล่าว เราสามารถพัฒนาโปรแกรมที่คำนวณค่าสูงสุดได้ดังนี้

---src[cpp]
int arraymax(int ar[], int n)
{
  if(n==1)
    return ar[0];
  else {
    int m = arraymax(ar,n-1);   // Line 6
    if(m > xn)
      return m;
    else
      return ar[n-1];
  }
}
---

สังเกตว่าในโปรแกรมดังกล่าว เราไม่ได้สร้างอาร์เรย์ $A'$ ขึ้นมาใหม่แต่อย่างใด
เนื่องจากวิธีการเราสามารถพิจารณาให้ $A'$ เป็นแค่ส่วนต้นของอาร์เรย์ $A$
สิ่งที่เราทำเพื่อป้อนเป็นข้อมูลป้อนเข้าให้กับฟังก์ชัน {\ct arraymax}
คือปรับจำนวนของข้อมูลในอาร์เรย์เท่านั้นเอง

---q ผลบวกของอาร์เรย์
ออกแบบอัลกอริทึมที่รับอาร์เรย์ $A$ ของจำนวนเต็ม $n$ จำนวน
แล้วคำนวณผลรวมของข้อมูลในรายการ
---

---q เปลี่ยนทิศทาง
\label{quiz:rec-array-max-alt}
แทนที่เราจะนิยามให้ $A'$ เป็นอาร์เรย์ $A$ ที่ลบข้อมูลตัวสุดท้ายออกไป เราอาจจะนิยาม
\[
A'=[A_1,A_2,\ldots,A_{n-1}]
\]
นั่นคือ ให้เป็นอาร์เรย์ $A$ ที่ลบข้อมูลตัวแรกออก
จงพัฒนาอัลกอริทึมหาค่ามากที่สุดโดยใช้การเรียกตัวเองบนอาร์เรย์ $A'$ ที่นิยามใหม่นี้
และเขียนโปรแกรม

(คำแนะนำเพิ่มเติม: ในการส่งค่า $A'$ ในการเรียกตัวเองอาจจะดูซับซ้อนกว่าวิธีเก่าเล็กน้อย
แต่อย่าลืมว่าเราสามารถบวกพอยน์เตอร์ได้)
---



\subsection{ฟังก์ชันเรียกตัวเอง}
อัลกอริทึมดังกล่าวสามารถพิจารณาว่าเป็นการคำนวณค่าฟังก์ชัน $f$ ที่มีนิยามดังต่อไปนี้

$f([A_0,A_1,\ldots,A_{n-1}]) = 
\left\{
\begin{array}{ll}
A_0, &  \mbox{ถ้า } n=1 \\
\max \{ A_{n-1},f([A_0,A_1,\ldots,A_{n-2}]) \},  & \mbox{ในกรณีอื่น ๆ}
\end{array}
\right.$

\subsection{การทำซ้ำกับการเรียกตัวเอง}
การคำนวณค่าสูงสุดในรายการเป็นปัญหาพื้นฐานที่เหมาะกับอัลกอริทึมแบบทำซ้ำ
ด้านล่างแสดงส่วนของโปรแกรมดังกล่าว

---src[cpp]
int arraymax(int ar[], int n)
{
  int m = ar[0];
  for(int i=0; i<n; ++i)
    if(ar[i] > m)
      m = ar[i];
  return m;
}
---

ผู้อ่านที่สนใจอาจเริ่มสงสัยว่าการพัฒนาโปรแกรมแบบเรียกตัวเองมีประโยชน์อย่างไร?

TODO: อธิบายเพิ่มเติม

อย่างไรก็ตาม ภาษาโปรแกรมภายใต้กรอบคิดที่ไม่ใช่ภาษาเชิง imperative
อาจจะไม่มีโครงสร้างควบคุมที่เป็นการวนรอบ เช่น ภาษาเชิงฟังก์ชัน เช่น Haskell หรือ ML
หรือภาษาเชิงตรรก เช่น Prolog โปรแกรมที่เขียนบนภาษาในกลุ่มนี้
จะไม่มีแนวคิดเกี่ยวกับการเปลี่ยนแปลงค่าของตัวแปร
จึงทำให้โปรแกรมที่เขียนปราศจากผลข้างเคียง (side effect)
ทั้งหมดนี้ทำให้สามารถทดสอบโปรแกรมสะดวกขึ้น ลดข้อผิดพลาด
และทำให้โปรแกรมสามารถทำงานแบบขนานได้ง่ายขึ้นด้วย


\section{การจัดเรียงข้อมูล}
\label{sect:rec-sorting}

ในส่วนนี้เราจะพิจารณาตัวอย่างการออกแบบอัลกอริทึมโดยการคิดแบบเรียกตัวเอง
ปัญหาที่เราสนใจคือปัญหาการจัดเรียงข้อมูล ซึ่งเป็นปัญหาเกี่ยวกับการประมวลผลข้อมูลที่สำคัญมาก

เรามีจำนวนเต็ม $n$ จำนวน อยู่ในอาร์เรย์ $x$ (นั่นคือข้อมูลคือ
$[x_0,x_1,\ldots,x_{n-1}]$) เราต้องการเรียงข้อมูลในอาร์เรย์ดังกล่าวจากน้อยไปมาก

---q กรณีง่าย
มีกรณีใดบ้างที่เราสามารถเรียงข้อมูลในอาร์เรย์ $x$ ได้ง่ายมาก
---

กรณีที่อาร์เรย์มีข้อมูลเพียง 1 จำนวน การจัดเรียงอาร์เรย์ดังกล่าวสามารถทำได้โดยง่าย นั่นคือ
ไม่ต้องทำอะไรเลย  ถ้าไม่ใช่กรณีดังกล่าว เราจะเรียงข้อมูลได้อย่างไร?

แทนที่จะเริ่มแบบไม่มีอะไรเลย เราจะสมมติว่าในการพัฒนาโปรแกรมในการจัดการเรียงข้อมูล
$n$ ตัว เราสามารถเรียงข้อมูลในอาร์เรย์ที่มีข้อมูลจำนวน $m$ ตัวได้

สังเกตว่าเรากำลังแก้ปัญหาการจัดเรียงข้อมูล แต่เราสมมติว่าเราแก้ปัญหานั้นได้แล้ว!
ถ้าสมมติกันได้ง่าย ๆ แบบนี้โปรแกรมที่ใช้เรียงข้อมูลของเราคงมีลักษณะดังนี้

---algt เรียงข้อมูลในอาร์เรย์ $x$ ที่มีข้อมูล $n$ ตัว
* เรียงข้อมูลในอาร์เรย์ $x$ ที่มีข้อมูล $n$ ตัว
* คืนผลลัพธ์
---

---q อัลกอริทึมสมมติ
อัลกอริทึมดังกล่าวทำงานได้จริงหรือไม่? เพราะเหตุใด?
---

อัลกอริทึมข้างต้นนั้นทำงานไม่ได้จริง
เพราะว่าการทำงานของอัลกอริทึมจะเป็นการเรียกตัวเองไปเรื่อย ๆ ไม่มีวันสิ้นสุด

ดังนั้นการสมมติว่าเราสามารถเรียงข้อมูลในอาร์เรย์ได้นั้น จึงต้องมีขอบเขตที่ก่อให้เกิด
``ความก้าวหน้า'' ของการทำงาน
ในที่นี้เราจะใส่เงื่อนไขเพิ่มเติมว่าขนาดของอาร์เรย์ที่เราสามารถสมมติว่าเรียงได้นั้นมีค่าไม่เกิน
$n-1$ หรือให้ $m < n$

ดังนั้นเป้าหมายของเราจะเปลี่ยนจากการพยายามเรียงข้อมูล $n$ ตัว
ไปเป็นการพยายามทำงานบางอย่าง เพื่อทำให้งานที่เหลือกลายเป็นปัญหาการเรียงข้อมูล $m$
ตัว โดยที่ $m<n$

---q แนวทางการแก้ปัญหา
แนวทางที่เราระบุในย่อหน้าข้างต้นไม่ใช่แนวทางเดียวในการคิดแบบเรียกตัวเอง มีแนวทางอื่นอีกหรือไม่?

(คำใบ้: สลับ)
---

เราจะได้พิจารณาแนวทางอื่นในการคิดแบบเรียกตัวเองในตัวอย่างถัด ๆ ไป  

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

---q คำตอบบางส่วน
คำตอบบางส่วนของปัญหาการเรียงข้อมูลมีได้หลายแบบ ลองยกตัวอย่างสัก 2 แบบ
---

ในที่นี้เราจะพยายามทำให้ข้อมูลบางตัวในอาร์เรย์ อยู่ในตำแหน่ง ``ที่ถูกต้อง'' นั่นคือ
ตำแหน่งที่ข้อมูลนั้นจะอยู่เมื่ออาร์เรย์ดังกล่าวถูกเรียงแล้ว  

---q ตำแหน่งที่ถูกต้อง
สมมติเราพิจารณาข้อมูล $x_0$ จะหาตำแหน่งที่ถูกต้องของ $x_0$ ได้อย่างไร?
---

แทนที่เราจะเริ่มต้นด้วยข้อมูลบางตัว เช่น $x_0$ แล้วหาตำแหน่งที่ถูกต้อง
เราอาจจะมองกลับกัน คือเริ่มที่ตำแหน่งบางตำแหน่ง แล้วหาข้อมูลที่ควรจะอยู่ในตำแหน่งดังกล่าว

---q ข้อมูลถูกต้อง
\label{quiz:rec-sort-from}
(1) เราจะหาข้อมูลที่ควรจะมีดัชนีเท่ากับ $0$ ในอาร์เรย์ที่เรียงแล้วได้อย่างไร?  (2)
เราจะหาข้อมูลที่ควรจะมีดัชนีเท่ากับ $n-1$ ในอาร์เรย์ที่เรียงแล้วได้อย่างไร?
---

อัลกอริทึมในการเรียงอาร์เรย์ที่เราจะพัฒนาขึ้นนั้น ขึ้นกับว่าเราอยากจะตอบคำถาม (1) หรือ
(2) ในคำถามที่~\ref{quiz:rec-sort-from} ข้างต้นมากกว่ากัน
เพื่อความง่ายในการส่งค่าพารามิเตอร์ เราจะเลือกแนวทางจากคำถาม (2)
(ดูคำถามที่~\ref{quiz:rec-array-max-alt} ประกอบ)
แผนการของอัลกอริทึมเราจะเป็นดังด้านล่าง

---algt[algo:rec-sorting] เรียงข้อมูลในอาร์เรย์ $x$ ที่มีข้อมูล $n$ ตัว
* ย้ายข้อมูลที่มีค่ามากที่สุดไปยังตำแหน่ง $n-1$ โดยใช้การสลับกับข้อมูลอื่น ๆ
* เรียงข้อมูลในอาร์เรย์ $x'$ ที่มีข้อมูล $n-1$ ตัว โดยที่ $x'=[x_0,x_1,\ldots,x_{n-2}]$
---

เมื่อได้แผนการแล้ว การพัฒนาอัลกอริทึมที่สมบูรณ์และโปรแกรมก็ไม่ใช่เรื่องยากแต่อย่างใด
โปรแกรมที่~\ref{code:rec-selection-sort} แสดงอัลกอริทึมการจัดเรียงดังกล่าว
โดยละฟังก์ชัน {\ct find\_max\_index} ที่หาดัชนีของข้อมูลที่มากที่สุด และฟังก์ชัน {\ct
  swap} ไว้

อัลกอริทึมนี้ถ้าไม่เขียนโดยการเรียกตัวเอง นิยมเรียกว่าการจัดเรียงแบบเลือก (selection
sort)

---src[cpp,การจัดเรียงข้อมูลด้วยการจัดเรียงแบบเลือก,code:rec-selection-sort]
int find_max_index(int x[], int n) { // ... }

void sort(int x[], int n)
{
  if(n<=1)
    return;
  int maxi = find_max_index(x, n);
  swap(x[n-1], x[maxi]);
  sort(x, n-1);
}
---

\section{การค้นหาแบบทวิภาค: นิยามแบบเรียกตัวเอง}
\label{sect:rec-binary-search-revisited}

ในส่วนนี้เราจะพิจารณาอัลกอริทึมการค้นหาแบบทวิภาคในส่วนที่~\ref{sect:analysis-binary-search}
ซ้ำอีกครั้งหนึ่ง โดยเราจะเขียนฟังก์ชันการค้นหาใหม่ในรูปแบบของอัลกอริทึมแบบเรียกตัวเอง

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

ดังนั้นถ้าเราพิจารณาให้ดี ปัญหาที่เราต้องการจะแก้คือ:
\begin{quote}
ค้นหาข้อมูล $q$ จากอาร์เรย์ $A$ ขนาด $n$ ที่ข้อมูลเรียงลำดับจากน้อยไปมาก
โดยที่ดัชนีที่เป็นไปได้มีค่าระหว่าง $s$ ถึง $t$
\end{quote}
โดยในการค้นครั้งแรก เราจะให้ $s=0$ และ $t=n-1$ นั่นเอง

เราปรับอัลกอริทึม~\ref{algo:analysis-bin-search}
ใหม่ให้เป็นอัลกอริทึมแบบเรียกตัวเองได้ดังอัลกอริทึม~\ref{algo:rec-bin-search}
ในการเรียกใช้อัลกอริทึมดังกล่าว
เราจะเรียกผ่านอัลกอริทึม~\ref{algo:rec-bin-search-main}

\begin{figure}
---algt[*,algo:rec-bin-search] BinarySearch($q$, $A$, $s$, $t$)
* IF $s > t$ THEN RETURN $-1$ and EXIT
* $m\leftarrow \lfloor (s+t)/2\rfloor$
* IF $A[m] = q$ THEN
** RETURN $m$ and EXIT
* IF $A[m] < q$ THEN
** RETURN BinarySearch($q$, $A$, $m+1$, $t$)
* ELSE
** RETURN BinarySearch($q$, $A$, $t$, $m-1$)
---

---algt[*,algo:rec-bin-search-main] Find($q$, $A$, $n$)
* RETURN BinarySearch($q$, $A$, $0$, $n-1$)
---
\end{figure}

---q *
อิมพลีเมนท์อัลกอริทึม~\ref{algo:rec-bin-search} และทดสอบ
---

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

\section{การอุปนัยเชิงคณิตศาสตร์}

ในการพัฒนาโปรแกรมใด ๆ สิ่งที่เราต้องสนใจก่อนที่จะพิจารณาถึงประสิทธิภาพของโปรแกรม
ก็คือความถูกต้องของโปรแกรมนั้น ๆ \ \ อย่างไรก็ตาม
การพิสูจน์ความถูกต้องของโปรแกรมย่อยแบบเรียกตัวเองนั้นมีความซับซ้อนเป็นพิเศษ
ขั้นตอนการทำงานทั้งหมดมักไม่ได้ถูกระบุออกมาอย่างชัดเจนภายในโปรแกรมย่อยนั้น
แต่จะเป็นการโยนภาระการทำงานให้กับโปรแกรมย่อยนั้นเอง

ในส่วนนี้เราจะศึกษาเกี่ยวกับเทคนิคการพิสูจน์ที่เรียกว่า {\em การอุปนัยทางคณิตศาสตร์}
(mathematical induction)
ซึ่งเป็นเครื่องมือสำคัญในการพิสูจน์ความถูกต้องของโปรแกรมย่อยแบบเรียกตัวเอง

เราจะเริ่มจากตัวอย่าง พิจารณาผลรวม $1+2+3+\cdots+n$ ถ้ายังพอจำได้
ผลรวมดังกล่าวมีค่าเท่ากับ $\frac{n(n+1)}{2}$
อย่างไรก็ตามเราจะพิสูจน์ได้อย่างไรว่าผลรวมดังกล่าวมีค่าเท่ากับนิพจน์ที่อ้างมาจริง

เราอาจทดลองได้โดยการแทนค่า $ n $ ด้วยค่าต่าง ๆ เช่น

\begin{itemize}
\item เมื่อ $ n=1 $ เราจะได้ว่าผลรวมข้างต้นมีค่าเท่ากับ $ 1 $ ในขณะที่นิพจน์ $
  \frac{n(n+1)}{2}=\frac{1\cdot 2}{2}=1 $ เช่นกัน
\item เมื่อ $ n=2 $ เราจะได้ว่า ผลรวมมีค่า $ 1+2=3 $ ในขณะที่ $
  \frac{n(n+1)}{2}=\frac{2\cdot 3}{2}=3 $ เช่นกัน
\end{itemize}

เราสามารถไล่แทนค่าไปได้เรื่อย ๆ
... อย่างไรก็ตามวิธีดังกล่าวไม่สามารถพิสูจน์ได้ว่าผลรวมมีค่าเท่ากับนิพจน์ที่อ้างมาได้
เนื่องจากอาจมีค่าบางค่าที่เราไม่ได้แทนลงไปที่ผลรวมมีค่าไม่เท่ากับนิพจน์ดังกล่าว

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

การอุปนัยทางคณิตศาสตร์ นั้นมีลักษณะที่ดูผิวเผินแล้วมีลักษณะแตกต่างออกไป
เราจะเริ่มจากตัวอย่างการพิสูจน์ว่านิพจน์ดังกล่าวข้างต้นมีค่าเท่ากับผลรวมตามที่เราอ้างไว้

{\bf ขั้นที่ 1.} เราจะเริ่มโดยการตรวจสอบว่านิพจน์ดังกล่าวมีค่าเท่ากับผลรวมเมื่อ $ n=1 $ ซึ่งขั้นตอนนี้เราได้ทำไปแล้วตอนต้น

{\bf ขั้นที่ 2a.} จากนั้นเราสมมติว่านิพจน์ดังกล่าวมีค่าเท่ากับผลรวมเมื่อ $n=k$ สำหรับจำนวนนับ $k$ ใด ๆ ที่มีค่ามากกว่าหรือเท่ากับ $ 1 $ นั่นคือ
$$1+2+\cdots+k=\frac{k(k+1)}{2}$$ 	

{\bf ขั้นที่ 2b.} จากข้อสมมติดังกล่าว เราจะแสดงว่านิพจน์ดังกล่าวมีค่าเท่ากับผลรวมเมื่อ $ n=k+1 $ ด้วย
นั่นคือเราจะพิสูจน์ว่า: $$ 1+2+\cdots+k+(k+1)=\frac{(k+1)(k+2)}{2} $$

จากข้อสมมติที่ $ n=k $ เราสามารถพิสูจน์สมการเป้าหมายได้ไม่ยากนัก ดังนี้
\begin{eqnarray*}
1+2+\cdots+k+(k+1) &=& (1+2+\cdots+k)+(k+1)\\
&=& \frac{k(k+1)}{2}+(k+1) \ \ \ \mbox{(โดยการแทนค่าจากข้อสมมติ)}\\
&=& \frac{k(k+1)+2(k+1)}{2} \ \ \ \mbox{(จัดพจน์)}\\
&=& \frac{(k+1)(k+2)}{2} \ \ \ \mbox{(ดึงพจน์ย่อยร่วม)}
\end{eqnarray*}

ก่อนจะพิจารณาต่อไปเราจะทบทวน (อย่างไม่เป็นรูปแบบ) ว่าในขั้นตอนทั้ง 2 ขั้น เราได้แสดงอะไรไปบ้าง

\begin{itemize}
\item เราแสดงว่านิพจน์ดังกล่าวเท่ากับผลรวมจริงเมื่อ $ n=1 $
\item เราสมมติให้นิพจน์ดังกล่าวเท่ากับผลรวมเมื่อ $ n=k $ สำหรับ $ k\geq 1 $ ใด ๆ จากนั้นแสดงว่านิพจน์ดังกล่าวเท่ากับผลรวมเมื่อ $ n=k+1 $ ขั้นตอนนี้กล่าวในอีกทางหนึ่งก็คือการพิสูจน์ว่า:

ถ้า นิพจน์ดังกล่าวเท่ากับผลรวมเมื่อ $ n=k $ สำหรับ $ k\geq 1 $ ใด ๆ แล้ว นิพจน์ดังกล่าวเท่ากับผลรวมเมื่อ $ n=k+1 $ ด้วย
\end{itemize}

ความจริงทั้งสองข้อเมื่อนำมารวมกันกลับมีพลังในการพิสูจน์มากมาย กล่าวคือ
เมื่อเราทราบว่านิพจน์เท่ากับผลรวมเมื่อ $ n=1 $ (จากข้อ 1.)
เราสามารถนำความจริงที่พิสูจน์ในข้อ 2 มาใช้ได้ โดยพิจารณากรณีที่ $ k=1 $
ดังนั้นความจริงข้อ 2 ทำให้เราสรุปได้ว่า นิพจน์เท่ากับผลรวมเมื่อ $ n=k+1=2 $

ถ้าเราเอาความจริงข้อ 2 มาใช้อีกรอบ โดยครั้งนี้ให้ $ k=2 $
(สังเกตว่าเราสามารถความจริงข้อ 2 มาใช้ได้เนื่องจากเราทราบว่าผลรวมเท่ากับนิพจน์เมื่อ $
n=2 $ แล้ว) เราจะสามารถสรุปได้ว่า นิพจน์เท่ากับผลรวมเมื่อ $ n=k+1=3 $ ด้วย

เราสามารถนำความจริงข้อ 2 มาใช้ไปเรื่อย ๆ ทำให้เราสามารถอ้างไปได้เรื่อย ๆ
ว่านิพจน์นั้นเท่ากับผลรวมเมื่อ $ n=4,5,6,7,\ldots $
นั่นคือเราสามารถสรุปได้ว่านิพจน์ดังกล่าวมีค่าเท่ากับผลรวมสำหรับทุก ๆ จำนวนเต็ม $ n $ ที่
$ n\geq 1 $.

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

\framed\noindent
{\bf หลักการอุปนัยทางคณิตศาสตร์}\\
สำหรับเพรดิเคต $P(n)$ ที่ขึ้นกับจำนวนนับ $n$ ถ้าเราสามารถพิสูจน์ได้ว่า\\
1. $P(1)$ จริง และ\\
2. สำหรับจำนวนนับ $k\geq 1$ ใด ๆ $P(k)\Rightarrow P(k+1)$\\
แล้ว $P(n)$ เป็นจริงสำหรับทุก ๆ จำนวนนับ $n$
\endframed

เราเรียกขั้นที่ 1 ว่า{\em ขั้นฐาน} (basis) และเรียกส่วนที่สองว่า{\em ขั้นอุปนัย}
(inductive step) ในการพิสูจน์ขั้นอุปนัย เราเริ่มโดยการสมมติว่า $ P(i) $
เป็นจริงสำหรับจำนวนเต็ม $i$ ใด ๆ ข้อสมมติดังกล่าวเรียกว่า{\em สมมติฐานการอุปนัย}
(induction hypothesis) \ \ เนื่องจากในประโยค $P(n)$ เราใช้ $n$
เป็นตัวแปรของการอุปนัย เราจะกล่าวว่า การอุปนัยเชิงคณิตศาสตร์ดังกล่าว เป็น{\em
  การอุปนัยบนตัวแปร $n$}

สังเกตว่าในตัวอย่างที่ยังไม่สมบูรณ์ของเรานั้น เราได้พิสูจน์ขั้นที่ 1 และขั้นที่ 2 ไปแล้ว
โดยเพรดิเคตที่เราพิสูจน์ $ P(n) $ คือ

\begin{center}
``$ 1+2+\cdots+n = \frac{n(n+1)}{2} $''
\end{center}

ดังนั้นจากหลักการอุปนัยทางคณิตศาสตร์ เราสามารถสรุปได้ว่า $ P(n) $ จริงสำหรับทุก ๆ
จำนวนนับ $ n $

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

TODO: เพิ่มตัวอย่าง

\subsection{ความถูกต้องของโปรแกรม}

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

\begin{itemize}
\item {\bf เงื่อนไขก่อนหน้า (precondition)}
  จะระบุเงื่อนไขของข้อมูลป้อนเข้าของอัลกอริทึม ยกตัวอย่างเช่น
  ในอัลกอริทึมสำหรับการค้นหาแบบทวิภาคในส่วนที่~\ref{sect:rec-binary-search-revisited}
  เงื่อนไขก่อนหน้าคือข้อมูลในอาร์เรย์จะต้องเรียงลำดับจากน้อยไปหามาก
  ส่วนในกรณีของอัลกอริทึมการเรียงลำดับที่เราพิจารณาในส่วนที่~\ref{sect:rec-sorting}
  นั้นไม่ได้มีการกำหนดเงื่อนไขเริ่มต้นพิเศษแต่อย่างใด แค่เงื่อนไขความถูกต้องของข้อมูล เช่น
  อาร์เรย์มีข้อมูล $n$ ตัว เป็นต้น
\item {\bf เงื่อนไขตามหลัง (postcondition)}
  จะเป็นเงื่อนไขที่เราต้องการได้รับจากอัลกอริทึม
  ยกตัวอย่างเช่นในกรณีของอัลกอริทึมค้นหาแบบทวิภาคเราต้องการเงื่อนไขว่า
  ถ้าข้อมูลที่ต้องการค้นอยู่ในอาร์เรย์ อัลกอริทึมจะคืนดัชนีของข้อมูลนั้น
  และถ้าข้อมูลไม่อยู่ในอาร์เรย์อัลกอริทึมจะต้องคืนค่า $-1$
  \ ส่วนกรณีของอัลกอริทึมจัดเรียงข้อมูล
  เราต้องการเงื่อนไขว่าอาร์เรย์ผลลัพธ์มีข้อมูลของอาร์เรย์เดิมทั้งหมด
  และข้อมูลในอาร์เรย์นั้นเรียงตามลำดับจากน้อยไปมาก
\end{itemize}

การแสดงความอัลกอริทึมทำงานถูกต้องก็คือการพิสูจน์ว่า
ถ้าข้อมูลป้อนเข้าสอดคล้องกับเงื่อนไขก่อนหน้า หลังจากที่อัลกอริทึมทำงานเสร็จแล้ว
ผลลัพธ์และข้อมูลต่าง ๆ สอดคล้องกับเงื่อนไขตามหลัง

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

หนังสือเล่มนี้จะไม่ลงรายละเอียดในการพิสูจน์ความถูกต้องอย่างเต็มรูปแบบ
แต่จะใช้แนวคิดหลัก~ๆ นี้ในการแสดงว่าอัลกอริทึมทำงานถูกต้อง \ \ นอกจากนี้
ในการพัฒนาโปรแกรมในชีวิตจริง แม้ว่าเราจะไม่ได้พิสูจน์ความถูกต้องของโปรแกรมตลอดเวลา
แต่การใส่ใจกับเงื่อนไขก่อนหน้าและเงื่อนไขตามหลังอย่างสม่ำเสมอ
จะช่วยลดความผิดพลาดในโปรแกรม หรือช่วยทำให้เราพบข้อผิดพลาดได้รวดเร็วขึ้น

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

\subsubsection{อัลกอริทึมเรียงข้อมูลแบบการเลือก}

แม้ว่าอัลกอริทึม~\ref{algo:rec-sorting} จะทำงานบนอาร์เรย์ป้อนเข้าโดยตรง
เพื่อความสะดวกในการพิสูจน์ เราจะแยกอาร์เรย์ป้อนเข้าและอาร์เรยผลลัพธ์ออกจากกัน
โดยเราจะเรียกอาร์เรย์ป้อนเข้าว่าอาร์เรย์ $A$ และ อาร์เรย์ผลลัพธ์ว่าอาร์เรย์ $B$

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

เงื่อนไขความถูกต้องของการจัดเรียงมีดังนี้
\begin{itemize}
\item เงื่อนไขก่อนหน้า: ไม่มี
\item เงื่อนไขตามหลัง: อาร์เรย์ $B$ เป็นการเรียงสับเปลี่ยน (permutation) ของอาร์เรย์ $A$ และสำหรับทุก ๆ ดัชนี $i$ ที่ $0\leq i<n-1$ เราจะได้ว่า $B[i]\leq B[i+1]$
\end{itemize}

สังเกตว่าเงื่อนไขตามหลังประกอบด้วยเงื่อนไขย่อยสองเงื่อนไข คือ ($P1$) อาร์เรย์ $B$
เป็นการเรียงสับเปลี่ยน (permutation) ของอาร์เรย์ $A$
เพื่อรับประกันว่าข้อมูลป้อนเข้าจะอยู่ครบ และ ($P2$) สำหรับทุก ๆ ดัชนี $i$ ที่ $0\leq
i<n-1$ เราจะได้ว่า $B[i]\leq B[i+1]$ เพื่อรับประกันการเรียงลำดับของข้อมูล

ดังนั้นในการพิสูจน์ เราไม่จำเป็นที่จะต้องพิสูจน์เงื่อนไขทั้งสองนี้ไปพร้อมกันก็ได้ \ จากโปรแกรม
สังเกตว่าสิ่งเดียวที่โปรแกรมเปลี่ยนแปลงอาร์เรย์ $A$ เพื่อให้ได้อาร์เรย์ $B$
คือการสลับค่าข้อมูลในอาร์เรย์ด้วยฟังก์ชัน {\ct swap}
เพราะฉะนั้นเราสามารถสรุปได้ว่าอาร์เรย์ $B$ เป็นการเรียงสับเปลี่ยนของอาร์เรย์ $A$
\ นั่นคือเงื่อนไข ($P1$) เป็นจริง

เมื่อเราทราบว่าเงื่อนไข ($P1$) จริงแล้ว เราจะแสดงเงื่อนไข ($P2$)
ด้วยการอุปนัยเชิงคณิตศาสตร์ \ (ในการพิสูจน์เราจำเป็นจะต้องใช้ความจริงว่า ($P1$)
เป็นจริงด้วย)

---q โครงสร้างของการอุปนัยเชิงคณิตศาสตร์กับการเรียกตัวเอง
ลองพิจารณาโครงสร้างของการพิสูจน์โดยใช้การอุปนัยเชิงคณิตศาสตร์
เทียบกับอัลกอริทึมแบบเรียกตัวเอง ว่ามีโครงสร้างในรูปแบบเดียวกันอย่างไรบ้าง?
---

การพิสูจน์โดยใช้การอุปนัยเชิงคณิตศาสตร์ใช้จำนวนนับ $n$
ในการแบ่งประโยคที่ต้องการพิสูจน์เป็นส่วนย่อย ๆ \ เราจะใช้ $n$
แทนจำนวนข้อมูลในอาร์เรย์ที่เราต้องการจะเรียง \ \ เราจะให้ประโยค $P(n)$ คือ
\begin{quote}
$P(n)$: อัลกอริทึม~\ref{algo:rec-sorting} เมื่อรับอาร์เรย์ขนาด $n$ ให้ผลลัพธ์เป็นอาร์เรย์
  $B$ ที่สำหรับทุก ๆ ดัชนี $i$ ที่ $0\leq i<n-1$ เราจะได้ว่า $B[i]\leq B[i+1]$
\end{quote}

{\bf ขั้นฐาน:} เราจะเริ่มพิสูจน์ในกรณีฐาน นั่นคือ เมื่อ $n=1$: สังเกตว่าในกรณีดังกล่าว
ดัชนี $i$ ที่สอดคล้องกับเงื่อนไข $0\leq i < n-1=0$ นั้นไม่มี ดังนั้นประโยค $P(1)$
จึงเป็นจริง\footnote{ในกรณีนี้ เรานิยมกล่าวว่า $P(1)$
  เป็นจริงเนื่องจากสิ่งที่ต้องพิจารณานั้นว่างเปล่า (vacuously true)
  เพราะว่าเซตของสิ่งที่เราต้องพิสูจน์เงื่อนไขนั้น ไม่มีสมาชิกอยู่เลย}

{\bf ขั้นอุปนัย:} เราจะสมมติให้ $P(n)$ เป็นจริงสำหรับกรณีที่ $n=k$ สำหรับจำนวนนับ
$k$ ใด~ๆ เราจะพิสูจน์ว่า $P(n)$ เป็นจริงสำหรับกรณีที่ $n=k+1$

สำหรับขั้นตอนนี้ ถ้าเราเขียนอย่างรวบรัดเรามักเขียนว่า สำหรับ $k$ ใด~ๆ เราสมมติให้
$P(k)$ เป็นจริง และจะพิสูจน์ว่า $P(k+1)$ เป็นจริง 

พิจารณาการทำงานของอัลกอริทึมเมื่ออาร์เรย์มีขนาด $k+1$

สังเกตว่าอัลกอริทึมทำงานโดยการย้ายข้อมูลที่มีค่ามากที่สุดไปไว้ในอาร์เรย์ตำแหน่งที่ $k$
นั่นคือเราทราบว่า $B[i]\leq B[k]$ สำหรับทุก ๆ ดัชนี $i$ ที่ $0\leq i<k$

จากนั้นอัลกอริทึมเรียกตัวเองเพื่อทำงานกับตอนต้นของอาร์เรย์ ที่มีขนาด $k$ จากข้อสมมติว่า
$P(k)$ เป็นจริง เราจะได้ว่าเมื่ออัลกอริทึมทำงานเสร็จ เราจะได้ว่าอาร์เรย์ $B$
มีคุณสมบัติว่า สำหรับทุก ๆ ดัชนี $i$ ที่ $0\leq i<k-1$ เราจะได้ว่า $B[i]\leq
B[i+1]$ (สังเกตขอบเขตของดัชนี $i$ ว่ามีค่าถึงแค่ $k-2$ เท่านั้น)

เนื่องจากการทำงานในขั้นของการเรียกตัวเอง ไม่มีการเปลี่ยนแปลงค่าของ $B[k]$ นอกจากนี้
เนื่องจาก ($P1$) เป็นจริง อาร์เรย์ผลลัพธ์จากการเรียกตัวเองในส่วน $B[0]\ldots
B[k-1]$ จะเป็นการเรียงสับเปลี่ยนของอาร์เรย์เดิม \ นั่นคือ หลังการเรียกตัวเอง
$B[k-1]$ จะมีค่าเท่ากับบาง $B[i]$ ก่อนการเรียกตัวเอง

อย่างไรก็ตาม เนื่องจากก่อนการเรียกตัวเอง เราทราบว่า $B[k]$ มีค่ามากกว่าหรือเท่ากับทุก
ๆ $B[i]$ ดังนั้นเราสามารถสรุปได้ว่า หลังการเรียกตัวเอง $B[k]\geq B[k-1]$

ดังนั้น เราจึงได้ว่า สำหรับทุก ๆ ดัชนี $i$ ที่ $0\leq i<k$ เราจะได้ว่า $B[i]\leq
B[i+1]$, ซึ่งหมายความว่า $P(k+1)$ เป็นจริงนั่นเอง

เนื่องจากเราได้พิสูจน์ทั้งขั้นฐานและขั้นอุปนัยแล้ว โดยการอุปนัยเชิงคณิตศาสตร์
เราสามารถสรุปได้ว่า $P(n)$ เป็นจริง สำหรับทุก ๆ จำนวนนับ $n$ \ นั่นคือ
อัลกอริทึมจัดเรียง~\ref{algo:rec-sorting} เมื่อทำงานเสร็จแล้วผ่านเงื่อนไขตามหลัง
($P2$)

เนื่องจากเราสามารถแสดงได้ว่าอัลกอริทึมผ่านทั้งเงื่อนไข ($P1$) และ ($P2$)
เราจึงสรุปว่าอัลกอริทึมทำงานได้ถูกต้อง

ในขั้นอุปนัยนี้ เมื่อเราชำนาญขึ้น เรามักเขียนรวบรัดขึ้นอีกโดยไม่แยกระหว่าง $n$ กับ $k$
กล่าวคือเราจะเขียนว่า สำหรับ $n$ ใด ๆ เราสมมติให้ $P(n)$ เป็นจริง และจะพิสูจน์ว่า
$P(n+1)$ เป็นจริง ทั้งนี้สังเกตว่า $n$ ในประโยคข้างต้นกับ $n$ ภายในนิยามของประโยค
$P(n)$ เป็นตัวแปรคนละตัวกัน โดยเราสามารถพิจารณาได้ว่า $n$ ภายในนิยามของประโยค
$P(n)$ เป็นตัวแปรท้องถิ่น (local variable) ของประโยค $P$ นั่นเอง

\subsubsection{อัลกอริทึมการค้นหาแบบทวิภาค}

เช่นเดียวกับการวิเคราะห์อัลกอริทึมการจัดเรียง
เราจะวิเคราะห์ความถูกต้องของการค้นหาแบบทวิภาค
(อัลกอริทึม~\ref{algo:rec-bin-search} และ~\ref{algo:rec-bin-search-main})
โดยเริ่มจากการระบุเงื่อนไขก่อนหน้าและเงื่อนไขตามหลัง

---q *
ระบุเงื่อนไขก่อนหน้าและเงื่อนไขตามหลัง (อย่างเป็นทางการมากขึ้น)
ที่เราต้องการเพื่อพิสูจน์ความถูกต้องของอัลกอริทึม
---

เราต้องการค้นหาข้อมูล $q$ จากอาร์เรย์ $A$ ที่มีข้อมูล $n$ ตัวเรียงลำดับจากน้อยไปหามาก
เงื่อนไขความถูกต้องของอัลกอริทึมการค้นหา Find (\ref{algo:rec-bin-search-main})
มีดังนี้
\begin{itemize}
\item เงื่อนไขก่อนหน้า: อาร์เรย์ $A$ ต้องเรียงลำดับจากน้อยไปหามาก
\item เงื่อนไขตามหลัง: ถ้ามีข้อมูล $q$ ในอาร์เรย์ $A$
  จะต้องคืนผลลัพธ์เป็นดัชนีของข้อมูลนั้น ถ้าไม่มีจะต้องคืนค่า -1
\end{itemize}

อย่างไรก็ตาม ในกรณีนี้เรามีอัลกอริทึมสองอัลกอริทึมที่ต้องพิจารณา คือ อัลกอริทึม Find
(\ref{algo:rec-bin-search-main}) และอัลกอริทึม BinarySearch
(\ref{algo:rec-bin-search}) \ หน้าที่หลักของอัลกอริทึม Find
คือการกำหนดค่าเริ่มต้นให้กับพารามิเตอร์ $s$ และ $t$ \ ส่วนการทำงานหลักจะอยู่ที่ฟังก์ชัน
BinarySearch

ดังนั้นการที่เราจะแสดงว่าอัลกอริทึม Find ทำงานได้ถูกต้องได้นั้น
เราจำเป็นจะต้องแสดงว่าอัลกอริทึม BinarySearch ทำงานถูกต้องด้วย
\ เราจะวิเคราะห์หาเงื่อนไขก่อนหน้าที่เราจะรับประกันให้อัลกอริทึม
และเงื่อนไขตามหลังที่เราต้องการจากอัลกอริทึมดังกล่าว

สังเกตว่า ถ้าพารามิเตอร์ $s$ และ $t$ มีค่าไม่ถูกต้อง อัลกอริทึม BinarySearch
ก็จะไม่สามารถคืนดัชนีของข้อมูลที่เราต้องการออกมาได้
\ ข้อสังเกตนี้ทำให้เราคาดเดาได้ว่าเงื่อนไขก่อนหน้าจะต้องเกี่ยวข้องกับ $s$ และ $t$ ด้วย

---q *
ทดลองระบุเงื่อนไขก่อนหน้า และเงื่อนไขตามหลังที่เราต้องการ จากอัลกอริทึม BinarySearch
(\ref{algo:rec-bin-search})
---

เราสามารถระบุเงื่อนไขสำหรับความถูกต้องของอัลกอริทึม BinarySearch ได้ดังนี้
\begin{itemize}
\item เงื่อนไขก่อนหน้า: อาร์เรย์ $A$ ต้องเรียงลำดับจากน้อยไปหามาก และถ้า $q$ อยู่ในอาร์เรย์ $A$ จะมีดัชนี $i$ ที่ $s\leq i\leq t$ และ $A[i]=q$
\item เงื่อนไขตามหลัง: ถ้ามีข้อมูล $q$ ในอาร์เรย์ $A$
  อัลกอริทึมจะต้องคืนผลลัพธ์เป็นดัชนีของข้อมูลนั้น ถ้าไม่มีจะต้องคืนค่า -1
\end{itemize}

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

อย่างไรก็ตาม สำหรับอัลกอริทึมนี้เราจะใช้การอุปนัยเชิงคณิตศาสตร์แบบเข้ม (strong
induction)
ซึ่งมีรูปแบบแตกต่างจากการอุปนัยเชิงคณิตศาสตร์ที่เราได้กล่าวถึงในตอนต้นเล็กน้อย

\framed\noindent
{\bf หลักการอุปนัยทางคณิตศาสตร์แบบเข้ม}\\
สำหรับเพรดิเคต $P(n)$ ที่ขึ้นกับจำนวนนับ $n$ ถ้าเราสามารถพิสูจน์ได้ว่า\\
1. $P(1)$ จริง และ\\
2. สำหรับจำนวนนับ $k\geq 1$ ใด ๆ $P(1)\wedge P(2)\cdots\wedge P(k)\Rightarrow P(k+1)$\\
แล้ว $P(n)$ เป็นจริงสำหรับทุก ๆ จำนวนนับ $n$
\endframed

สังเกตว่าในขั้นอุปนัย เรามีเงื่อนไขที่มากขึ้น แทนที่จะมีแค่ $P(k)$ แต่เราสามารถอ้างได้ตั้งแต่
$P(1), P(2)$ จนถึง $P(k)$ \ \ อย่างไรก็ตาม
การใช้การอุปนัยแบบเข้มมีประโยชน์แค่ความสะดวกในการพิสูจน์เท่านั้น
เนื่องจากการอุปนัยแบบที่เราแนะนำในตอนต้น (หรือที่นิยมเรียกว่าการอุปนัยแบบอ่อน หรือ week
induction) กับการอุปนัยแบบเข้มนั้นสมมูลกัน

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

---q *
ลองพิจารณาการพิสูจน์ความถูกต้องของอัลกอริทึมเรียงข้อมูล
นิยามของความก้าวหน้าของอัลกอริทึมคืออะไร?
จากนั้นให้พิจารณาบทพิสูจน์และอธิบายว่าที่จุดใดที่เราอ้างถึงและใช้ความก้าวหน้าดังกล่าวในการพิสูจน์
---

---q ความก้าวหน้าของการค้นหาแบบทวิภาค
นิยามของความก้าวหน้าของอัลกอริทึมการค้นหาแบบทวิภาคคืออะไร?
(เราเคยพิจารณาเรื่องนี้ไปในส่วน~\ref{sect:analysis-binary-search})
---

เนื่องจากเราใช้จำนวนข้อมูลที่เหลือในการแสดงความก้าวหน้าของอัลกอริทึม
เราจะทำการอุปนัยบนจำนวนนั้น กล่าวคือเราจะพิสูจน์ว่าประโยค
\begin{quote}
$Q(k)$: ``อัลกอริทึม BinarySearch เมื่อเรียกใช้งานโดยที่มีจำนวนข้อมูลที่เป็นไปได้ $t-s+1 = k$ จำนวนและเงื่อนไขก่อนหน้าเป็นจริง จะให้ผลลัพธ์ที่สอดคล้องกับเงื่อนไขตามหลัง''
\end{quote}
เป็นจริงสำหรับทุก ๆ จำนวนเต็ม $k$ ที่ $k\geq 0$

สังเกตว่าเราจะเริ่มการอุปนัยที่ $k=0$
ซึ่งไม่ตรงกับนิยามของหลักการอุปนัยเชิงคณิตศาสตร์เสียทีเดียว
อย่างไรก็ตามเราจะดำเนินการพิสูจน์ในลักษณะนี้ไปก่อนและพิจารณาประเด็นนี้ในภายหลัง

{\bf ขั้นฐาน:} เมื่อ $k=0$ และเงื่อนไขก่อนหน้าเป็นจริง เราสามารถสรุปได้ว่าข้อมูล $q$
ไม่อยู่ในอาร์เรย์ (ดูคำถาม~\ref{quiz:rec-bin-basis}) นอกจากนี้เราทราบว่า
$t-s+1=0$ หรือ $s=t+1$ ทำให้เข้าเงื่อนไขของคำสั่ง IF ในบรรทัดที่ 1 และอัลกอริทึม
BinarySearch จะคืนค่า $-1$ ซึ่งสอดคล้องกับเงื่อนไขตามหลัง

---q *
\label{quiz:rec-bin-basis}
พิสูจน์ว่า ถ้า $k=0$ และเงื่อนไขก่อนหน้าเป็นจริง ข้อมูล $q$ จะไม่อยู่ในอาร์เรย์
---

{\bf ขั้นอุปนัย:} พิจารณากรณีที่ $k>0$ เราจะสมมติว่าสำหรับทุก ๆ $k'<k$ ประโยค
$Q(k')$ เป็นจริง นั่นคือ ถ้ามีการเรียกอัลกอริทึม BinarySearch
ที่จำนวนข้อมูลที่เป็นไปได้คือ $k'$ และเงื่อนไขก่อนหน้าเป็นจริง
ผลลัพธ์ที่ได้จะสอดคล้องกับเงื่อนไขตามหลัง

เรามีกรณีที่ต้องพิจารณา 3 กรณี แยกตามการทำงานของอัลกอริทึม BinarySearch

{\em กรณีที่ 1:} เมื่อ $A[m]=q$. ในกรณีนี้อัลกอริทึมจะตอบ $m$
ซึ่งทำให้ผลลัพธ์สอดคล้องกับเงื่อนไขตามหลัง

{\em กรณีที่ 2:} เมื่อ $A[m]<q$. เนื่องจากข้อมูลในอาร์เรย์เรียงลำดับกัน
(จากเงื่อนไขก่อนหน้า) เราจะทราบว่าสำหรับทุก~ๆ ดัชนี $i$ ที่ $0\leq i\leq m$,
$A[i]<q$ \ \ เมื่อเรานำความจริงนี้มาประกอบกับเงื่อนไขก่อนหน้า นั่นคือ ถ้ามีข้อมูล $q$
ใน $A$ จะมีดัชนี $i$ ที่ $s\leq i\leq t$ ที่ $A[i]=q$ เราจะสามารถสรุปได้ว่า
ถ้ามีข้อมูล $q$ ใน $A$ จะต้องมีดัชนี $i$ ที่ $m+1\leq i\leq t$ ที่ $A[i]=q$

จากนั้นอัลกอริทึมจะเรียกตัวเองเพื่อค้นหาแบบทวิภาคในอาร์เรย์โดยส่งค่าดัชนีเริ่มต้นเป็น $m+1$
และดัชนีสุดท้ายเป็น $t$ \ \ สังเกตว่าในกรณีนี้
ข้อสรุปข้างต้นแสดงว่าเงื่อนไขเริ่มต้นของอัลกอริทึม BinarySearch ที่เรียกตัวเองเป็นจริง
นอกจากนี้จำนวนที่เป็นไปได้ในการเรียกตัวเองคือ $k' = t -
\lfloor\frac{s+t}{2}\rfloor - 1 < t - s + 1<k$ ดังนั้น
โดยสมมติฐานการอุปนัยเราจะได้ว่า ผลลัพธ์ที่คืนจากการเรียกตัวเองถูกต้อง นั่นคือ ถ้า $q$
อยู่ในอาร์เรย์ $A$ โดยมีดัชนีตั้งแต่ $m+1$ จนถึง $t$ อัลกอริทึมจะคืนค่าดัชนี $i$ ที่
$A[i]=q$ และถ้า $q$ ไม่อยู่ในอาร์เรย์ในดัชนีตั้งแต่ $m+1$ ถึง $t$ อัลกอริทึมจะคืนค่า -1

ดังนั้น จากเงื่อนไขตามหลังที่ได้หลังการเรียกตัวเองและเงื่อนไขก่อนหน้าที่เรารับประกัน
เราสามารถสรุปได้ว่าผลลัพธ์ของ BinarySearch เมื่อจำนวนข้อมูลที่เป็นไปได้คือ $k$
สอดคล้องกับเงื่อนไขตามหลังในกรณีที่ 2 นี้

{\em กรณีที่ 3:} เมื่อ $A[m]>q$. สำหรับกรณีนี้
เราจะละไว้เป็นคำถามที่~\ref{quiz:rec-bin-induction-case3}

เมื่อเราได้พิจารณาทุกกรณีแล้ว เราสามารถสรุปได้ว่า ถ้าเราสมมติให้
$Q(0),Q(1),\ldots,Q(k-1)$ เป็นจริง แล้ว $Q(k)$ จะเป็นจริงด้วย
\ \ นั่นคือเราแสดงขั้นอุปนัยได้แล้ว

ดังนั้น จากหลักการอุปนัยเชิงคณิตศาสตร์แบบเข้ม เราสามารถสรุปได้ว่า $Q(k)$
เป็นจริงสำหรับทุก ๆ ค่า $k$ ที่ $k\geq 0$

---q กรณีที่ 3
\label{quiz:rec-bin-induction-case3} พิสูจน์ขั้นอุปนัยในกรณีที่ 3
---

{\bf หมายเหตุ.}  สังเกตว่าเราปรับรูปแบบการพิสูจน์แบบอุปนัยเชิงคณิตศาสตร์เล็กน้อย นั่นคือ
เราไม่ได้เริ่มค่าพารามิเตอร์ที่ 1 และแทนที่เราจะสมมติ $Q(0)\wedge
Q(1)\wedge\cdots\wedge Q(k)$ แล้วพิสูจน์ $Q(k+1)$ เรากลับสมมติ $Q(0)\wedge
Q(1)\wedge\cdots\wedge Q(k-1)$ และพยายามพิสูจน์ $Q(k)$
\ \ ทั้งหมดนี้เป็นแค่การปรับรูปแบบ
แต่ไม่ได้ทำข้อสรุปของการอุปนัยเชิงคณิตศาสตร์เปลี่ยนไปแต่อย่างใด
เพราะเราสามารถนิยามประโยค $Q'(i)$ ให้เป็นประโยค $Q(i-1)$ และพิสูจน์ประโยค
$Q'(i)$ สำหรับ $i=1,2,\ldots$ ได้ด้วยการอุปนัยเชิงคณิตศาสตร์ในรูปแบบมาตรฐาน
จากนั้นข้อสรุปว่า $Q'(i)$ เป็นจริงสำหรับ $i=1,2,\ldots$ ก็จะสมมูลกับข้อสรุปว่า
$Q(k)$ เป็นจริงเมื่อ $k=0,1,2,\ldots$ นั่นเอง