Рекуррентные соотношения

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

Например, сумма двух натуральных чисел в математике определена так (в терминах примитивных операций «ноль» \(0\) и «инкремент» \(S\)):

\[ \begin{aligned} a + 0 & = a \\ a + s(n) & = s(a + n) \end{aligned} \]

Естественно, в программировании (которое является разделом математики, находящемся на стыке дискретной математики и абстрактной алгебры) тоже многие объекты и алгоритмы определяются именно в терминах рекуррентных соотношений.

Цифры числа

Приведём простой пример: цифры натурального числа можно получить следующим образом (без использования встроенной функции str)

def digits(n):
  if n == 0: return '0'
  if n == 1: return '1'
  if n == 2: return '2'
  if n == 3: return '3'
  if n == 4: return '4'
  if n == 5: return '5'
  if n == 6: return '6'
  if n == 7: return '7'
  if n == 8: return '8'
  if n == 9: return '9'
  return digits(n//10) + digits(n%10)

Здесь по сути написано, что цифры числа \(n\) — это (в случае, если оно больше 9) цифры его неполного частного при делении на 10, за которыми следует последняя цифра, полностью определяемая остатком числа по модулю 10.

Аналогично можно получить, например, двоичные цифры:

def bin_digits(n):
  if n == 0: return '0'
  if n == 1: return '1'
  return bin_digits(n//2) + bin_digits(n%2)

Конечно, то же самое можно получить и при помощи цикла:

def bin_digits(n):
  if n == 0: return '0'

  result = ''

  while n > 0:
    if n % 2 == 0: digit = '0'
    else:          digit = '1'

    result = digit + result
    n = n // 10

  return result

Но рекуррентное соотношение в данном случае выглядит гораздо проще. Единственная тонкость — для каждого рекуррентного соотношения требуется доказательство (по индукции) того, что оно вообще когда-либо завершает работу. Впрочем, цикл while в этом плане не сильно лучше.

Унарная запись числа

Для разнообразия приведём пример рекуррентной функции, которая не имеет результата работы, а интересна только своим побочным эффектом.

def print_unary(n):
  if n == 0: print()
  else: print('|', end=''); print_unary(n-1)

Последовательность

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

def print_reversed_sequence():
  n = int(input())

  if n == 0: return

  print_reversed_sequence()
  print(n)

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

Упражнения

Во всех этих упражнениях запрещается использовать циклы while и for.

  1. Напишите функцию, печатающую троичную запись натурального числа.

  2. Напишите функцию print_reciprocal_digits(n,k), печатающую k цифр после запятой числа, обратного целому положительному n.

  3. Напишите функцию print_square(n), печатающую квадратик \(n\times n\). Запрещается использовать умножение текста на число.

  4. Напишите функцию C(n,k), печатающую соответствующий биномиальный коэффициент.