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

В этом уроке мы будем применять рекурсию к последовательности Фибоначчи, которая представляет собой ряд чисел, где число является сложением двух последних чисел, т.е. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 и т.д. Последовательность начинается с 0, и поэтому n-е число является суммой (n-1)-го и (n-2)-го чисел.

Рекурсивные представления в SmartPy

В SmartPy рекурсия реализуется путем разрешения функции вызывать саму себя внутри своего собственного определения. Этот метод чрезвычайно полезен при работе с проблемами, которые можно разбить на более мелкие, идентичные подпроблемы. Рекурсивное представление в SmartPy - это, по сути, представление, использующее рекурсию. Представление - это функция SmartPy, которая не изменяет хранилище контрактов, но может читать из него. Когда мы говорим о рекурсивном представлении, мы имеем в виду функцию представления, которая вызывает сама себя во время своего выполнения.

Последовательность Фибоначчи

Последовательность Фибоначчи - это набор чисел, в котором каждое число является суммой двух предыдущих, начиная с 0 и 1. Эта последовательность, несмотря на свою простоту, служит прекрасной основой для понимания рекурсии благодаря своей рекурсивной природе.

Последовательность Фибоначчи определяется рекуррентным соотношением:

SCSS
F(n) = F(n-1) + F(n-2)

При этом начальными условиями являются F(0) = 0 и F(1) = 1. Это означает, что для получения n-гочисла в последовательности Фибоначчи мы складываем(n-1)-е и(n-2)-е числа. Эта рекурсивная природа как раз и делает последовательность Фибоначчи идеальным инструментом для понимания рекурсии. Теперь, когда мы лучше понимаем, что такое рекурсия и как она применяется к последовательности Фибоначчи, давайте погрузимся в код SmartPy, который реализует рекурсивное представление для вычисления последовательности Фибоначчи.

Проводник по коду

Приведенный код SmartPy определяет контракт, FibonacciView, который вычисляет последовательность Фибоначчи, используя рекурсивное представление. Это отличный пример для понимания того, как создаются и используются рекурсивные функции в SmartPy.

Python
import smartpy as sp


@sp.module
def main():
 class FibonacciView(sp.Contract):
      """Контракт с рекурсивным представлением для вычисления суммы чисел Фибоначчи."""

        @sp.onchain_view()
 def fibonacci(self, n):
          """Возвращает сумму чисел Фибоначчи до n.

            Args:
 n (sp.int): количество чисел Фибоначчи для суммирования.
            Return:
 (sp.int): сумма чисел Фибоначчи
 " " " 
 sp.cast(n, int)
 if n < 2:
 return n
 else:
 n1 = sp.view("fibonacci", sp.self_address(), n - 1, int).unwrap_some()
 n2 = sp.view("fibonacci", sp.self_address(), n - 2, int).unwrap_some()
                return n1 + n2


if "templates" not in __name__:

   @sp.add_test(name="Базовый сценарий FibonacciView", is_default=True)
 def basic_scenario():
 sc = sp.test_scenario(main)
        sc.h1("Базовый сценарий.")
        sc.h2("Origination.")
        c1 = main.FibonacciView()
 sc += c1
 sc.verify(c1.fibonacci(8) == 21)

Этот контракт FibonacciView имеет рекурсивную функцию представления, fibonacci, которая возвращает n-ое число Фибоначчи.

Функция украшена @sp.onchain_view(), указывая на то, что это операция над хранилищем контракта, предназначенная только для чтения. Эта функция принимает в качестве аргумента целое число n, представляющее позицию в последовательности Фибоначчи, которую мы хотим извлечь.

Внутри функции мы сначала приводим n к целому числу для безопасности. Далее идет рекурсивная часть функции. Если n меньше 2, мы просто возвращаем n, поскольку первые два числа последовательности Фибоначчи - это 0 и 1. Если n больше или равно 2, мы вычисляем n-ое число Фибоначчи, рекурсивно вызывая функцию fibonacci для n-1 и n-2, а затем складывая результаты. Это соответствует рекуррентному соотношению, определяющему последовательность Фибоначчи. Вызовы sp.view создают эти рекурсивные обращения к самой функции fibonacci.

Использование цикла для повышения эффективности
Хотя рекурсия является ценной концепцией для понимания, важно отметить, что она может быть менее эффективной и требовать больше вычислительных ресурсов, особенно при работе с большими числами. Чтобы избежать проблем, подобных переполнению стека, более эффективным подходом было бы использование цикла для вычисления последовательности Фибоначчи и хранение вычисленных чисел Фибоначчи в отдельном контракте.
Вот пример высокого уровня того, как Вы можете модифицировать контракт FibonacciView для использования цикла:
Этот модифицированный контракт, FibonacciCalculator, использует цикл для эффективного вычисления чисел Фибоначчи и сохраняет их в хранилище контракта. Затем Вы можете вызвать точку входа calculate_fibonacci для получения n-го числа Фибоначчи.
Этот подход более ресурсоэффективен и подходит для больших значений n.

Python
@sp.moduledef main():
 class FibonacciCalculator(sp.Contract):
      """Контракт для эффективного вычисления последовательности Фибоначчи."" " def __init__(self):
 self.init(storage=sp.map(tkey=sp.TInt, tvalue=sp.TInt).set(0, 0).set(1, 1))

       @sp.entry_pointdef calculate_fibonacci(self, n):
 sp.verify(n >= 0, message="n должно быть неотрицательным")
 storage = self.data
 for i in range(2, n + 1):
 next_fib = storage[i - 1] + storage[i - 2]
 storage = storage.set(i, next_fib)
 sp.result(storage[n])

Давайте продолжим раздел тестирования.

В тестовой функции basic_scenario мы создаем новый экземпляр контракта FibonacciView, добавляем его в наш сценарий, а затем используем sc.verify для проверки того, что 8-е число Фибоначчи равно 21, что является истинным для последовательности Фибоначчи.

Выполнение кода в SmartPy IDE

Чтобы выполнить код:

1. Откройте среду разработки SmartPy IDE.

2. Скопируйте и вставьте предоставленный код в редактор.

3. Щелкните на кнопке "Выполнить". В правой части IDE Вы должны увидеть выполняющийся тестовый сценарий. Вы увидите выполняемые операции и проверяемые чеки.
   В этом уроке было рассмотрено много вопросов. Мы прошли путь от основ рекурсии и ее использования в программировании до рекурсивных представлений в SmartPy и даже применили эти понятия к последовательности Фибоначчи. Мы также изучили пример рабочего кода на SmartPy, и Вы узнали, как запустить и проверить этот код в SmartPy IDE.