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

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

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

برای درک بهتر بازگشت لازم است آن را با برنامه‌نویسی سنتی شیءگرا مقایسه کنیم.

فیلم آموزش برنامه نویسی سوئیفت – برنامه نویسی iOS با Swift در فرادرس

کلیک کنید

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

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

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

CLASS یا STRUCT

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

1//simple struct example - methods & properties
2struct Car {
3    
4    var color: String
5    var make: String
6        
7    init(color: String, make: String) {        
8        self.color = color
9        self.make = make
10    }
11    
12    func buildCar() {
13        print("a \(color) \(make) has been built..")
14    }   
15}

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

1//simple usable class
2class LLNode<T> {  
3    var key: T?
4    var previous: LLNode?
5    var next: LLNode?
6}
7//gives compilation error
8struct Tree<T> {    
9    var key: T?
10    var left: Tree?
11    var right: Tree?
12}

تابع‌ها

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

1//fibonacci sequence - traditional approach
2extension Int {
3func fibNormal() -> Array<Int>? {
4                
5           //check trivial condition
6           guard self > 2 else {
7               return nil
8           }
9//initialize the sequence
10           var sequence: Array<Int> = [0, 1]                
11           var i: Int = sequence.count
12while i != self {            
13               let results: Int = sequence[i - 1] + sequence[i - 2]
14               sequence.append(results)            
15               i += 1
16           }
17return sequence        
18     }
19}
20//execute sequence
21let positions: Int = 4
22let results: Array<Int>? = positions.fibNormal()

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

1//fibonacci sequence - recursive approach
2extension Int {
3   
4     mutating func fibRecursive(_ sequence: Array<Int> = [0, 1]) -> Array<Int>? {
5        
6        var final = Array<Int>()
7                
8        //mutated copy
9        var output = sequence
10//check trivial condition
11        guard self > 2 else {
12            return nil
13        }
14let i: Int = output.count
15        
16        
17        //set base condition
18        if i == self {
19            return output
20        }
21                
22        let results: Int = output[i - 1] + output[i - 2]
23        output.append(results)        
24        
25        //set iteration
26        final = self.fibRecursive(output)!        
27        
28        return final       
29    }
30}
31//execute sequence
32var positions: Int = 4
33let results: Array<Int>? = positions.fibRecursive()

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

کلاس‌ها

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

1   //recursive depth-first search 
2    
3    func traverse() {   
4    
5        guard self.key != nil else {
6            return
7        }
8        
9        //process left side
10        if self.left != nil {
11            left?.traverse()
12        }
13        
14       print("...node \(self.key!) visited..")
15    //process the right side
16       if self.right != nil {
17            right?.traverse()
18        }
19        
20    }

Enum-ها

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

1//recursive enumeration
2indirect enum Algorithm<T> {
3    
4    case Empty
5    case Elements(Array<T>)
6    case InsertionSort(Algorithm<T>)
7    case BubbleSort(Algorithm<T>)
8    case SelectionSort(Algorithm<T>)    
9}

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

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

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

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

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

==