Блог

У меня есть следующий код для рекурсивного поиска ^n:

 def power(x, y):
  if y == 0: 
      return 1
  a = f(x*x, y//2) 
  if y % 2 == 1:
    a = x*a
  return a
  

Как я могу математически доказать, что это всегда работает?

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