• ที่ต้องสอนเรื่องนี้เพราะว่าเดี๋ยวได้ไปใช้เขียนในการทำ Sorting ใช้ในพวก Merge Sort เป็นต้น

A Function and Calling A Function

• A function is a sequence of commands that can be reused together later in a program.
• A function can call another function.
• To call a function, you just call its name with required input.

Repetition

• In programming, repetition is an ability for a program to repeat instructions, in which they are repeated base on some condition.

Two Ways To Do Repetitions

Iteration

• Use a loop (for, while) to control the repetition

Recursion

• Solve part of the problem and make the program calls itself to solve the same problem but smaller

Recursive Program

• A recursion is the concept of defining a repetition of procedures by making a call to itself
• Basic case: tell when the calling-itself process should be stopped (IMPORTANT)
• General case: tell when the calling-itself process should continue and what needs to pass to the next call
• อาจจะออกข้อสอบให้ Trace Program แล้วถามว่าเป็น Tail หรือว่า Non-Tail

Types of Recursion

• ถ้าคำตอบท้าย คือคำตอบทั้งหมดของระบบ เรียกว่า “Tail”
• ถ้าคำตอบท้าย ยังต้องมาบวกกับอะไร เพื่อเพิ่มพูนค่าไปเรื่อย ๆ แบบนี้เรียก “Non-tail”

Tail recursion

• Tail recursion is defined as a recursive function in which the recursive call is the last statement that is executed by the function. So basically nothing is left to execute after recursion call
• It performance of tail-recursion can be optimized so that it can run as quick as the iterative method 👑

Non-tail recursion

• The result cannot be immediately returned, so it needs to save partially solved solutions on to a memory stack
• สังเกตว่ายังเอามาบวกอะไรอีกมั้ย ไม่ใช่แค่อันท้าย execute ละคือคำตอบของ function นั้นเลย
• The performance can be very worse when the input size increases

Advantage

• A recursive program makes it easier to visualize and prove, for example binary tree problem, and Fibonacci problem.
• Some complicated programs can be written using recursion and it makes the program shorter than the iterative ones
  • Ex. Tower of Hanoi problem
    

Disadvantage

• Non-tailed recursive programs may take more operations than iterative ones resulting long running time and may consume large storage.