Как рекурсивно вычислить все пути к конечному состоянию в итерированной системе с двумя переменными состояния? ⇐ Python

[Anonymous]

Вычислите количество способов достижения конечного состояния (A = 1) с помощью рекурсии.
Рассмотрим итерированную систему с двумя переменными состояния A и B. .

• A может иметь значения 0 или 1
• B может иметь значение 0,1,2,3 или 4

Переменные инициализируются значениями (A,B) = (0,2). На каждой итерации одна из двух переменных состояния может перейти к одному соседнему разрешенному значению, т.е. для A 0 --> 1, 1 -->0. Для B значение 2 может перейти как 2-->1 или 2-->3.

Терминальное состояние достигается для A=1.
Сколько существует различных способов достичь конечного состояния после максимального количества итераций? Я должен написать метод, который рекурсивно вычисляет это число!
Пример (начальная позиция, начальная позиция B, текущий шаг, максимальный шаг) = (0,2,0,1) = 1
Вот моя попытка:

Код: Выделить всё

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

Но, как видно из этой таблицы, это не удается:



Входные данные
Ожидаемый результат
Фактический Вывод




(0,2,0,1)
1
1

(0,2,0,2)
2
3


(0,2,0,3)
4
7




Подробнее здесь: https://stackoverflow.com/questions/792 ... ted-system