ดูต้นฉบับสำหรับ Ioi/recursion

หน้านี้รวมแบบฝึกหัดการเขียน recursion ด้วย Racket

* [http://theory.cpe.ku.ac.th/wiki/images/01204435-lect02-scheme.pdf เอกสาร lisp/scheme/racket]

== เริ่มต้น ==
1. myprod  (หาผลคูณ, คืน 1 ถ้าเป็นรายการว่าง)

 > (myprod '())
 1
 > (myprod '(1 2 3 4 5))
 120

2. unitlist

เขียนฟังก์ชัน unitlist รับรายการ lst ทีคืนค่า #t ถ้า lst เป็นรายการความยาว 1  (ไม่ต้องสนใจกรณีที่เป็นรายการว่าง)

 > (unitlist '(1))
 #t
 > (unitlist '(1 2 3))
 #f

3. mymin

 > (mymin '(1 2 3 -1 100))
 -1

== ฝึกฝน ==

1. mypushback

เขียนฟังก์ชัน mypushback รับ list และ element แล้ว return list ที่มี element ต่อท้าย

 > (mypushback '(1 2 3 4) 10)
 '(1 2 3 4 10)

ฟังก์ชันที่เขียนทำงานในเวลาเท่าใด ถ้าลิสต์ที่ได้รับมีความยาว n

2. mylast

เขียนฟังก์ชัน mylast รับ list และคืนข้อมูลสุดท้ายใน list ไม่ต้องพิจารณากรณีที่ได้รับ list ว่าง

 > (mylast '(10 20 30))
 30

3. myappend

เขียนฟังก์ชันรับ list สอง list และคืน list ที่เกิดจากการต่อกันของทั้งสอง list

 > (myappend '(1 2 3) '(20 30 40))
 '(1 2 3 20 30 40)

== ท้าทาย ==
1. myrev

เขียนฟังก์ชัน myrev ที่รับรายการแล้วคืนรายการที่กลับหน้าหลัง

 > (myrev '(1 3 4 5 6 7 8))
 '(8 7 6 5 4 3 1)

สามารถเขียนฟังก์ชันอื่นประกอบได้  เวลาในการทำงานของฟังก์ชันที่เขียนเป็นเท่าใด ถ้ารายการมีความยาว n

2. myflat

เขียนฟังก์ชัน myflat ที่รับรายการ จากนั้นแปลงรายการเป็นแบบรายการชั้นเดียว  สามารถใช้ฟังก์ชัน list? เพื่อตรวจสอบว่าข้อมูลเป็นรายการหรือไม่ได้

 > (myflat '(1 2 (1 2 3 (4 5) 6) (((7) 8) 9) 10 (11)))
 '(1 2 1 2 3 4 5 6 7 8 9 10 11)

== merge sort ==

=== merge-list ===
เขียนฟังก์ชัน merge-list รับลิสต์สองลิสต์ที่เรียงจากน้อยไปหามาก แล้วคืนค่าลิสต์ที่เป็นลิสต์รวมของลิสต์ทั้งสองที่เรียงลำดับจากน้อยไปหามากแล้ว

 > (merge-list '(1 2 3 5 7 11 13) '(2 4 6 8 10 12))
 '(1 2 2 3 4 5 6 7 8 10 11 12 13)

=== split-list ===
ให้เขียนฟังก์ชัน split-list ที่รับลิสต์ของจำนวนเต็ม  แล้วคืนค่าเป็นลิสต์ที่มีสมาชิกสองตัว ตัวแรกเป็นลิสต์ที่ประกอบด้วยสมาชิกในลิสต์ที่มีตำแหน่งเป็นเลขคี่ ตัวที่สองลิสต์ของสมาชิกที่มีตำแหน่งเป็นเลขคู่

ตัวอย่างการทำงาน

 > (split-list '(1 3 2 4 5 7 4 3 6 9 10))
 '((1 2 5 4 6 10) (3 4 7 3 9))
 > (split-list '(1))
 '((1) ())
 > (split-list '())
 '(() ())

hint: อาจจะใช้ฟังก์ชัน cond ในการแยกกรณี, สามารถใช้ฟังก์ชัน first  และ second เพื่ออ่านข้อมูลตัวแรก และตัวที่สองของลิสต์ได้,  ให้ทดลองใช้ฟังก์ชัน let

=== merge-sort ===

เขียนฟังก์ชัน merge-sort ที่เรียงลำดับข้อมูลในลิสต์  ให้ใช้ฟังก์ชัน merge-list และ split-list

ตัวอย่างการทำงาน

 > (merge-sort '(1 9 8 2 3 7 4 6 10 39 28 17 50 60 70))
 '(1 2 3 4 6 7 8 9 10 17 28 39 50 60 70)

hint: อย่าลืม base cases (กรณีที่เป็นลิสต์ว่าง และกรณีที่ลิสต์มีสมาชิก 1 ตัว)

== ต้นไม้ ==