Recursive function

21 December 2020

ในบทนี้ คุณจะได้เรียนรู้เกี่ยวกับ Recursive function เราจะมาดูกันว่า Recursive function คืออะไรและมันถูกนำไปใช้อย่างไรในการเขียนโปรแกรม เนื้อหาในบทนี้จะพูดถึงแนวคิดและการทำงานของ Recursive function เป็นหลัก และสำหรับโค้ดตัวอย่างจะมีภาษา C ภาษา C++ ภาษา Java ภาษา Python และภาษา PHP นี่เป็นเนื้อหาในบทนี้

  • Recursive function คืออะไร
  • การประยุกต์ใช้ในการเขียนโปรแกรม
  • โปรแกรมหาค่า Factorial
  • โปรแกรมหาค่า Fibonacci number

Recursive function คืออะไร

Recursive function (ฟังก์ชันรีเคอร์ชีพ) คือฟังก์ชันที่เรียกใช้ตัวเองเพื่อแก้ปัญหาบางอย่างโดยการแบ่งปัญหาให้เล็กลง จากนั้นรวมผลลัพธ์เข้าด้วยกัน ซึ่งการแก้ปัญหาในรูปแบบนี้เรียกว่า Divide-and-conquer ซึ่งเป็นวิธีการแก้ปัญหาที่พบได้ทั่วไปในชีวิตประวัน เช่น ในการบริหารจัดการองค์กร องค์กรหรือบริษัทนั้นจะถูกแบ่งออกเป็นหน่วยงาน (Division) และแต่ละหน่วยงานจะถูกแบ่งย่อยออกเป็นแผนกต่างๆ (Department) แต่ละแผนกก็จะแบ่งย่อยออกเป็นทีม

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

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

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

การประยุกต์ใช้ในการเขียนโปรแกรม

การใช้งาน Recursive function ในการเขียนโปรแกรมนั้นพบได้ในโจทย์ปัญหาทั่วไป เช่น การหาค่าแฟกทอเรียล (Factorial) ของตัวเลขจำนวนเต็ม n การหาค่าจำนวนฟีโบนัชชี (Fibonacci number) หรือการค้นหาแบบไบนารี (Binary Search) การจัดเรียงข้อมูลด้วยอัลกอริทึม Merge sort การท่องไปในต้นไม้ (Tree traversal) ซึ่งตัวอย่างปัญหาเหล่านี้สามารถใช้ Recursive function ในการแก้ปัญหาได้

สำหรับในตัวอย่างนี้เราจะยกตัวอย่างบางปัญหาที่พบบ่อยและง่ายต่อการเข้าใจ เพื่อให้คุณเข้าใจการทำงานของ Recursive function ซึ่งในตัวอย่างจะแสดงโค้ดในภาษา C ภาษา C++ ภาษา Java ภาษา Python และภาษา PHP ถ้าหากไม่มีภาษาที่คุณต้องการ แค่ดูในภาษาที่คุณคุ้นเคยหรือมีความใกล้เคียงกับภาษาเขียนโปรแกรมมากที่สุด เพราะเราไม่สามารถแสดงตัวอย่างของภาษาทั้งหมดได้

โปรแกรมหาค่า Factorial

ตัวอย่างพื้นฐานที่ง่ายที่สุดในการเรียนรู้และทำความเข้าใจเกี่ยวกับ Recursive function ก็คือการเขียนฟังก์ชันเพื่อหาค่า Factorial ของจำนวนเต็ม n ในตัวอย่างนี้ เราจะเขียนโปรแกรมสำหรับหาค่า Factorial ของจำนวนเต็ม n โดยการใช้ Recursive function นี่เป็นโค้ดตัวอย่างของโปรแกรมในภาษาต่างๆ

factorial.cpp
#include <iostream>
using namespace std;

int fac(int n)
{
    if (n == 0) {
        return 1;
    } else {
        return n * fac(n - 1);
    }
}

int main()
{
    int n = 5;
    cout << n << "! = " << fac(n) << endl;
    return 0;
}
factorial.c
#include <stdio.h>

int fac(int n)
{
    if (n == 0) {
        return 1;
    } else {
        return n * fac(n - 1);
    }
}

int main()
{
    int n = 5;
    printf("%d! = %d", 5, fac(n));
    return 0;
}
Factorial.java
package com.marcuscode.function;

public class Factorial {

    private static int fac(int n) {
        if (n == 0) {
            return 1;
        } else {
            return n * fac(n - 1);
        }
    }

    public static void main(String[] args) {
        int n = 5;
        System.out.println(n + "! = " + fac(n));
    }
}
factorial.py
def fac(n):
    if n == 0:
        return 1
    else:
        return n * fac(n - 1)

n = 5
print("%d! = %d" % (n, fac(n)))
factorial.php
<?php
function fac($n) {
    if ($n == 0) {
        return 1;
    } else {
        return $n * fac($n - 1);
    }
}

$n = 5;
printf("%d! = %d", $n, fac($n));

นี่เป็นผลลัพธ์การทำงานของโปรแกรม เราได้เรียกใช้ฟังก์ชันสำหรับหาค่า Factorial ของ 5 สำหรับหาค่าของ 5! และผลลัพธ์ที่ได้มีค่าเป็น 120

5! = 120

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

สิ่งที่สำคัญเกี่ยวกับโปรแกรมนี้ก็คือฟังก์ชัน fac() ฟังก์ชันนี้เป็นฟังก์ชันที่ใช้สำหรับหาค่าของ Factorial ของจำนวนเต็ม n จากพารามิเตอร์ที่รับเข้ามา จากนั้นส่งค่ากลับเป็นค่า Factorial ของตัวเลขดังกล่าว

int n = 5;
cout << n << "! = " << fac(n) << endl;

ที่จุดเริ่มต้นในฟังก์ชัน main() เราเรียกใช้ฟังก์ชันเพื่อหาค่า Factorial ของจำนวนเต็มบวก 5 และแสดงผลลัพธ์ออกทางหน้าจอ นี่เป็นจุดที่การเรียกใช้ตัวเองหรือ Recursive calls ได้เริ่มต้นขึ้น

  1. โปรแกรมส่ง 5 เข้าไปยังฟังก์ชัน fac() ผ่านพารามิเตอร์ n และตรวจสอบว่ามีค่าเท่ากับ 0 หรือไม่ ถ้าเงื่อนไขเป็นจริง โปรแกรมจะส่งค่ากลับเป็น 1 และหยุดเรียกใช้ตัวเอง จากนั้นคำอธิบายจะข้ามไปที่ข้อ (4) แต่ถ้าไม่ใช่ทำในข้อต่อไป

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

  3. ในตอนนี้โปรแกรมส่งค่า 4 ไปยังฟังก์ชัน fac() และย้อนกลับไปทำที่ขั้นตอน (1) ใหม่ แต่เปลี่ยนค่าในพารามิเตอร์ n เป็น 4 แทน

  4. ในขณะที่โปรแกรมเรียกใช้ตัวเองโดยลดค่า n ลงเรื่อยๆ จนค่าในตัวแปรเท่ากับ 0 ฟังก์ชันส่งค่ากลับเป็น 1 และเรียกหยุดเรียกใช้ตัวเอง นี่เป็นเงื่อนไขสำหรับหยุดเรียกใช้ตัวเอง ตามคำนิยาม 0! นั้นมีค่าเท่ากับ 1 และไม่มีค่า Factorial สำหรับตัวเลขที่น้อยกว่า 0

  5. เมื่อโปรแกรมหยุดเรียกใช้ตัวเอง มันส่งค่ากลับมายังการเรียกใช้แต่ละระดับในรูปแบบต่อไปนี้ 120 <- 5 * (4 * (3 * (2 * (1 * (1)))))

  6. แต่ละวงเล็บคือการเรียกใช้ตัวเองของฟังก์ชัน fac() ในตอนสุดท้ายค่าที่ส่งกลับมาทั้งหมดจะถูกนำมาคูณกันและส่งค่ากลับมายังที่ที่เราเรียกใช้ฟังก์ชันครั้งแรกใน main() ดังนั้น 120 จึงเป็นคำตอบสำหรับตัวอย่างการทำงานนี้

การทำงานของโปรแกรมสามารถแสดงได้ดังแผนภาพต่อไปนี้

fac(5) = 5 * fac(4)
fac(4) = 4 * fac(3)
fac(3) = 3 * fac(2)
fac(2) = 2 * fac(1)
fac(1) = 1 * fac(0)
fac(0) = 1
// หยุดเรียกตัวเอง
// และเริ่มต้นส่งค่ากลับ
fac(0) = 1 
fac(1) = 1 * 1 <- fac(0)
fac(2) = 2 * 1 <- fac(1)
fac(3) = 3 * 2 <- fac(2)
fac(4) = 4 * 6 <- fac(3)
fac(5) = 5 * 24 <- fac(4)
fac(5) = 120

อย่างที่คุณเห็นในตัวอย่าง ในการคำนวณหาผลลัพธ์ของ 5! ผลลัพธ์ของมันไม่ได้ถูกคำนวณในทันที เนื่องจาก 5! นั้นมีค่าเท่ากับ 5 * 4! ดังนั้นมันรอผลลัพธ์จากการหา 4! ให้เสร็จก่อน และ 4! ก็เช่นเดียวกัน มีค่าเท่ากับ 4 * 3! มันรอผลลัพธ์จากการหา 3! ก่อน

จนกระทั่งในที่สุด 0! มีค่าเท่ากับ 1 นี่ทำให้การเรียกใช้ตัวเองจบลง และผลลัพธ์ถูกส่งกลับคืน 1! ที่รอผลลัพธ์จาก 1 * 0! ได้รับคำตอบ และมันส่งกลับไปให้ 2! ที่รอผลลัพธ์จาก 2 * 1! และทำย้อนกลับขึ้นไปจนกระทั่ง 5! ที่รอผลลัพธ์จาก 5 * 4! ซึ่งในตอนนี้ค่าของ 4! ถูกคำนวณเรียบร้อยแล้ว ดังนั้นมันส่งผลลัพธ์สุดท้ายเป็น 5 * 4! = 120 และส่งกลับไปยังการเรียกใช้ครั้งแรกในฟังก์ชัน main()

และนี่เป็นขั้นตอนการทำงานจริงๆ ของ Recursive function สำหรับหาค่า Factorial ซึ่งการทำงานในรูปแบบนี้เรียกว่า Divide-and-conquer แบบทางเดียว

โปรแกรมหาค่า Fibonacci number

Fibonacci number (จำนวนฟีโบนัชชี) นั้นเป็นลำดับของตัวเลขโดยที่ตัวเลขในลำดับใดๆ จะเป็นผลของการบวกค่าของตัวเลขสองลำดับก่อนหน้าจากมัน โดยที่เลขในสองลำดับแรกจะเป็น 0 และ 1 เสมอ นี่เป็นตัวอย่างลำดับของจำนวนฟีโบนัชชี

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...

จะเห็นว่าลำดับของตัวเลขจะเริ่มจาก 0 และ 1 จากนั้นค่าของตัวเลขที่ลำดับใดๆ ยกตัวอย่างเช่น 13 จะเป็นตัวเลขที่ได้มาจากผลบวกของตัวเลขสองลำดับก่อนหน้าของมัน นั่นคือ 5 + 8 และเช่นเดียวกัน 8 ก็ได้มากจาก 3 +5 ซึ่งเป็นตัวเลขในสองลำดับก่อนหน้า

สำหรับตัวอย่างนี้ เราจะเขียนโปรแกรมเพื่อบอกว่าจำนวนฟีโบนัชชีในลำดับที่ n คือตัวเลขอะไร โดยการใช้ Recursive function ในการแก้ปัญหา นี่เป็นตัวอย่างโค้ดของโปรแกรมในภาษาต่างๆ

fibonacci.cpp
#include <iostream>
using namespace std;

int fibonacci(int n)
{
    if (n == 1) {
        return 0;
    } else if (n == 2) {
        return 1;
    } else {
        return fibonacci(n - 2) + fibonacci(n - 1);
    }
}

int main()
{
    int n = 8;
    cout << "Fibonacci sequence at position ";
    cout << n << " is " << fibonacci(n) << endl;
    return 0;
}
fibonacci.c
#include <stdio.h>

int fibonacci(int n)
{
    if (n == 1) {
        return 0;
    } else if (n == 2) {
        return 1;
    } else {
        return fibonacci(n - 2) + fibonacci(n - 1);
    }
}

int main()
{
    int n = 8;
    printf("Fibonacci sequence at position ");
    printf("%d is %d\n", n , fibonacci(n));
    return 0;
}
Fibonacci.java
package com.marcuscode.function;

public class Fibonacci {

    private static int fibonacci(int n) {
        if (n == 1) {
            return 0;
        } else if (n == 2) {
            return 1;
        } else {
            return fibonacci(n - 2) + fibonacci(n - 1);
        }
    }

    public static void main(String[] args) {
        int n = 8;
        System.out.print("Fibonacci sequence at position ");
        System.out.println(n + " is " + fibonacci(n));
    }
}
fibonacci.py
def fibonacci(n):
    if n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return fibonacci(n - 2) + fibonacci(n - 1)

n = 8
print("Fibonacci sequence at position ", end = "")
print("%d is %d\n" % (n , fibonacci(n)))
fibonacci.php
<?php
function fibonacci($n) {
    if ($n == 1) {
        return 0;
    } else if ($n == 2) {
        return 1;
    } else {
        return fibonacci($n - 2) + fibonacci($n - 1);
    }
}

$n = 8;
printf("Fibonacci sequence at position ");
printf("%d is %d\n", $n , fibonacci($n));

นึ่เป็นผลลัพธ์การทำงานของโปรแกรมจากการรันโปรแกรมสองครั้ง เพื่อหาเลขฟีโบนัชชีในลำดับที่ 8 และ 15

Fibonacci sequence at position 8 is 13

Fibonacci sequence at position 15 is 377

ในตัวอย่างนี้ เป็นโปรแกรมสำหรับค่าเลขฟีโบนัชชีในลำดับที่กำหนด เราได้สร้างฟังก์ชัน fibonacci() ฟังก์ชันนี้รับค่าลำดับเข้ามาผ่านพารามิเตอร์ n และส่งค่ากลับเป็นเลขฟีโบนัชชีที่อยู่ในลำดับดังกล่าว ฟังก์ชันได้เริ่มถูกเรียกใช้งานจากฟังก์ชัน main() นี่เป็นที่ที่การเรียกใช้ตัวเองได้เริ่มต้นขึ้น

if (n == 1) {
    return 0;
} else if (n == 2) {
    return 1;
} else  {
...

ในฟังก์ชัน fibonacci() มีสองเงื่อนไขสำหรับหยุดการเรียกใช้ตัวเอง นั่นคือเมื่อค่าลำดับในตัวแปร n เป็น 1 และ 2 นั่นเป็นเพราะว่าจากคำนิยาม เลขฟีโบนัชชีในสองลำดับแรกจะเป็น 0 และ 1 ตามลำดับ ดังนั้นเราส่งค่ากลับเป็นค่าเหล่านี้เพื่อหยุดฟังก์ชันจากการเรียกใช้ตัวเอง

...
} else {
    return fibonacci(n - 2) + fibonacci(n - 1);
}

ในกรณีที่พารามิเตอร์ไม่ใช่สองลำดับแรก ฟังก์ชันจะเรียกใช้ตัวมันเองไปเรื่อยๆ สิ่งที่มันทำก็คือเรียกใช้ตัวมันเองโดยส่งพารามิเตอร์เป็นสองลำดับก่อนหน้า นั่นหมายความว่าเพื่อหาเลขฟีโบนัชชีในลำดับที่ 8 fibonacci(8) โปรแกรมจะต้องทำการหาคำตอบของสองลำดับก่อนหน้ามันก่อนด้วย fibonacci(6) + fibonacci(7)

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

และนี่ก็เป็นวิธีที่ฟังก์ชัน fibonacci() ซึ่งเป็นฟังก์ชันสำหรับการหาจำนวนฟีโบนัชชีของตัวเลขในลำดับที่ n ทำงาน

ในบทนี้ คุณได้เรียนรู้เกี่ยวกับ Recursive function เราได้พูดถึงความหมายของ Recursive function และตัวอย่างการประยุกต์ใช้งานในการเขียนโปรแกรมสำหรับหาค่า Factorial และการหาจำนวนฟีโบนัชชี เราได้แสดงตัวอย่างของโปรแกรมในภาษาต่างๆ เช่น ภาษา C ภาษา C++ ภาษา Java ภาษา Python และภาษา PHP เป็นต้น

บทความนี้เป็นประโยชน์หรือไม่?Yes·No