общее решение (рекурсивное веселье c)

Question

У меня есть эта рекурсивная функция, которая ищет возможные решения проблемы подъема по лестнице. Можно ли вернуть окончательный счет без глобальной переменной?

def foo(number, steps):
    global count
    if steps == number:
        count += 1
    else:
        if number - 2 >= steps:
            foo(number, steps+2)
        if number -1 >= steps:
            foo(number, steps+1)
    return count

Answer 1

В общем, идея в этих типах рекурсивных алгоритмов состоит в том, чтобы использовать возвращаемое значение из рекурсивных вызовов в текущем вызове.

В данном конкретном случае: число способов добраться до вершины с текущей позиции, это сумма способов, которые начинаются с одного шага, и способов, которые начинаются с двойного шага.

Мы также можем упростить логи c путем добавления дополнительных базовых случаев для ситуации, когда мы перешагнули цель, и сообщения об отсутствии решений в этом случае. Это означает, что нам не нужна отдельная проверка перед каждым рекурсивным вызовом, а также обрабатываются случаи, когда нас просили начать за пределами цели.

Наконец, нам не нужно отдельное отслеживание количество предпринятых шагов и общее расстояние до цели: все, что нас волнует, это оставшееся расстояние .

Итак:

def number_of_paths(distance):
    if distance < 0:
        # We overstepped the goal, so now we can't get there.
        return 0
    elif distance == 0:
        # We're there, so there's exactly one way to get there: wait in place.
        return 1
    else:
        # We try both possible step sizes and total the results.
        return number_of_paths(distance - 2) + number_of_paths(distance - 1)