[Python] How to recursively calculate all paths to a terminal state in an iterated system with...

Compute the number of ways to reach the terminal state (A = 1) using recursion.

Consider an iterated system with two state variables A and B.

• 
  A can have a values of 0 or 1
  
  
• 
  B can have a value of 0,1,2,3 ог 4
  

The variables are initialized to (A,B) = (0,2). At each iteration, one of the two state variables can transition to one adjacent allowed values, i.e. for A 0 --> 1, 1-->0. For B, a value of 2 can transition as 2-->1 or 2-->3.
A terminal state is reached for A=1.

How many different ways are there to reach the terminal state after maximum iterations? I am supposed to write a method that computes this number recursively!

Example (A initial position ,B initial position, Current Step, Maximum Step) = (0,2,0,1) = 1

Here's my try:

def recurse(A, B, step, max_step):
if A == 1:
return 1
if step > max_step:
return 0
ways = 0
if A == 0:
ways += recurse(1, B, step + 1, max_step)
if B > 0:
ways += recurse(A, B - 1, step + 1, max_step)
if B < 4:
ways += recurse(A, B + 1, step + 1, max_step)
return ways


But as can be seen in this table, it fails:

Input Expected Output Actual Output
(0,2,0,1) 1 1
(0,2,0,2) 2 3
(0,2,0,3) 4 7

Continue reading...