10/22 рекурсия

Замещение рекурсии стеком. Рекурсивная реализация алгоритма сортировки слиянием:

   1 def sjoin(s1, s2):
   2     res = []
   3     while s1 and s2:
   4         res.append(s1.pop() if s1[-1]>s2[-1] else s2.pop())
   5     return s1+s2+list(reversed(res))
   6 
   7 def jsort(seq):
   8     l = len(seq)
   9     if l<2:
  10         return list(seq)
  11     return sjoin(jsort(seq[l//2:]), jsort(seq[:l//2]))

Здесь для эффективности pop() и append() работают с концом списка, но полученный слиянием результат оказывается в обратном порядке, поэтому его надо перевернуть.

Д/З: стековая реализация алгоритма сортировки слиянием

Подсказка:

1. Избавимся в алгоритме от создания неименованных объектов, тупо поименовав их

   def jsort(seq):
       if len(seq)<2:
           res = seq
       else:
           s1 = jsort(seq[len(seq)//2:])
           s2 = jsort(seq[:len(seq)//2])
           res = sjoin(s1, s2)
       return res

2. Посмотрим, какие из имён должны пережить рекурсивный вызов jsort(). В данном случае это seq, s1. А s2 вычисляется после рекурсивного вызова, его хранить не надо. Кроме того, надо как-то возвращать res

   • ⇒ кадр стека (пространство имён) состоит из трёх ячеек
3. Рекурсивный вызов — это добавление очередного кадра в стек. Возврат из вызова — удаление кадра из стека. В рекурсивной записи это могут быть последовательные команды. В цикле, в который превращается рекурсия, всё это соответствует очередному обороту цикла. Так что в стеке нужно дополнительно хранить, в какую часть исходного рекурсивного кода мы выполняем:

   1. До вычисления s1

   2. После вычисления s1, но до собственно присваивания s1=

   3. До вычисления s2

   4. После вычисления s2, но до собственно присваивания s2= и вычисления res

   5. Собственно return

4. Это можно сделать, например, с помощью переменной, хранящей состояние. В примере мы просто запоминаем None вместо s1 и res на первых этапах, и подменяем их на результат вычисления на более поздних, и такм образом отличаем один от другого.

Вот пример решения:

   1 def jsorts(seq):
   2     stack = [[seq, None, None]]
   3     while stack[0][-1] is None:
   4         seq, s1, res = stack[-1]
   5         if len(seq)<2:          # res = seq
   6             seq, s1, res = stack[-1] = [seq, seq, seq]
   7         if s1 is None:          # jsort(seq[len(seq)//2:])
   8             stack.append([seq[len(seq)//2:], None, None])
   9             continue
  10         if res is None:         # jsort(seq[:len(seq)//2])
  11             stack.append([seq[:len(seq)//2], None, None])
  12             continue
  13         stack.pop()             # return res
  14         seq, s1, oldres = stack[-1]
  15         if s1 is None:          # s1 = ...
  16             stack[-1][1] = res
  17         else:                   # s2 = ... and other
  18             stack[-1][-1] = sjoin(s1, res)
  19     return stack[-1][-1]