1 Сумма чисел от 1 до n

Если бы я хотел , чтобы узнать сумму чисел от 1 до n , где n натуральное число, я могу сделать 1 + 2 + 3 + 4 + ... + (several hours later) + n . В качестве альтернативы, я мог бы написать for цикла:

 n = 0
for i in range (1, n+1):
    n += i

 

Или я мог бы использовать технику, известную как рекурсия:

 def recursion(n):
    if n == 1:
        return 1
    return n + recursion(n - 1)

 

Рекурсия имеет преимущества перед двумя вышеупомянутыми методами. Рекурсии занимает меньше времени , чем выписывание 1 + 2 + 3 на сумму от 1 до 3. Для recursion(4) , рекурсии может быть использован для работы в обратном направлении:

Вызовы функций: (4 -> 4 + 3 -> 4 + 3 + 2 -> 4 + 3 + 2 + 1 -> 10)

В то время как for цикла работает строго вперед: (1 -> 1 + 2 -> 1 + 2 + 3 -> 1 + 2 + 3 + 4 -> 10). Иногда рекурсивное решение проще, чем итеративное решение. Это очевидно при реализации обращения связанного списка.