Дата и время публикации:    2020-03-16 10:30:00

Проблема и решение

1. Суть проблемы

Обычно, рекурсию принято рассматривать на примере факториала, который описывается формулой (1) [3.1]

(1) $n! = 1 \times 2 \times 3 \times...\times n\times(n-1)!$

Ее запись выглядит последовательностью выполнения операций умножения $n \times (n-1)!$, где $n = 1$ является базовым случаем или ограничением числа рекурсивных вызовов, как показано в листинге 1.1

Листинг 1.1

print ("===== n! =====")
nmax=5
def sf(n:int,t:str)->int:
      if  n == 1 :
          print( 'o:'+t+str(int(nmax-n))+', x: '+str(n))
          return 1
      print( 'item:'+t+str(int(nmax-n))+', n: '+str(n))
      return n* sf(n-1,'a') 

print ('Res: ' + str(sf(nmax,'r')))
...

Как следует из листинга 1.1, она заключается в рекурсивном вызове функции $n \times f(n-1)$ и умножения возвращаемого значения согласно формулы (1), что подтверждает дамп 1.2, в котором выполняется код из листинга 1.1

Дамп 1.2

===== n! =====
item:r0, n: 5
item:a1, n: 4
item:a2, n: 3
item:a3, n: 2
o:a4, x: 1
Res: 120
...

Что объяснимо, когда, согласно листингу 1.1, значение $n-1$ достигнет базового случая и станет равным 1 будет решена формула (1)

2. Решение

Давайте представим, что есть более сложная формула (2)

(2) $f(x) = f(x-1) + 2 \times f(x-2) + 1$ , где $f(0) = 0 || f(1) = 1$,

которую решал последовательно: сначала, упростил до рекурсивной формулы (3)

(2) $f(x) = f(x-2) + 1$

Её реализация на Python показана в листинге 2.1

Листинг 2.1

...
print ("===== f(x-2) + 1 =====")
nmax=8
def cf(x:int,t:str)->int:
      if  x == 1 or x == 0 :
          print( 'o:'+t+str(int(nmax-x))+', x: '+str(x))
          return 1
      print( 'i:'+t+str(int(nmax-x))+', x: '+str(x))
      return cf(x-2,'a') + 1

print ('Res: ' + str(cf(nmax,'r')))
...

В результате, будет последовательно высчитана рекурсивно формула (3) :

x: 8  f(8) = f(6) + 1 = 5
x: 6  f(6) = f(4) + 1 = 4
x: 4  f(4) = f(2) + 1 = 3
x: 2  f(2) = f(0) + 1 = 2 
x: 0  f(0) = 1

Теперь усложним формулу (3) и добавим множитель 2, как показано в формуле (4)

которую воплотил в Python, как показано в листинге 2.2

Листинг 2.2

...
print ("===== 2*f(x-2) + 1 =====")
nmax=7
def cf(x:int,t:str)->int:
      if  x == 1 or x == 0 :
          print( 'o:'+t+str(int(nmax-x))+', x: '+str(x))
          return 1
      print( 'i:'+t+str(int(nmax-x))+', x: '+str(x))
      return 2*cf(x-2,'a') + 1

print ('Res: ' + str(cf(nmax,'r')))
...

Соответственно, получил следующие итерации вызова рекурсивной формулы (4):

f(7) = 2*f(5) + 1 = 15  
f(5) = 2*f(3) + 1 = 7
f(3) = 2*f(1) + 1 = 3
f(1) = 1  

В конце, добавил f(x-1) к формуле (4), тем самым привел ее к изначальному виду, который соответстыует формуле (2) и формуле (5), последняя имеет более приземленный вид для отслеживания всех переходов в дереве рекурсивных вызовов:

(5) $fb(x-1) + 2 \times fa(x-2) + 1$ , где $fb(0) == 1$, $fa(0) == 1$ и $fb(1) == 1$, $fa(1) == 1$

Она показывает наличие ветвления рекурсивной функции вправо — $fb(x) и влево из формулы (2) и упрошает реализацию в Python, как показано в листинге 2.3

Листинг 2.3

...
print ("===== f(x-1) + 2*f(x-2) + 1 =====")
nmax=5
def cf(x:int)->int:
      if  x == 1 or x == 0 :
          return 1
      return cf(x-1) + 2*cf(x-2) + 1

print (cf(nmax,'r'))
...

В результате было получен число, равное 31, что является правильным решением, которое можно объяснить, если изготовить синтетический код, как показано в листинге 2.4

Листинг 2.4

print ("===== f(x-1) + 2*f(x-2) + 1 =====")
nmax=5
xarrs=list()
def cf(x:int,t:str,bn:int,an:int, xarrs:listint,int],str])->int:
      if t == 'a' : 
         an += 1
      if t == 'b' : 
         bn += 1
      if t == 'r' :
         an = 0 
         bn = 0
      xs=(lambda x,t: x+2 if t == 'a' else ( x+1  if t == 'b' else x))(x,t)
      svalue=f"{t}({xs}) => f({x})" 
      xarrs.append(bn,an],svalue])
      if  x == 1 or x == 0 :
          return 1
      return cf(x-1,'b',bn,an,xarrs) + 2*cf(x-2,'a',bn,an,xarrs) + 1

print ('Res: ' + str(cf(nmax,'r', 0,0,xarrs)))
print ('Recursive calls table:')
xtable = xarrs
i=0
while i < xtable.__len__() : 
    print (xtable[i])
    i += 1

Он будет регистрировать, в моем случае на процессоре AMD Ryzen 7 3750H, следующие несовсем внятные результаты, показанные в дампе 2.5

Листинг 2.5

...
===== f(x-1) + 2*f(x-2) + 1 =====
Res: 31
Recursive calls table:
[[0, 0], 'fr(5) => f(5)']
[[0, 1], 'fa(5) => f(3)']
[[0, 2], 'fa(3) => f(1)']
[[1, 0], 'fb(5) => f(4)']
[[1, 1], 'fa(4) => f(2)']
[[1, 1], 'fb(3) => f(2)']
[[1, 2], 'fa(2) => f(0)']
[[1, 2], 'fa(2) => f(0)']
[[2, 0], 'fb(4) => f(3)']
[[2, 1], 'fa(3) => f(1)']
[[2, 1], 'fb(2) => f(1)']
[[2, 1], 'fb(2) => f(1)']
[[3, 0], 'fb(3) => f(2)']
[[3, 1], 'fa(2) => f(0)']
[[4, 0], 'fb(2) => f(1)']

Поэтому, когда просортировал таблицу по первому элементу [3.6], как показано в листинге 2.6

Листинг 2.6

...
===== f(x-1) + 2*f(x-2) + 1 =====
Res: 31
Recursive calls table:
[[0, 0], 'r(5) => f(5)']
[[1, 0], 'b(5) => f(4)']
[[2, 0], 'b(4) => f(3)']
[[3, 0], 'b(3) => f(2)']
[[4, 0], 'b(2) => f(1)']
[[3, 1], 'a(2) => f(0)']
[[2, 1], 'a(3) => f(1)']
[[1, 1], 'a(4) => f(2)']
[[2, 1], 'b(2) => f(1)']
[[1, 2], 'a(2) => f(0)']
[[0, 1], 'a(5) => f(3)']
[[1, 1], 'b(3) => f(2)']
[[2, 1], 'b(2) => f(1)']
[[1, 2], 'a(2) => f(0)']
[[0, 2], 'a(3) => f(1)']

В результате получил следующие решения рекурсивной функции (2), как показано на схеме 2.7, которая содержит переход рекурсии от узла к узлу, прикинутые на пальцах.

Рисунок 2.7

Показанные выше переходы от одного узла к другому формируют следующую таблицу последовательности рекурсивных вызовов, одновременно служащей таблицей истинности всех состояния числа x (=5) для рекурсивно вызываемых $fa()$ и $fb()$, как показано в таблице 2.8

Затем, решил задачу на Python получения выше представленной таблицы 2.8 и показанного на рисунке 2.7 графа истинности всех состояний числа X для рекурсивно вызываемых $fa()$ и $fb()$. Код на Python можно скачать с моей странички в gist.github.com, после выполнения которого смог произвести расчеты, подтверждающие получение числа 31, как показано на рисунке 2.10

Рисунок 2.10

Таким образом, сколько бы не было бы членов у рекурсивной функции, порождающие дополнительно вложенные рекурсивные вызовы, и какая бы она не была сложной, все расчеты для выбранной рекурсивной функции следует производит, снизу вверх с точки, которая называется базовым случаем, как наглядно показывает алгоритм на рисунке 2.10 и приведенные выше расчеты для формул (3) и (4).

3. Библиография

3.1 RapidTables.com — Factorial (n!)

3.2 Tree Traversal in Python Using Recursion (With Code)

3.3 Recursive Formula

3.4 Python | Sort a list according to the second element in sublist