Przekształcanie algorytmów rekurencyjnych w iteracyjne (recursive to iterative algorithm transformation)

recursive_to_iterative.rb

#
#          Przekształcanie algorytmów rekurencyjnych w iteracyjne
#                 na przykładzie znanych i kochanych algorytmów:
#                                BinarySearch i QuickSort ;)
#
#


# ======================== Binary Search Algorithm =================================
module Recursive
  def Recursive.binary_search(arr, x, l=0, r=arr.length-1) # 1) definicja zmiennych określających stan/kontekst wykonania algorytmu
    if l>=r # 2) warunek stopu
      return r if arr[r] == x
      return :not_found
    end

    mid = (l + (r-l)/2).floor
    if x > arr[mid]
      binary_search(arr, x, mid + 1, r) # 3a) wywołanie rekurencyjne z nowymi zmiennymi stanu
    else
      binary_search(arr, x, l, mid)     # 3b) wywołanie rekurencyjne z nowymi zmiennymi stanu
    end  
  end
end

# Kiedy jest tylko jedno wywołanie rekurencyjne na poziom rekurencji (tzn. funkcja wywołuje się tylko raz)
# to porzebny jest tylko jeden zestaw zmiennych określających stan/kontekst wykonania algorymu. Można więc
# zdefiniować ten zestaw zmiennych na początku i potem tylko zmieniać ich wartości, aż do momentu gdy zajdzie
# warunek stopu.
module Iterative 
  def Iterative.binary_search(arr,x)
    # 1) definicja zmiennych określających stan
    l = 0
    r = arr.length-1

    while !(l>=r) # 2) warunek stopu
      mid = (l + (r-l)/2).floor
      if x > arr[mid]
        l = mid + 1 # 3a) zmiana zmiennych stanu i przejście do kolejnej iteracji pętli
      else
        r = mid     # 3a) zmiana zmiennych stanu i przejście do kolejnej iteracji pętli
      end  
    end

    return r if arr[r] == x
     return :not_found
  end
end


puts "BinarySearch:"
a = [-24, -18, -13, -11, -7, -6, -5, -4, -3, -2, -1, 0, 3, 4, 5, 7, 9, 12, 13, 14, 17, 19]
i = rand(a.length-1)
x = a[i]
puts i
puts Recursive.binary_search(a,x)
puts Iterative.binary_search(a,x)



# ========================= Quick Sort Algorithm ==================================

# partition jest identyczne dla wersji rekurencyjnej i iteracyjnej QuickSort'a
module Common
  def Common.partition(arr,lo,hi,pivot) 
    while lo <= hi
      lo += 1 while arr[lo] < pivot
      hi -= 1 while arr[hi] > pivot
      if lo <= hi
        arr[lo], arr[hi] = arr[hi], arr[lo]
        lo += 1
        hi -= 1
      end
    end
    return lo, hi
  end
end

module Recursive
  def Recursive.qsort(arr, first=0, last=arr.length-1) # definicja zmiennych stanu dla aktualnego wywołania
      pivot = arr[(first+last)/2]
      lo, hi = Common.partition(arr,first,last,pivot)

      qsort(arr, first, hi  ) if first < hi # wywołanie rekurencyjne nr. 1 z nowymi zmiennymi stanu
      qsort(arr, lo,    last) if last  > lo # wywołanie rekurencyjne nr. 2 z nowymi zmiennymi stanu

      return arr
  end
end

# W sytuacji w której jest więcej niż jedno wywołanie rekruncyjne algorytm musi pamiętać stan w momęcie
# pierwszego wywołania rekurencyjnego by móc wykonać drugie. Potrzeba więc pamięciać więcej niż jeden
# zestaw zmiennych stanu na raz. W przypadku QuckSort trzeba mieć w pamięci zmienne stanu dla pierwszego
# wywołania rekurencyjnego by je wykonać iteracyjnie ale trzeba też zapisać na potem zestaw zmiennych stanu
# dla drugiego wywołania rekurencyjnego (lub na odwrót ;) ale i tak trzeba pamiętać więcej niż jeden zestaw
# zmiennych stanu na raz). Potrzeba więc struktury danych która będzie przechowywała zestawy zmiennych stanu.
# W przypadku 'iteryzacji' algorytmów rekurencyjnych na myśl od razu przychodzi stos. Stos jest tworzony na
# początku i w każdym momencie wykonania algorymu zawiera zestawy zmiennych stanu dla których musi zostać
# jeszcze wykonana pętla. Warunkiem stopu jest więc pusty stos.
module Iterative 
  def Iterative.qsort(arr)
    stack = [0, arr.length - 1] # definicja i initalizacja stosu 'pierwszym' zestawem zmiennych stanu
    
    until stack.empty? # czy są jeszcze jakieś zmienne stanu z którymi ma być wykonana pętla
      # definicja zestawu zmiennych stanu dla aktualnej iteracji (zdjęcie ze stosu - w odwrotnej kolejności niż włożenie!)
      last  = stack.pop
      first = stack.pop
      
      pivot = arr[(first+last)/2]
      lo, hi = Common.partition(arr,first,last,pivot)
      
      # włożenie na stos zmiennych stanu z którymi ma być uruchomiona pętla 'w przyszłości'
      stack << first << hi   if first < hi
      stack << lo    << last if last  > lo
    end
    
    return arr
  end
end

puts"\nQuickSort:"
arr = ((1..30).inject([]) {|a,n| a << rand(8*n)-3*n}).sort
p arr
arr.shuffle!
p Recursive.qsort(arr)
a.shuffle!
p Iterative.qsort(arr)