KodeDevel

بازگشتی (recursion) در برنامه نویسی

تاریخ انتشار:
آخرین بروزرسانی:
بازگشتی (recursion) در برنامه نویسی

تابع بازگشتی

تابع (متد) بازگشتی به تابعی گفته میشه که داخل خودش دوباره صداش بزنیم.

به طور معمول هنگامی که اجرای کد های یک تابع تموم بشه از تابع خارج میشیم و بقیه ی کد های برنامه اجرا میشن؛ اما با صدا زدن تابع داخل خودش بجای خارج شدن از تابع، همون تابع (احتمالا با مقادیر جدید) داخل خودش اجرا میشه و بعد از پایان اجرای تابع، به تابع قبلی بر میگردیم؛ به این نوع توابع (متد ها)، بازگشتی میگیم.

یک تابع میتونه بی نهایت داخل خودش صدا زده بشه، اگه این روند متوقف نشه در اثر مصرف منابع سیستمی برنامه دچار StackOverFlow میشه؛ بنابراین توابع بازگشتی رو با دستورات شرطی (selector ها) کنترل میکنیم.

به جایی که روند صدا زدن تابع متوقف بشه base-case میگیم.

مثال

static void myFunction(int count){
 if(count <= 0){ //base-case
   System.out.println("Base-case reached");
   System.out.println("Hello from " + count);
 }else{
   myFunction(count - 1);
   System.out.println("Hello from " + count);
 }
}
        
fun myFunction(count: Int){
  if(count <= 0){ //base-case
    println("Base-case reached")
    println("Hello from $count")
  }else{
    myFunction(count - 1)
    println("Hello from " + count)
  }
}
        
function myFunction(count) {
  if (count <= 0) { //base-case
    console.log("Base-case reached");
    console.log("Hello from " + count);
  } else {
    myFunction(count - 1);
    console.log("Hello from " + count);
  }
}
        
def myFunction(count):
    if count <= 0: #base-case
        print("Base-case reached")
        print("Hello from " + str(count))
    else:
        myFunction(count - 1)
        print("Hello from " + str(count))

در مثال بالا ابتدا برنامه مقدار count رو بررسی میکنه اگه کوچک تر یا مساوی صفر باشه یک پیغام نمایش میده و از تابع خارج میشه ولی اگه بزرگتر از صفر باشه، داخل بدنه ی else قبل از نمایش پیغام یک بار تابع خودشو صدا میزنه و کد های داخل تابع جدید به اجرا در میاد؛ در تابع جدید مقدار count یک واحد کمتر از مقدار قبلی خواهد بود و همین عمل تکرار میشه تا به base-case برسیم و سپس پیغام Hello from... به ترتیب از آخرین باری که تابع رو صدا زدیم (یعنی count <= 0) نمایش داده میشه تا به اولین اجرای تابع برسیم و در نهایت برنامه از تابع اصلی نیز خارج میشه.

مثال

میخوایم فاکتوریل یک عدد رو به روش بازگشتی حساب کنیم

static long fact(int n){
  if(n == 0) return 1;
  else return n * fact(n-1);
}
        
fun fact(n: Int): Long = if(n == 0) 1 else n * fact(n-1);
        
function fact(n) {
  if (n === 0) return 1;
  else return n * fact(n - 1);
}
        
def fact(n):
    if n == 0: 
        return 1
    else: 
        return n * fact(n - 1)

در مثال بالا با هربار صدا زدن تابع fact یک واحد از مقدار پارامتر n کم میشه تا به base-case برسیم و سپس از base-case برنامه شروع میکنه به برگردوندن نتیجه به تابع قبلی

در زیر نحوه ی عمل کردن تابع بازگشتی fact برای 4 فاکتوریل به صورت تصویری بیان شده.

نحوه ی عملکرد تابع بازگشتی fact برای 4 فاکتوریل.
نحوه ی عملکرد تابع بازگشتی fact برای 4 فاکتوریل.

در زیر بعد از رسیدن به base-case به صورت جبری عملکرد تابع fact برای 4 فاکتوریل بیان شده.

fact(0) = 1 //base-case
fact(1) = 1 * fact(0) // 1*1=1
fact(2) = 2 * fact(1) // 2*1=2
fact(3) = 3 * fact(2) // 3*2=6
fact(4) = 4 * fact(3) // 4*6=24

مثال

میخوایم دنباله ی فیبوناچی رو به روش بازگشتی حل کنیم.

static int fib(int index){
  if(index == 1 || index == 2) return 1;
  else return fib(index-1) + fib(index-2);
}
        
fun fib(index: Int): Int{
  if(index == 1 or index == 2) return 1
  else return fib(index - 1) + fib(index - 2)
}
        
function fib(index) {
  if (index === 1 || index === 2) return 1;
  else return fib(index - 1) + fib(index - 2);
}
        
def fib(index):
    if index == 1 or index == 2: 
        return 1
    else: 
        return fib(index - 1) + fib(index - 2)

مثال

میخوایم ببینیم یک کلمه متقارن (Palindrome) است یا خیر.

static boolean isPalindrome(String word){
  if(word.length() <= 1){
    return true;
  } else if(word.charAt(0) != word.charAt(s.length - 1)){
      return false;
  } else{
     return isPalindrome(word.substring(1, word.length -1);
  }
}
        
fun isPalindrome(String word): Boolean{
  if(word.length <= 1) return true
  else if(word[0] != word[word.length - 1]){
    return false
  }else {
    return isPalindrome(word.substring(1, word.length - 1))
  }
}
        
function isPalindrome(word) {
  if (word.length <= 1) {
    return true;
  } else if (word.charAt(0) !== word.charAt(word.length - 1)) {
    return false;
  } else {
    return isPalindrome(word.substring(1, word.length - 1));
  }
}
        
def isPalindrome(word):
    if len(word) <= 1:
        return True
    elif word[0] != word[-1]:
        return False
    else:
        return isPalindrome(word[1:-1])

مقایسه ی بازگشتی (Recursion) با حلقه ها

بعضی از مسائل با بازگشتی راحت تر از حلقه ها حل میشن

بازگشتی در برنامه نویسی یعنی صدا زدن تابع (متد) داخل خودش؛ این کار میتونه جایگزین استفاده از حلقه (loop) ها بشه.

گاهی حل مسائل برنامه نویسی از طریق تعریف توابع بازگشتی ساده تر از حل آنها توسط حلقه هاست.

بیشتر مسائلی که با بازگشتی حل میشن، با حلقه ها نیز قابل حل هستند و برعکس.

استفاده از حلقه ها برای حل مسائل نسبت به استفاده از توابع بازگشتی بهینه تره، در حلقه ها یک متغیر تعریف می کنیم و تا پایان کار ازش استفاده میکنیم اما در توابع بازگشتی با هربار صدا زدن تابع، کد های داخل تابع دوباره اجرا میشن و متغیر های جدیدی ایجاد میشه که افزایش متغیر ها باعث افزایش منابع مصرفی سیستم میشه.

فرض کنید میخوایم یک کیک رو بخوریم؛ تا زمانی که کیک وجود داره میتونیم یک تیکه از کیک رو برداریم و بخوریم؛ وجود کیک base-case مساله است. 

eat(Cake cake){
 if cake.exists()
     cake.takeOneSlice()
     eat(cake)
}

به طور کلی (تجربه ی شخصی) اگه بخوایم از حلقه ها به عنوان جایگزین توابع بازگشتی استفاده کنیم از حلقه ی while به عنوان base-case مسأله استفاده می کنیم. 

eatCake(Cake cake){
 
 while cake.exists
   cake.takeOneSlice()
     
}

تابع بازگشتی کمکی (Recursive Helper Function)

با تابع بازگشتی کمکی (Recursive Helper Function) میتونیم مقادیری که قراره به تابع بازگشتی اصلی پاس بدیم رو خلاصه کنیم.

میتونیم یک تابع برای تابع بازگشتی (recursive) تعریف کنیم تا مقادیری که قراره به عنوان پارامتر تابع بازگشتی پاس بدیم رو باهاش خلاصه کنیم، به این تابع تابع بازگشتی کمکی (Recursive Helper Function) میگیم.

مثال پیدا کردن کلمه ی متقارن میتونه بهینه تر بشه؛‌ در مثالی که زده شد با هربار صدا کردن تابع isPalindrome یک String جدید توسط تابع substring ایجاد میشه؛ میتونیم بجای ایجاد substring برای هر بار صدا زدن isPalindrome از index استفاده کنیم با این کار منابع سیستمی کمتری درگیر و الگوریتم بهینه تر میشه.

static boolean isPalindrome(String word, int low, int hight){
  if(low >= high) return true;
  else if(s.charAt(low) != word.charAt(high)) return false;
  else return isPalindrome(word, low + 1, high - 1);
}
        
fun isPalindrome(word: String, low: Int, high: Int): Boolean{
  if(low <= high) return true
  else if(s.charAt(low) != word.charAt(high)) return false;
  else return isPalindrome(word, low + 1, high - 1)
}
        
function isPalindrome(word, low, high) {
  if (low === undefined && high === undefined) {
    let low = 0;
    let high = word.length - 1;
    return isPalindrome(word, low, high);
  }

  if (low >= high) return true;
  else if (word.charAt(low) !== word.charAt(high)) return false;
  else return isPalindrome(word, low + 1, high - 1);
}
        
def isPalindrome(word, low, high):
    if low >= high:
        return True
    elif word[low] != word[high]:
        return False
    else:
        return isPalindrome(word, low + 1, high - 1)

میتونیم برای isPalindrome یک تابع کمکی (helper function) تعریف کنیم.

static boolean isPalindrome(String word){
  int low = 0;
  int high = word.length() - 1;
  return isPalindrome(word, low, high);
}
        
fun isPalindrome(word: String){
  val low = 0;
  val high = word.length - 1
  return isPalindrome(word, low, high)
}
        
function isPalindrome(word){
  const low = 0;
  const high = word.length - 1
  isPalindrome(word, low, high)
}
        
def isPalindrome(word):
  low = 0
  high = len(word) - 1
  return isPalindrome(word, low, high)

مثال

در مثال زیر میخوایم مرتب سازی (selection sort) رو به روش بازگشتی پیاده سازی کنیم.

fun sort(double[] list){
  int low =0;
  int high = list.length - 1;

  sort(list, low, high);
}

static void sort(double[] list, int low, int high){

  if(low < high){

    int indexOfMin = low;
    double min = list[low];

    for(int i= low + 1; i<= high; i++){
      if(list[i] < min){
        min = list[i];
        indexOfMin = i;
      }
    }

    list[indexOfMin] = list[low];
    list[low] = min;

    sort(list, low + 1, high);

  }
}
        
fun sort(list: Array<Double>){
  val low = 0
  val high = list.size

  sort(list, low, high)
}
        
fun sort(list: Array<Double>, low: Int, high: Int){

  if(low < high){
   
    var indexOfMin = low;
    var min = list[low];

    for(i in low + 1 to high){
      if(list[i] < min){
        min = list[i]
        indexOfMin = i
      }
    }

    list[indexOfMin] = list[low]
    list[low] = min

    sort(list, low + 1, high)
  }
}
        
function sort(list){
  const low = 0
  const high = list.length - 1
  sort(list, low, high)
}

function sort(list, low, high) {

  if (low < high) {
    let indexOfMin = low;
    let min = list[low];

    for (let i = low + 1; i <= high; i++) {
      if (list[i] < min) {
        min = list[i];
        indexOfMin = i;
      }
    }

    list[indexOfMin] = list[low];
    list[low] = min;

    sort(list, low + 1, high);
  }
}
        
def sort(list):
  sort(list, 0, len(list) - 1)


def sort(list, low=None, high=None):
    if low < high:
        indexOfMin = low
        min_val = list_array[low]

        for i in range(low + 1, high + 1):
            if list[i] < min_val:
                min_val = list[i]
                indexOfMin = i

        list[indexOfMin] = list[low]
        list[low] = min_val

        sort(list_array, low + 1, high)

در مثال زیر میخوایم جستجوی دودویی (binary search) رو با بازگشتی پیاده کنیم.

static int binarySearch(double[] list, int key){
  int low = 0;
  int high = list.length - 1;
  return binarySearch(list, key, low, high)
}

static int binarySearch(double[] list, int key, int low, int high)
  if(low > high) return -low-high;

  int mid = (low + high)/2;
  
  if(key < list[mid]){
    return binarySearch(list, key, low, mid - 1);
  }else if(key > list[mid]{
    return binarySearch(list, key, mid + 1, high);
  }else{
    return mid;
  }
}
        
fun binarySearch(list: Array<Double>, key: Double){
  val low = 0
  val high = list.size() - 1
  return binarySearch(list, key, low, high)
}

fun binarySearch(list: Array<Double>, key: Double, low: Int, high: Int): Int {
  if(low > high) return -low-high

  var mid = (low + high)/2

  if(key < list[mid]){
    return binarySearch(list, key, low, mid-1)
  }else if(key > list[mid]){
    return binarySearch(list, key, mid + 1, high)
  }else {
    return mid
  }

}
        
function binarySearch(list, key){
  return binarySearch(list, 0, list.length - 1) 
}

function binarySearch(list, key, low, high) {
  if (low > high) return -low - high;

  let mid = Math.floor((low + high) / 2);

  if (key < list[mid]) {
    return binarySearch(list, key, low, mid - 1);
  } else if (key > list[mid]) {
    return binarySearch(list, key, mid + 1, high);
  } else {
    return mid;
  }
}        
def binarySearch(list_array, key):
  return binarySearch(list_array, key, 0, length(list_array) - 1)

def binarySearch(list_array, key, low, high):
    if low is None and high is None:
        low = 0
        high = len(list_array) - 1
        return binarySearch(list_array, key, low, high)

    # 4-argument search logic
    if low > high:
        return -low - high

    mid = (low + high) // 2

    if key < list_array[mid]:
        return binarySearch(list_array, key, low, mid - 1)
    elif key > list_array[mid]:
        return binarySearch(list_array, key, mid + 1, high)
    else:
        return mid

تابع tail-recursive

تابع tail-recursive بهینه تر از تابع recursive معمولی است.

تابع (متد) tail recursive به تابعی گفته میشه که بعد از اجرای همه ی کد های داخلش، صدا زده میشه.

در واقع در این توابع اخرین کدی که اجرا میشه صدا زدن تابع داخل خودشه.

فرم کلی:

Type myTailRecFunction(...){

  do some operations

  myTailRecFunction(...)

}

در توابع tail recursive، همه ی کد های داخل تابع اجرا شده و سپس تابع صدا زده میشه؛ چون عملیاتی برای اجرا بجز صدا زدن تابع باقی نمی مونه این نوع پیاده سازی بهینه تر از recursive معمولی است.

هنگام صدا زدن دوباره ی تابع در این روش، کد های داخل تابع قبلی اجرا شده بنابراین متغیر ها و عملیات در تابع قبلی باقی نمی مونه و حافظه ی کمتری مصرف میشه.

توجه

در کاتلین tail recursive به صورت native پشتیبانی میشه؛ هنگام تعریف تابع کافیه از کلیدواژه ی tailrec قبل از کلیدواژه ی fun استفاده کنیم.

مثال

میخوایم تابع فاکتوریل رو به صورت tail recursive پیاده کنیم.

static long fact(int n){
 return fact(n, 1)
}

static long fact(int n, int result){
  if(n == 0) return result;
  else return fact(n - 1 , n * result)
}

        
tailrec fact(n: Int, result: Int = 1): Long = if(n == 0) return result else return fact(n-1, result * n);
        
function fact(n, result) {
  if (result === undefined) {
    return fact(n, 1);
  }

  if (n === 0) return result;
  else return fact(n - 1, n * result);
}
        
def fact(n, result=None):
    if result is None:
        return fact(n, 1)

    if n == 0:
        return result
    else:
        return fact(n - 1, n * result)

مورد مطالعه (مثال ها)

در این قسمت میخوایم مسأله ی directory size و tower of hanoi رو با بازگشتی حل کنیم.

directory size

با استفاده از روش بازگشتی میخوایم اندازه ی کل پوشه (اندازه ی تمام فایل ها و پوشه های داخلش) رو حساب کنیم. 

static long getSize(File file){
  long size = 0;
  if(file.isDirectory()){
    File[] files = file.listFiles();
    if(files != null){
      for(File f : files){
        if(f.isDirectory()){
          size += getSize(f);
        }else {
          size += f.length();
        }
      }
    }
  }else {
    size += file.length();
  }

  return size;
}
        
fun getSize(file: File): Long{
  var size: Long = 0;
  if(file.isDirectory()){
    val files = file.listFiles()
    if(files != null){
      for(f in files){
        if(f.isDirectory()){
          size+= getSize(f);
        }else{
          size += f.length();
        }
      }
    }
  }
}
        
const fs = require('fs');
const path = require('path');

function getSize(filePath) {
  let size = 0;
  const stats = fs.statSync(filePath);

  if (stats.isDirectory()) {
    let files = fs.readdirSync(filePath);
    if (files !== null) {
      for (let file of files) {
        const f = path.join(filePath, file);
        const fStats = fs.statSync(f);
        if (fStats.isDirectory()) {
          size += getSize(f);
        } else {
          size += fStats.size;
        }
      }
    }
  } else {
    size += stats.size;
  }

  return size;
}
        
import os

def getSize(file_path):
    size = 0
    if os.path.isdir(file_path):
        try:
            files = os.listdir(file_path)
        except OSError:
            files = None

        if files is not None:
            for file in files:
                f = os.path.join(file_path, file)
                if os.path.isdir(f):
                    size += getSize(f)
                else:
                    size += os.path.getsize(f)
    else:
        size += os.path.getsize(file_path)

    return size

tower of hanoi

tower of hanoi یک مسأله ی ذاتا بازگشتیه و ساده ترین راه حل برای حل این مسأله استفاده از روش بازگشتی است.

شرح مساله به این صورته سه تا خونه داریم به نام های A, B, C و n تا دیسک فرضی به ترتیب بزرگیشون توی خونه ی A قرار داره و میخوایم با همین ترتیب و بدون اینکه دیسک های پایینی روی دیسک های بالایی قرار بگیرن از A به B انتقالشون بدیم.

در زیر عملکرد برنامه رو به صورت تصویری برای سه تا دیسک نشون دادیم.

مسأله ی tower of hanoi در برنامه نویسی مسأله ی tower of hanoi در برنامه نویسی

الگوی حل tower of hanoi

برای حل tower of hanoi:

I- ابتدا باید n-1 دیسک رو با کمک B از A به C ببریم.

II- سپس آخرین دیسک (دیسک n ام) رو از A به B ببریم.

III- در نهایت n-1 دیسک رو که به C بردیم، اکنون به کمک A از C به B ببریم.

static void moveDisks(int n){
  moveDisks(n, 'A', 'B', 'C');
}

static void moveDisks(int n, char fromTower, char toTower, char auxTower){
  if(n == 1){
    System.out.println("Move disk " + n + " from " + fromTower + " to " + toTower);
  }else{

    moveDisks(n - 1, fromTower, auxTower, toTower);

    System.out.println("Move disk " + n + " from " + fromTower + " to " + toTower);

    moveDisks(n - 1, auxTower, toTower, fromTower);

  }
}
        
fun moveDisks(n: Int){
  moveDisks(n, 'A', 'B', 'C')
}

fun moveDisks(n: Int, fromTower: Char, toTower: Char, auxTower: Char){
  if(n == 1){
    // Move last disk from A to B
    println("Move disk " + n + " from " + fromTower + " to " + toTower)
  }else{

    moveDisks(n - 1, fromTower, auxTower, toTower)

    println("Move disk " + n + " from " + fromTower + " to " + toTower)

    moveDisks(n - 1, auxTower, toTower, fromTower)

  }
}
        
function moveDisks(n){
  moveDisks(n, 'A', 'B', 'C')
}

function moveDisks(n, fromTower, toTower, auxTower) {

  if (n === 1) {
    console.log("Move disk " + n + " from " + fromTower + " to " + toTower);
  } else {
    moveDisks(n - 1, fromTower, auxTower, toTower);
    console.log("Move disk " + n + " from " + fromTower + " to " + toTower);
    moveDisks(n - 1, auxTower, toTower, fromTower);
  }
}        
def moveDisks(n):
    moveDisks(n, 'A', 'B', 'C')

def moveDisks(n, fromTower, toTower, auxTower):
    if n == 1:
        print("Move disk " + str(n) + " from " + fromTower + " to " + toTower)
    else:
        moveDisks(n - 1, fromTower, auxTower, toTower)
        print("Move disk " + str(n) + " from " + fromTower + " to " + toTower)
        moveDisks(n - 1, auxTower, toTower, fromTower)

خلاصه

  • بعضی از مسائل با روش بازگشتی راحت تر از حلقه ها حل میشن.
  • بازگشتی (recursion) میتونه جایگزین استفاده از حلقه ها بشه.
  • بسیاری از مسائلی که با روش بازگشتی حل میشن توسط حلقه ها نیز قابل حل هستند و برعکس.
  • به تابعی که داخلش خودشو صدا میزنیم تابع بازگشتی میگیم.
  • توابع بازگشتی رو با شرط کنترل می کنیم.
  • هنگامی که بخوایم یک تابع داخل خودش صدا زده نشه از شرط استفاده میکنیم و این حالت پایه (base-case) مسأله است.
  • به تابعی که بعد از اجرای همه ی کد هاش داخل خودش صداش میزنیم، توابع tail-recursive میگیم.
  • تابع tail recursive بهینه تر از تابع recursive است.

بازخورد و دیدگاه‌ ها

اولین نفری باشید که در این صفحه نظر می‌دهید

notifications برای اطلاع از جدیدترین مطالب و پست های مرتبط، عضو کانال تلگرام ما بشید.

عضویت در کانال تلگرام
arrow_drop_up
کپی شد!