ساخت الگوریتم بازگشتی در سوئیفت — از صفر تا صد

منظور از الگوریتم‌های بازگشتی به طور خلاصه یک تکنیک کدنویسی است که مجموعه نامعینی از ارجاع‌ها را به خود تابع بازگشت می‌دهد. در این مقاله به بررسی مفهوم «بازگشت» (Recursion) پرداختi و شیوه ساخت الگوریتم بازگشتی در سوئیفت را مورد بررسی قرار می‌دهیم.

طرز کار الگوریتم بازگشتی در سوئیفت

برای درک بهتر بازگشت لازم است آن را با برنامه‌نویسی سنتی شیءگرا مقایسه کنیم. در اغلب راه‌حل‌ها، کد از اشیای متفاوتی تشکیل می‌یابد که در اغلب موارد با هم قابل تعویض هستند. بدین ترتیب برنامه‌نویس به اشیای مختلف (ماند کلاس‌ها) ارجاع می‌دهد تا یک مدل بسازد. با این حال تکنیک بازگشتی مدلی با یک شیء می‌سازد که به خودش ارجاع می‌دهد:

رویکرد سنتی – ارجاع اشیا به اشیای دیگر

رویکرد بازگشتی – ارجاع شیء به خودش

CLASS یا STRUCT

چند روش برای اجرای بازگشت در سوئیفت وجود دارد. اگر به زبان‌هایی مانند C عادت دارید، باید بدانید که شیو مدیریت انواع از سوی سوئیفت متفاوت است. بسیاری از اشیای سوئیفت مانند protocol-ها، struct-ها و enum-ها به عنوان اعضای درجه یک زبان محسوب می‌شوند. بدین ترتیب اغلب انواع عملیات که برای کلاس تدارک دیده شده‌اند را می‌توان با یک struct جایگزین کرد:

//simple struct example - methods & properties
struct Car {
    
    var color: String
    var make: String
        
    init(color: String, make: String) {        
        self.color = color
        self.make = make
    }
    
    func buildCar() {
        print("a \(color) \(make) has been built..")
    }   
}

Struct-های سوئیفت کامپوننت‌های سبکی هستند که به عنوان انواع مقداری (By Value) عمل می‌کنند. به طور عکس، کلاس‌ها در سوئیفت به صورت ارجاعی (By Reference) عمل می‌کنند. از آنجا که وهله‌های Struct کپی می‌شوند و مورد ارجاع قرار نمی‌گیرند، نمی‌توان از آن‌ها برای ساخت مدل‌های بازگشتی استفاده کرد:

//simple usable class
class LLNode<T> {  
    var key: T?
    var previous: LLNode?
    var next: LLNode?
}
//gives compilation error
struct Tree<T> {    
    var key: T?
    var left: Tree?
    var right: Tree?
}

تابع‌ها

بازگشت را می‌توان در دنباله مشهور فیبوناچی نیز مشاهده کرد. ایده آن ساخت یک دنباله عددی است که از جمع کردن دو عضو قبلی دنباله ساخته می‌شود. در ادامه تکنیک‌های سنتی و بازگشتی را با هم مقایسه می‌کنیم:

//fibonacci sequence - traditional approach
extension Int {
func fibNormal() -> Array<Int>? {
                
           //check trivial condition
           guard self > 2 else {
               return nil
           }
//initialize the sequence
           var sequence: Array<Int> = [0, 1]                
           var i: Int = sequence.count
while i != self {            
               let results: Int = sequence[i - 1] + sequence[i - 2]
               sequence.append(results)            
               i += 1
           }
return sequence        
     }
}
//execute sequence
let positions: Int = 4
let results: Array<Int>? = positions.fibNormal()

تکنیک بازگشتی به صورت زیر است:

//fibonacci sequence - recursive approach
extension Int {
   
     mutating func fibRecursive(_ sequence: Array<Int> = [0, 1]) -> Array<Int>? {
        
        var final = Array<Int>()
                
        //mutated copy
        var output = sequence
//check trivial condition
        guard self > 2 else {
            return nil
        }
let i: Int = output.count
        
        
        //set base condition
        if i == self {
            return output
        }
                
        let results: Int = output[i - 1] + output[i - 2]
        output.append(results)        
        
        //set iteration
        final = self.fibRecursive(output)!        
        
        return final       
    }
}
//execute sequence
var positions: Int = 4
let results: Array<Int>? = positions.fibRecursive()

به تفاوت‌های تابع‌ها توجه کنید. در نگاه نخست، می‌بینیم که fibRecursive از یک حالت مبنا استفاده می‌کند و سپس خودش را فرا می‌خواند. به طور عکس fibNormal منطق کنترلی را در یک حلقه while نگه می‌دارد. چنان که می‌بینید منطق بازگشتی در اغلب موارد موجب افزایش پیچیدگی می‌شود، چون کل یک کلاس، تابع یا متد در اغلب موارد به عنوان یک ساختار کنترلی مورد استفاده قرار می‌گیرد.

کلاس‌ها

با این که بازگشت در اغلب موارد موجب افزایش پیچیدگی می‌شود، اما در این بخش الگوریتم «جستجوی عمق-اول» (depth-first search) را بررسی می‌کنیم. چنان که می‌دانید این کد همراه با یک «پشته فراخوانی» (Call Stack) برای پیمایش یک «درخت جستجوی دودویی» (binary search tree) مورد استفاده قرار می‌گیرد. با این که می‌توان این الگوریتم را طوری بازنویسی کرد که از تکنیک تکرار بهره بگیرد، اما الگوریتم بازگشتی یک راه‌حل بهینه ارائه می‌کند:

   //recursive depth-first search 
    
    func traverse() {   
    
        guard self.key != nil else {
            return
        }
        
        //process left side
        if self.left != nil {
            left?.traverse()
        }
        
       print("...node \(self.key!) visited..")
    //process the right side
       if self.right != nil {
            right?.traverse()
        }
        
    }

Enum-ها

Enum-ها نیز مانند بسیاری از اشیای درجه اول سوئیفت عمل می‌کنند. همان طور که Enum-ها در زبان‌های دیگر استفاده می‌شوند، در سوئیفت نیز الگوریتم نوع enum برای مدل‌سازی رفتار استفاده می‌شود. این مدل به مدیریت حالت‌های خاص کمک می‌کند. enum یک نوع بازگشتی نامیده می‌شود، زیرا شامل مقادیری است که از نوع Algorithm نیز هستند:

//recursive enumeration
indirect enum Algorithm<T> {
    
    case Empty
    case Elements(Array<T>)
    case InsertionSort(Algorithm<T>)
    case BubbleSort(Algorithm<T>)
    case SelectionSort(Algorithm<T>)    
}

یکی از اهداف Enum-ها بهبود خوانایی کد است. در این مورد می‌توانیم از Algorithm برای ارائه پشتیبانی با نوع امن برای یک پیاده‌سازی استفاده کنیم و می‌توانیم آن را به سهولت برای پشتیبانی از سناریوهای دیگر نیز بسط دهیم:

//build an algorithm model
let list = Algorithm.Elements([8, 2, 10, 9, 7, 5])
let model = Algorithm.InsertionSort(list)
...

بدین ترتیب به پایان این مقاله می‌رسیم.

اگر این مطلب برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌های برنامه‌‌نویسی
• آموزش برنامه‌نویسی Swift (سوئیفت) برای برنامه نویسی iOS
• مجموعه آموزش‌های دروس علوم و مهندسی کامپیوتر
• آموزش سوئیفت (Swift) — مجموعه مقالات مجله فرادرس
• آموزش برنامه‌نویسی سوئیفت (Swift): متغیر، ثابت و انواع داده – بخش اول

==