Как написать рекурсивную функцию python

Рекурсию не очень просто понять при первом знакомстве, но без ее понимания в разработке будет тяжело. В этом материале рассмотрим:

• Рекурсивную функцию поиска факториала.
• Как рекурсивные функции работают в коде.
• Действительно ли рекурсивные функции выполняют свои задачи лучше итеративных?

Рекурсивные функции

Рекурсивная функция — это та, которая вызывает сама себя.

В качестве простейшего примера рассмотрите следующий код:

def factorial_recursive(n):

    if n == 1:

        return n

    else:

        return n*factorial_recursive(n-1)

Вызывая рекурсивную функцию здесь и передавая ей целое число, вы получаете факториал этого числа (n!).

Вкратце о факториалах

Факториал числа — это число, умноженное на каждое предыдущее число вплоть до 1.

Например, факториал числа 7:
7! = 7*6*5*4*3*2*1 = 5040

Вывести факториал числа можно с помощью функции:

num = 3

print(f"Факториал {num} это {factorial_recursive(num)}")

Эта функция выведет: «Факториал 3 это 6». Еще раз рассмотрим эту рекурсивную функцию:

def factorial_recursive(n):

    ...

По аналогии с обычной функцией имя рекурсивной указывается после def, а в скобках обозначается параметр n:

def factorial_recursive(n):
    if n == 1:
        return n
    else:
        return n*factorial_recursive(n-1)

Благодаря условной конструкции переменная n вернется только в том случае, если ее значение будет равно 1. Это еще называют условием завершения. Рекурсия останавливается в момент удовлетворения условиям.

def factorial_recursive(n):
    if n == 1:
        return n
    else:
        return n*factorial_recursive(n-1)

В коде выше выделен фрагмент самой рекурсии. В блоке else условной конструкции возвращается произведение n и значения этой же функции с параметром n-1.

Это и есть рекурсия. В нашем примере это так сработало:

3 * (3-1) * ((3-1)-1)  # так как 3-1-1 равно 1, рекурсия остановилась

Детали работы рекурсивной функции

Чтобы еще лучше понять, как это работает, разобьем на этапы процесс выполнения функции с параметром 3.

Для этого ниже представим каждый экземпляр с реальными числами. Это поможет «отследить», что происходит при вызове одной функции со значением 3 в качестве аргумента:

# Первый вызов

factorial_recursive(3):

    if 3 == 1:

        return 3

    else:

        return 3*factorial_recursive(3-1)


# Второй вызов

factorial_recursive(2):

    if 2 == 1:

        return 2

    else:

        return 2*factorial_recursive(2-1)



  


                       
  





# Третий вызов

factorial_recursive(1):

    if 1 == 1:

        return 1

    else:

        return 1*factorial_recursive(1-1)

Рекурсивная функция не знает ответа для выражения 3*factorial_recursive(3–1), поэтому она добавляет в стек еще один вызов.

Как работает рекурсия

/ factorial_recursive(1) - последний вызов
|| factorial_recursive(2) - второй вызов
|| factorial_recursive(3) - первый вызов

Выше показывается, как генерируется стек. Это происходит благодаря процессу LIFO (last in, first out, «последним пришел — первым ушел»). Как вы помните, первые вызовы функции не знают ответа, поэтому они добавляются в стек.

Но как только в стек добавляется вызов factorial_recursive(1), для которого ответ имеется, стек начинает «разворачиваться» в обратном порядке, выполняя все вычисления с реальными значениями. В процессе каждый из слоев выпадает в процессе.

• factorial_recursive(1) завершается, отправляет 1 в
• factorial_recursive(2) и выпадает из стека.
• factorial_recursive(2) завершается, отправляет 2*1 в
• factorial_recursive(3) и выпадает из стека. Наконец, инструкция else здесь завершается, возвращается 3 * 2 = 6, и из стека выпадает последний слой.

Рекурсия в Python имеет ограничение в 3000 слоев.

>>> import sys

>>> sys.getrecursionlimit()

3000

Рекурсивно или итеративно?

Каковы же преимущества рекурсивных функций? Можно ли с помощью итеративных получить тот же результат? Когда лучше использовать одни, а когда — другие?

Важно учитывать временную и пространственную сложности. Рекурсивные функции занимают больше места в памяти по сравнению с итеративными из-за постоянного добавления новых слоев в стек в памяти. Однако их производительность куда выше.

Рекурсия может быть медленной, если реализована неправильно

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

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

def factorial_iterative(num):

    factorial = 1

    if num < 0:

        print("Факториал не вычисляется для отрицательных чисел")

    else:

        for i in range (1, num + 1):

            factorial = factorial*i

        print(f"Факториал {num} это {factorial}")

Рассмотрим задачу получения факториала числа. В математике он обозначается «!» и функция факториала описывается так:

1. 0! = 1.
2. n! = 1 * 2 * … * n, n > 0.

Напишем функцию, вычисляющую факториал числа n.

def fact(n):
    factorial = 1
    for i in range(2, n + 1):
        factorial *= i
    return factorial


print(fact(5))

Давайте немного перепишем определение факториала:

1. 0! = 1.
2. n! = (1 * 2 * … * (n — 1)) *n = (n — 1)! * n

Мы видим, что для вычисления n! нам нужно найти (n - 1)! и умножить результат на n. Таким образом, мы используем функцию для вычисления нового значения функции. Функции, в которых происходит вызов самих этих функций называют рекурсивными.

Давайте напишем рекурсивную функцию для вычисления факториала. При создании рекурсивных функций необходимо:

1. Написать, что вернёт функция при начальном значении аргумента.
2. Написать правило получения нового значения на основе уже вычисленных на предыдущих шагах.

def fact(n):
    if n == 0:  # 0! = 1
        return 1
    return fact(n - 1) * n  # n! = (n - 1)! * n


print(fact(5))

Вывод программы:

120

Обратите внимание, что рекурсивный вариант функции выполняет действия, которые описаны правилом вычисления факториала. Такой стиль программирования называется декларативным. Данный подход описывает сам результат. Функции, которые мы писали ранее, основаны на императивном стиле, и отвечают на вопрос о способе получения результата.

Рассмотрим применение рекурсивной функции для вычисления n-го числа последовательности Фибоначчи. Числа Фибоначчи — последовательность чисел, вычисляемых по следующему правилу:

1. Первые два числа последовательности равны 1.
2. n-ое число Фибоначчи равно сумме двух предыдущих, то есть fib(n) = fib(n — 1) + fib(n — 2).

Программа с рекурсивной функцией вычисления n-го числа Фибоначчи запишется так:

def fib(n):
    if n in (0, 1):
        return 1
    return fib(n - 1) + fib(n - 2)


print(fib(35))

Вывод программы:

14930352

При запуске программы, можно заметить, что вычисление 35-го числа последовательности происходит с небольшой задержкой. Проверим, сколько времени занимают вычисления. Выполним вычисления 10 раз и выведем среднее время вычисления с точностью 1 мс. В тестировании скорости работы кода нам помогает стандартный модуль timeit.

from timeit import timeit


def fib(n):
    if n in (0, 1):
        return 1
    return fib(n - 1) + fib(n - 2)


print(f"Среднее время вычисления: "
      f"{round(timeit('fib(35)', number=10, globals=globals()) / 10, 3)} с.")

Вывод программы:

Среднее время вычисления: 2.924 с.

Проверим, сколько времени займут те же вычисления у императивной версии функции.

from timeit import timeit


def fib(n):
    f_1, f = 1, 1
    for i in range(n - 1):
        f_1, f = f, f_1 + f
    return f


print(f"Среднее время вычисления: "
      f"{round(timeit('fib(35)', number=10, globals=globals()) / 10, 3)} с.")

Вывод программы:

Среднее время вычисления: 2e-06 с.

Получили результат 2 микросекунды у императивной функции против почти 3 секунд у рекурсивной. В чём же причина?

Проблема рекурсивной функции заключается в том, что внутри неё происходит два вызова самой себя для каждого значения. И так до тех пор, пока не функция не дойдет до начальных значений аргументов (1 и 1). В итоге появляется несколько рекурсивных веток, которые образуют рекурсивное дерево. Покажем его часть на рисунке.

Числа на схеме показывают номер числа Фибоначчи. Цветом показаны числа с одинаковым номером. Из схемы дерева становится понятно, что рекурсивная реализация функции выполняет много одинаковых вычислений. Давайте добавим счётчик количества вызовов нашей рекурсивной функции:

def fib(n):
    global count
    count += 1
    if n in (0, 1):
        return 1
    return fib(n - 1) + fib(n - 2)


count = 0
print(f"35-ое число Фибоначчи равно: {fib(35)}.")
print(f"Количество вызовов рекурсивной функции равно: {count}.")

Вывод программы:

35-ое число Фибоначчи равно: 14930352.
Количество вызовов рекурсивной функции равно: 29860703.

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

Напишем рекурсивную функцию с кэшированием, использовав для сохранения вычисленных значений словарь, в котором ключами будут номера чисел последовательности, а значения — сами числа.

def fib(n):
    global count
    count += 1
    if n not in cash:
        cash[n] = fib(n - 1) + fib(n - 2)
    return cash[n]


count = 0
cash = {0: 1, 1: 1}
print(f"35-ое число Фибоначчи равно: {fib(35)}.")
print(f"Количество вызовов рекурсивной функции равно: {count}.")

Вывод программы:

35-ое число Фибоначчи равно: 14930352.
Количество вызовов рекурсивной функции равно: 69.

За счет кэширования количество вызовов рекурсивной функции существенно сократилось. Проверим скорость работы нашей функции.

from timeit import timeit


def fib(n):
    global count
    count += 1
    if n not in cash:
        cash[n] = fib(n - 1) + fib(n - 2)
    return cash[n]


count = 0
cash = {0: 1, 1: 1}
print(f"Среднее время вычисления: "
      f"{round(timeit('fib(35)', number=10, globals=globals()) / 10, 6)} с.")

Вывод программы:

Среднее время вычисления: 2e-06 с.

Скорость работы также существенно увеличилась. Попробуем вычислить число Фибоначчи с номером 1000:

from timeit import timeit


def fib(n):
    if n not in cash:
        cash[n] = fib(n - 1) + fib(n - 2)
    return cash[n]


cash = {0: 1, 1: 1}
print(f"Среднее время вычисления: "
      f"{round(timeit('fib(1000)', number=10, globals=globals()) / 10, 6)} с.")

Вывод программы:

RecursionError: maximum recursion depth exceeded

Программа выдала ошибку по превышению глубины рекурсии. В Python по умолчанию максимальный размер глубины рекурсии равен 1000. Для изменения глубины рекурсии для вашей программы нужно вызвать функцию setrecursionlimit() из стандартного модуля sys и передать новое значение для предела глубины.

from timeit import timeit
from sys import setrecursionlimit


def fib(n):
    if n not in cash:
        cash[n] = fib(n - 1) + fib(n - 2)
    return cash[n]


setrecursionlimit(2000)
cash = {0: 1, 1: 1}
print(f"Среднее время вычисления: "
      f"{round(timeit('fib(1000)', number=10, globals=globals()) / 10, 6)} с.")

Вывод программы:

Среднее время вычисления: 0.000132 с.

Обратите внимание: максимально возможное значение глубины рекурсии зависит от операционной системы. Поэтому бесконечно его увеличивать не получится.

Итак, наша рекурсивная функция с кэшированием стала работать быстро. Однако есть и недостаток: её код стал читаться сложнее. Поручим процесс запоминания промежуточных значений функции интерпретатору. Для этого в Python в стандартном модуле functools есть функция lru_cache. Её следует использовать так, как показано в следующем примере:

from timeit import timeit
from functools import lru_cache


@lru_cache(maxsize=1000)
def fib(n):
    if n in (0, 1):
        return 1
    return fib(n - 1) + fib(n - 2)

    
print(f"Среднее время вычисления: "
      f"{round(timeit('fib(35)', number=10, globals=globals()) / 10, 6)} с.")

Вывод программы:

Среднее время вычисления: 2e-06 с.

Благодаря автоматическому кэшированию, наша функция снова приобрела «декларативный» вид и при этом работает быстро.

Ещё по теме

Функция lru_cache в примере используется как декоратор. Подробнее о них можно почитать в этом материале

If you’re familiar with functions in Python, then you know that it’s quite common for one function to call another. In Python, it’s also possible for a function to call itself! A function that calls itself is said to be recursive, and the technique of employing a recursive function is called recursion.

It may seem peculiar for a function to call itself, but many types of programming problems are best expressed recursively. When you bump up against such a problem, recursion is an indispensable tool for you to have in your toolkit.

By the end of this tutorial, you’ll understand:

• What it means for a function to call itself recursively
• How the design of Python functions supports recursion
• What factors to consider when choosing whether or not to solve a problem recursively
• How to implement a recursive function in Python

Then you’ll study several Python programming problems that use recursion and contrast the recursive solution with a comparable non-recursive one.

def function():
    x = 10
    function()

>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

>>> def countdown(n):
...     print(n)
...     if n == 0:
...         return             # Terminate recursion
...     else:
...         countdown(n - 1)   # Recursive call
...

>>> countdown(5)
5
4
3
2
1
0

def countdown(n):
    print(n)
    if n > 0:
        countdown(n - 1)

>>> def countdown(n):
...     while n >= 0:
...         print(n)
...         n -= 1
...

>>> countdown(5)
5
4
3
2
1
0

>>> def factorial(n):
...     return 1 if n <= 1 else n * factorial(n - 1)
...

>>> factorial(4)
24

>>> def factorial(n):
...     print(f"factorial() called with n = {n}")
...     return_value = 1 if n <= 1 else n * factorial(n -1)
...     print(f"-> factorial({n}) returns {return_value}")
...     return return_value
...

>>> factorial(4)
factorial() called with n = 4
factorial() called with n = 3
factorial() called with n = 2
factorial() called with n = 1
-> factorial(1) returns 1
-> factorial(2) returns 2
-> factorial(3) returns 6
-> factorial(4) returns 24
24

>>> def factorial(n):
...     return_value = 1
...     for i in range(2, n + 1):
...         return_value *= i
...     return return_value
...

>>> factorial(4)
24

>>> from functools import reduce
>>> def factorial(n):
...     return reduce(lambda x, y: x * y, range(1, n + 1) or [1])
...

>>> factorial(4)
24

timeit(<command>, setup=<setup_string>, number=<iterations>)

>>> from timeit import timeit

>>> timeit("print(string)", setup="string='foobar'", number=100)
foobar
foobar
foobar
   .
   . [100 repetitions]
   .
foobar
0.03347089999988384

>>> setup_string = """
... print("Recursive:")
... def factorial(n):
...     return 1 if n <= 1 else n * factorial(n - 1)
... """

>>> from timeit import timeit
>>> timeit("factorial(4)", setup=setup_string, number=10000000)
Recursive:
4.957105500000125

>>> setup_string = """
... print("Iterative:")
... def factorial(n):
...     return_value = 1
...     for i in range(2, n + 1):
...         return_value *= i
...     return return_value
... """

>>> from timeit import timeit
>>> timeit("factorial(4)", setup=setup_string, number=10000000)
Iterative:
3.733752099999947

>>> setup_string = """
... from functools import reduce
... print("reduce():")
... def factorial(n):
...     return reduce(lambda x, y: x * y, range(1, n + 1) or [1])
... """

>>> from timeit import timeit
>>> timeit("factorial(4)", setup=setup_string, number=10000000)
reduce():
8.101526299999932

>>> from math import factorial
>>> factorial(4)
24

>>> setup_string = "from math import factorial"

>>> from timeit import timeit
>>> timeit("factorial(4)", setup=setup_string, number=10000000)
0.3724050999999946

names = [
    "Adam",
    [
        "Bob",
        [
            "Chet",
            "Cat",
        ],
        "Barb",
        "Bert"
    ],
    "Alex",
    [
        "Bea",
        "Bill"
    ],
    "Ann"
]

>>> for index, item in enumerate(names):
...     print(index, item)
...
0 Adam
1 ['Bob', ['Chet', 'Cat'], 'Barb', 'Bert']
2 Alex
3 ['Bea', 'Bill']
4 Ann

>>> names
['Adam', ['Bob', ['Chet', 'Cat'], 'Barb', 'Bert'], 'Alex', ['Bea', 'Bill'], 'Ann']

>>> names[0]
'Adam'
>>> isinstance(names[0], list)
False

>>> names[1]
['Bob', ['Chet', 'Cat'], 'Barb', 'Bert']
>>> isinstance(names[1], list)
True

>>> names[1][1]
['Chet', 'Cat']
>>> isinstance(names[1][1], list)
True

>>> names[1][1][0]
'Chet'
>>> isinstance(names[1][1][0], list)
False

def count_leaf_items(item_list):
    """Recursively counts and returns the
       number of leaf items in a (potentially
       nested) list.
    """
    count = 0
    for item in item_list:
        if isinstance(item, list):
            count += count_leaf_items(item)
        else:
            count += 1

    return count

>>> count_leaf_items([1, 2, 3, 4])
4
>>> count_leaf_items([1, [2.1, 2.2], 3])
4
>>> count_leaf_items([])
0

>>> count_leaf_items(names)
10
>>> # Success!

 1def count_leaf_items(item_list):
 2    """Recursively counts and returns the
 3       number of leaf items in a (potentially
 4       nested) list.
 5    """
 6    print(f"List: {item_list}")
 7    count = 0
 8    for item in item_list:
 9        if isinstance(item, list):
10            print("Encountered sublist")
11            count += count_leaf_items(item)
12        else:
13            print(f"Counted leaf item "{item}"")
14            count += 1
15
16    print(f"-> Returning count {count}")
17    return count

>>> count_leaf_items(names)
List: ['Adam', ['Bob', ['Chet', 'Cat'], 'Barb', 'Bert'], 'Alex', ['Bea', 'Bill'], 'Ann']
Counted leaf item "Adam"
Encountered sublist
List: ['Bob', ['Chet', 'Cat'], 'Barb', 'Bert']
Counted leaf item "Bob"
Encountered sublist
List: ['Chet', 'Cat']
Counted leaf item "Chet"
Counted leaf item "Cat"
-> Returning count 2
Counted leaf item "Barb"
Counted leaf item "Bert"
-> Returning count 5
Counted leaf item "Alex"
Encountered sublist
List: ['Bea', 'Bill']
Counted leaf item "Bea"
Counted leaf item "Bill"
-> Returning count 2
Counted leaf item "Ann"
-> Returning count 10
10

def count_leaf_items(item_list):
    """Non-recursively counts and returns the
       number of leaf items in a (potentially
       nested) list.
    """
    count = 0
    stack = []
    current_list = item_list
    i = 0

    while True:
        if i == len(current_list):
            if current_list == item_list:
                return count
            else:
                current_list, i = stack.pop()
                i += 1
                continue

        if isinstance(current_list[i], list):
            stack.append([current_list, i])
            current_list = current_list[i]
            i = 0
        else:
            count += 1
            i += 1

>>> count_leaf_items([1, 2, 3, 4])
4
>>> count_leaf_items([1, [2.1, 2.2], 3])
4
>>> count_leaf_items([])
0

>>> count_leaf_items(names)
10
>>> # Success!

>>> def is_palindrome(word):
...     """Return True if word is a palindrome, False if not."""
...     return word == word[::-1]
...

>>> is_palindrome("foo")
False
>>> is_palindrome("racecar")
True
>>> is_palindrome("troglodyte")
False
>>> is_palindrome("civic")
True

>>> def is_palindrome(word):
...     """Return True if word is a palindrome, False if not."""
...     if len(word) <= 1:
...         return True
...     else:
...         return word[0] == word[-1] and is_palindrome(word[1:-1])
...

>>> # Base cases
>>> is_palindrome("")
True
>>> is_palindrome("a")
True

>>> # Recursive cases
>>> is_palindrome("foo")
False
>>> is_palindrome("racecar")
True
>>> is_palindrome("troglodyte")
False
>>> is_palindrome("civic")
True

 1import statistics
 2
 3def quicksort(numbers):
 4    if len(numbers) <= 1:
 5        return numbers
 6    else:
 7        pivot = statistics.median(
 8            [
 9                numbers[0],
10                numbers[len(numbers) // 2],
11                numbers[-1]
12            ]
13        )
14        items_less, pivot_items, items_greater = (
15            [n for n in numbers if n < pivot],
16            [n for n in numbers if n == pivot],
17            [n for n in numbers if n > pivot]
18        )
19
20        return (
21            quicksort(items_less) +
22            pivot_items +
23            quicksort(items_greater)
24        )

>>> # Base cases
>>> quicksort([])
[]
>>> quicksort([42])
[42]

>>> # Recursive cases
>>> quicksort([5, 2, 6, 3])
[2, 3, 5, 6]
>>> quicksort([10, -3, 21, 6, -8])
[-8, -3, 6, 10, 21]

import random

def get_random_numbers(length, minimum=1, maximum=100):
    numbers = []
    for _ in range(length):
        numbers.append(random.randint(minimum, maximum))

    return numbers

>>> numbers = get_random_numbers(20)
>>> numbers
[24, 4, 67, 71, 84, 63, 100, 94, 53, 64, 19, 89, 48, 7, 31, 3, 32, 76, 91, 78]
>>> quicksort(numbers)
[3, 4, 7, 19, 24, 31, 32, 48, 53, 63, 64, 67, 71, 76, 78, 84, 89, 91, 94, 100]

>>> numbers = get_random_numbers(15, -50, 50)
>>> numbers
[-2, 14, 48, 42, -48, 38, 44, -25, 14, -14, 41, -30, -35, 36, -5]
>>> quicksort(numbers)
[-48, -35, -30, -25, -14, -5, -2, 14, 14, 36, 38, 41, 42, 44, 48]

>>> quicksort(get_random_numbers(10, maximum=500))
[49, 94, 99, 124, 235, 287, 292, 333, 455, 464]
>>> quicksort(get_random_numbers(10, 1000, 2000))
[1038, 1321, 1530, 1630, 1835, 1873, 1900, 1931, 1936, 1943]

Когда функция вызывает сама себя, она называется рекурсивной функцией. В этом руководстве мы узнаем, как написать функцию рекурсии Python.

Когда функция определена таким образом, что она вызывает сама себя, она называется рекурсивной функцией. Это явление называется рекурсией. Python поддерживает рекурсивные функции.

Рекурсия очень похожа на цикл, в котором функция вызывается на каждой итерации. Вот почему мы всегда можем использовать циклы как замену функции рекурсии Python.

Но некоторые программисты предпочитают рекурсию циклам. В основном это вопрос выбора, и вы можете использовать циклы или рекурсию.

Примеры

Следующий код возвращает сумму первых n натуральных чисел, используя рекурсивную функцию python.

def sum_n(n):
    if n== 0:
        return 0
    else:
        return n + sum_n(n-1)

Это печатает сумму первых 100 натуральных чисел и первых 500 натуральных чисел

print(sum_n(100))
print(sum_n(500))

Вывод

C:/Users/TutorialsPoint1/~.py
5050
125250

1. Факториал целого числа

Факториал целого числа вычисляется путем умножения целых чисел от 1 до этого числа. Например, факториал 10 будет 1 * 2 * 3…. * 10.

Давайте посмотрим, как мы можем написать факториальную функцию с помощью цикла for.

def factorial(n):
    result = 1

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

    return result


print(f'Factorial of 10 = {factorial(10)}')
print(f'Factorial of 5 = {factorial(5)}')

Давайте посмотрим, как мы можем изменить функцию factorial() для использования рекурсии.

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n - 1)


print(f'Factorial of 10 = {factorial(10)}')
print(f'Factorial of 5 = {factorial(5)}')

На изображении ниже показано выполнение рекурсивной функции.

2. Ряд Фибоначчи

Ряд Фибоначчи — это последовательность чисел, каждое из которых представляет собой сумму двух предыдущих чисел. Например — 1, 1, 2, 3, 5, 8, 13, 21 и так далее.

Давайте посмотрим на функцию для возврата чисел ряда Фибоначчи с помощью циклов.

def fibonacci(n):
    """ Returns Fibonacci Number at nth position using loop"""
    if n == 0:
        return 0
    if n == 1:
        return 1
    i1 = 0
    i2 = 1
    num = 1
    for x in range(1, n):
        num = i1 + i2
        i1 = i2
        i2 = num
    return num


for i in range(10):
    print(fibonacci(i), end=" ")

# Output: 0 1 1 2 3 5 8 13 21 34 

Вот реализация функции fibonacci() с использованием рекурсии.

def fibonacci(n):
    """ Returns Fibonacci Number at nth position using recursion"""
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)


for i in range(10):
    print(fibonacci(i), end=" ")

# Output: 0 1 1 2 3 5 8 13 21 34 

Здесь рекурсивный код функции меньше и прост для понимания. Так что использование рекурсии в этом случае имеет смысл.

Базовый случай

При определении рекурсивной функции должен быть хотя бы один базовый случай, для которого нам известен результат. Затем каждый последующий вызов рекурсивной функции должен приближать ее к базовому случаю.

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

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

Преимущества

• Иногда рекурсия уменьшает количество строк кода.
• Код выглядит просто.
• Если мы знаем базовый случай, тогда использовать в функции проще.

Недостатки

• Если не реализовано должным образом, функция никогда не завершится.
• Понимание рекурсии вызывает большую путаницу по сравнению с циклами.

Recursion in Python works just as recursion in an other language, with the recursive construct defined in terms of itself:

For example a recursive class could be a binary tree (or any tree):

class tree():
    def __init__(self):
        '''Initialise the tree'''
        self.Data = None
        self.Count = 0
        self.LeftSubtree = None
        self.RightSubtree = None

    def Insert(self, data):
        '''Add an item of data to the tree'''
        if self.Data == None:
            self.Data = data
            self.Count += 1
        elif data < self.Data:
            if self.LeftSubtree == None:
                # tree is a recurive class definition
                self.LeftSubtree = tree()
            # Insert is a recursive function
            self.LeftSubtree.Insert(data)
        elif data == self.Data:
            self.Count += 1
        elif data > self.Data:
            if self.RightSubtree == None:
                self.RightSubtree = tree()
            self.RightSubtree.Insert(data)

if __name__ == '__main__':
    T = tree()
    # The root node
    T.Insert('b')
    # Will be put into the left subtree
    T.Insert('a')
    # Will be put into the right subtree
    T.Insert('c')

As already mentioned a recursive structure must have a termination condition. In this class, it is not so obvious because it only recurses if new elements are added, and only does it a single time extra.

Also worth noting, python by default has a limit to the depth of recursion available, to avoid absorbing all of the computer’s memory. On my computer this is 1000. I don’t know if this changes depending on hardware, etc. To see yours :

import sys
sys.getrecursionlimit()

and to set it :

import sys #(if you haven't already)
sys.setrecursionlimit()

edit: I can’t guarentee that my binary tree is the most efficient design ever. If anyone can improve it, I’d be happy to hear how