Usage of Complex Recursion in Python

cmplxrecursion.py

"""
Complex Recursion

Normaly we are considiring the recursion as a factorial that corresponds to 
an example below:

"""

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')))

"""
No, the recursion may be presented through more complex formula :

f(x) = f(x-1) + f(x-2) + 1 , and the base case consists the following 
                             conditions: f(0) = 1 || f(1) = 1 

This recursive function will have be some solutions are contained next steps: 
"""
print ("===== f(x-1) + 1 =====")
nmax=5
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-1,'b') + 1

print ('Res: ' + str(cf(nmax,'r')))
"""
  Here is 5 counts that I were calculated by formula:
  f(x) = f(x-1) + 1                                   
                                                              
i:r0, x: 5  f(5)  = f(4) + 1 = 5
i:b4, x: 4  f(4)  = f(3) + 1 = 4
i:b3, x: 3  f(3)  = f(2) + 1 = 3
i:b2, x: 2  f(2)  = f(1) + 1 = 2 
i:b1, x: 1  f(1)  = 1
Res: 5

"""
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')))

"""
Here is 4 counts that I were calculated by formula:
  f(x) = 2*f(x-2) + 1       
  
i:r0, x: 7 f(7) = 2*f(5) + 1 = 15  
i:a2, x: 5 f(5) = 2*f(3) + 1 = 7
i:a4, x: 4 f(3) = 2*f(1) + 1 = 3
i:a6, x: 2 f(1) = 1
"""
print ("===== f(x-1) + 2*f(x-2) + 1 =====")
"""
    List xarrs contains a statistics of recursive calls :
    Item 0: a coordinate of recursive calls for functions fb(x) and fa(x)
    Item 1: a name of recursive call    
   
    coordinates and name functions fb(x) and fa(x) are using in next tree:

                              
                              f0(5): (0,0)
line 0:                            |
                --------------------------------------------
               |                                            |
          fb(4): (1,0)                                 fa(3)(0,1)		
line 1:        |                                            |
          ---------------------                       -------------        
         |                     |                     |             |
    fb(3):(2,0)           fa(2):(1,1)          fb(2):(1,1)   fa(1):(0,2)  
         |                     |                       |
line 2:  |                     |                       | 
      -----------            ------------          ---------------
     |           |           |           |        |               |        
fb(2):(3,0) fa(1):(2,1) fb(1):(2,1) fa(0):(1,2) fb(1):(2,1)   fa(0):(1,2) 
        |
line 3: |
   -------------  
  |             |
fb(1):(4,0)  fa(0):(3,1)

"""

nmax=5
xarrs=list()
def cf(x:int,t:str,bn:int,an:int, xarrs:list[[int,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"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 (f'Recursive calls table ({xarrs.__len__()}):')
xtable = sorted(xarrs, key = lambda x: x[0] )
i=0
while i < xtable.__len__() : 
    print (xtable[i])
    i += 1

"""
Then I'm forming address for each recursive point on this recursive call tree    

0A: f0(5):(0,0)   3C: fb(1):(2,1)
1A: fb(4):(1,0)   3D: fa(0):(1,2)
1B: fa(3):(0,1)   3E: fb(1):(2,1)
2A: fb(3):(2,0)   3F: fa(0):(1,2)
2B: fa(2):(1,1)   4A: fb(1):(4,0) 
2C: fb(2):(1,1)   4B: fa(0):(3,1)
2D: fa(1):(0,2)     
                  
3A: fb(2):(3,0)
3B: fa(1):(2,1)

Which has been mapped in dictionary and in some classes of statistics 
registration as show below
"""

print ("===== f(x-1) + 2*f(x-2) + 1 (with statics graph ) =====")
class _GraphNode() : 
      """ The common properties and methods to use nodeA, nodeB, and nodeR """
      _x:    int
      _vline: int
      _name: str
      _lbranch: object
      _rbranch: object
      _parent: object 
      _coords: tuple[int,int]

      def __init__(self,x,p) :
          self._parent = (lambda inst: None if not inst else inst )(p)
          self._lbranch = None # NodeB 
          self._rbranch = None # NodeA
          self._x = x
          self._name = f'f({x})' 	     
          self._coords = (0,0) 
          self._vline  = 0 

      def coordinates(self)->tuple[int,int] :
          """ return a coordinate of the node by prev node""" 
          return self._coords

      @property 
      def lbranch(self) :
           """ Get a node to the left branch for this node """ 
           return self._lbranch
      @lbranch.setter
      def lbranch(self,node) :
           """ Set new node to the left branch for this node """ 
           self._lbranch = node
  	    
      @property 
      def rbranch(self) :
           """ Get a node for the right branch for this node """ 
           return self._rbranch
      @lbranch.setter
      def rbranch(self,node) :
           """ Set new node to the right branch for this node """ 
           self._rbranch = node
   
      @property 
      def parent(self) :
            """ Get a parent node for this node""" 
            return self._parent

      @property 
      def name(self) :
           """ Get a name of parent node for this node""" 
           return self._name

      @name.setter
      def name(self,name) :
           """ Get a name of parent node for this node"""
           self._name = name
      
      @property 
      def vline(self) :
           """ Get a vertical position for this node""" 
           return self._vline

      @property 
      def X(self) :
           """ Get the value X for this node""" 
           return self._x


class NodeR(_GraphNode) :
      """
          The statistics of jumps for Root node is a start point of thie recursion 
      """
      def __init__(self,x,p) :
          super(NodeR, self).__init__(x,p )

class NodeA(_GraphNode) :
      """
          The statistics of jumps for node A is a right branching of 
          the recursive function
      """     
      def __init__(self,x,p) :
          super(NodeA, self).__init__(x,p) 
          if self._parent :
             self._vline = self.parent._vline + 1
             (b,a) = self.parent.coordinates()
             self._coords = (b,a+1)
                        
class NodeB(_GraphNode) :
      """
          The statistics of jumps for node B is a left branching of 
          the recursive function
      """     
      def __init__(self,x,p) :
          super(NodeB, self).__init__(x,p)
          if self._parent :          	
             self._vline = self._parent._vline + 1
             (b,a) = self._parent.coordinates()
             self._coords = (b+1,a)

address = [
           { "0-(0, 0)-Fr(5)" : "0A"  
                                      }, # line 0 
           { "1-(1, 0)-fb(4)" : "1A", 
             "1-(0, 1)-fa(3)" : "1B" 
                                      }, # line 1
           { "2-(2, 0)-fb(3)" : "2A", 
             "2-(1, 1)-fa(2)" : "2B", 
	     "2-(1, 1)-fb(2)" : "2C", 
             "2-(0, 2)-fa(1)" : "2D" 
                                      }, # line 2
           { "3-(3, 0)-fb(2)" : "3A", 
             "3-(2, 1)-fa(1)" : "3B", 
             "3-(2, 1)-fb(1)" : "3C", 
             "3-(1, 2)-fa(0)" : "3D", 
             "3-(2, 1)-fb(1)+" : "3E", 
             "3-(1, 2)-fa(0)+" : "3F"              
                                      }, # line 2
           { "4-(4, 0)-fb(1)" : "4A", 
             "4-(3, 1)-fa(0)" : "4B" 
                                      }, # line 2
]

def leaf(x,t,p) :
    """
        Appends leaf nodes and this function to be used in node_show() only!   
    """ 
    anode = None
    bnode = None
    if t == 'b' :
       bnode = NodeB(x,p)  # create a leaf node 
       coords=bnode.coordinates()
       vline=bnode.vline 	   
       bnode.name = f'{vline}-{coords}-fb({x})'
       if vline == 3 and coords == (2, 1) :
          paddr = bnode.parent.name
          if paddr == '2-(1, 1)-fb(2)' :
             bnode.name += f'+'
     
       return bnode
    if t == 'a' :
       anode = NodeA(x,p)  # create a leaf node 
       coords=anode.coordinates()
       vline=anode.vline 
       anode.name = f'{vline}-{coords}-fa({x})'
       if vline == 3 and coords == (1, 2) :
          paddr = anode.parent.name
          if paddr == '2-(1, 1)-fb(2)' :
             anode.name += f'+'
       return anode
    return None

def node_append(x,t,prnt) :    
    """
        Appends intermediate nodes A and B as show below
  
		    B(x+1)   A(x+2) <-- were already created                 
                         \   /          and those are a parent node   
                          (P)   
                           |
                          (C)
                  Left-->/   \<--Right 
                        /     \  
                     B(x-1)   A(x-2) <-- introduced nodes for the functions Fb() and Fa()
                                  
        Where, 
        (P) is a parent node 
	(A) is a node by name A
        (B) is a node'by name B
        (C) is a node into current postion and 
	    that node was created at prev iteration.   
    """
    bnode = None
    anode = None
    if not prnt :
       return (bnode,anode)

    isbasecase = lambda x : x == 1 or x == 0    
    if t == 'b' or  t == 'a' or t == 'r' :
        if t == 'r' : 
           coords=prnt.coordinates()
           vline=prnt.vline 	 
           prnt.name = f'{vline}-{coords}-Fr({x})' 	
           print ( 
                 'F({x}):[center] ', prnt.coordinates(),',', 
                  prnt.name, 'address: ', address[vline].get(prnt.name) )
    else : # but the line below are unlikely to execute, it seems to me  
       raise Exception('Sequence for moving from one node to another was broken!')
    
    bx = x-1
    if not isbasecase(bx) :  
       bnode = NodeB(bx,prnt) 
       coords=bnode.coordinates()
       vline=bnode.vline 
       bnode.name = f'{vline}-{coords}-fb({bx})'
    else:
       bnode = leaf(bx,'b',prnt)
	    
    ax = x-2
    if not isbasecase(ax) :
       anode = NodeA(ax,prnt) 
       coords=anode.coordinates()
       vline=anode.vline 
       anode.name = f'{vline}-{coords}-fa({ax})'
    else:
       anode = leaf(ax,'a',prnt) 
   
    prnt.lbranch = bnode    
    prnt.rbranch = anode

    return (bnode,anode) 

def cf(x:int,t:str,prnt:_GraphNode)->int:
    """
        the recursive function executes a code from the equation:
            F(X) = f(x-1) + 2*f(x-2) + 1  
        and it registrates statistics of jumps from/to a one node to another 
    """  
    node=None
    if x == 1 or x == 0 :
       return 1  
    (bnode,anode) = node_append(x,t,prnt) # create an intermediate node 
    if bnode : 
       coords=bnode.coordinates()	
       vline=bnode.vline 	  
       print ( 'B(x-1): [left ] ', bnode.coordinates(),',', 
                                   bnode.name,  
                                   'address: ', address[vline].get(bnode.name) )
    if anode :    
       coords=anode.coordinates()
       vline=anode.vline 	  
       print ( 'A(x-2): [right] ', anode.coordinates(), ',', anode.name, 'address: ', address[vline].get(anode.name)  ) 

    return cf(x-1,'b',bnode) + 2*cf(x-2,'a',anode) + 1

nmax=5
rnode = NodeR(nmax,None) # the line of this code to be run one time!   
print ('Res: ' + str(cf(nmax,'r',rnode)))

"""
Here is 15 counts that I were calculated by formula:
  f(x) = fb(x-1) + 2*fa(x-1) + 1
  
15. Address 0A: Fr(5) = fb(4) + 2*fa(3) + 1 = 16 + 2*7 + 1 = 16 + 14 + 1 = 31 	
      14. Address 1A: fb(4) = fb(3) + 2*fa(2) + 1 = 7 + 2*4 + 1 = 16 
                    13.Address 2A: fb(3) = fb(2) + 2*fa(1) + 1 = 4 + 2*1 + 1 = 7
                                   12.Address 3A: fb(2) = fb(1) + 2*fa(1) + 1 = 1 + 2*1 + 1 = 4 
			                          11.Address 4A: fb(1) = 1
                                                  10.Address 4B: fa(0) = 1 
  	                           09.Address 3B: fa(1) = 1
                    08.Address 2B: fa(2) = fb(1) + 2*fa(0) + 1 = 1 + 2 + 1 = 4   
                                   07.Address 3C: fb(1) = 1  
                                   06.Address 3D: fa(0) = 1 

      05. Address 1B: fa(3) = fb(2) + 2*fa(1) + 1 = 4 + 2*1 + 1 = 7
                    04.Address 2C: fb(2) = fb(1) + 2*fa(0) + 1 = 4       
				   02.Address 3E: fb(1) = 1   
                                   01.Address 3F: fa(0) = 1 
  	             03.Address 2D:fa(1) = 1  
"""