Вычисление суммы натуральных чисел от 1 до n

Если n==1, то сумма равна 1. Иначе сумма чисел от 1 до n равна сумме чисел от 1 до n−1, которую можно вычислить при помощи рекурсии плюс число n.

def sum(n):
if n == 1:
return 1
else:
return n + sum(n — 1)

ПРОВЕРКА СТРОКИ НА ПАЛИНДРОМНОСТЬ

Строка является палиндромом, если она одинаково читается как справа налево, так и слева направо. Напишем функцию IsPalindrome, которая возвращает значение типа bool в зависимости от того, является ли строка палиндромом.

Крайнее значение — пустая строка или строка из одного символа всегда палиндром. Рекурсивный переход — строка является палиндромом, если у нее совпадают первый и последний символ, а также строка, полученная удалением первого и последнего символа является палиндромом.

def IsPalindrome(S):
if len(S) <= 1:
return True
else:
return S[0] == S[-1] and IsPalindrome(S[1:-1])

СУММИРОВАНИЕ СПИСКА

Дан список чисел, необходимо просуммировать его.

Крайний случай — пустой список, сумма чисел в нем равна 0. Иначе нужно вычислить сумму чисел в срезе списка без одного элемента и добавить значение этого элемента.

def Sum(A):
if len(A) == 0:
return 0
else:
return Sum(A[:-1]) + A[-1]

НАИБОЛЬШЕЕ ЗНАЧЕНИЕ В СПИСКЕ

Дан список чисел, необходимо найти наибольшее значение в нем.

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

def Max(A):
if len(A) == 1:
return A[0]
else:
return max(Max(A[:-1]), A[-1])

ЧИСЛА ФИБОНАЧЧИ

Последовательность Фибоначчи задана так: F0=0, F1=1, при n>1 число Фибоначчи с номером nвычисляется как Fn=Fn−1+Fn−2. Для рекурсивного вычисления чисел Фибоначчи достаточно аккуратно запрограммировать эти соотношения:

def Fib(n):
if n <= 1:
return n
else:
return Fib(n — 1) + Fib(n — 2)

Рекурсивные функции являются мощным механизмом в программировании. К сожалению, они не всегда эффективны (об этом речь пойдет позже). Также часто использование рекурсии приводит к ошибкам, наиболее распространенная из таких ошибок – бесконечная рекурсия, когда цепочка вызовов функций никогда не завершается и продолжается, пока не кончится свободная память в компьютере. Пример бесконечной рекурсии приведен в эпиграфе к этому разделу. Две наиболее распространенные причины для бесконечной рекурсии:

1. Неправильное оформление выхода из рекурсии. Например, если мы в программе вычисления факториала забудем поставить проверку if n==0, то factorial(0) вызовет factorial(−1), тот вызовет factorial(−2) и т.д.

2. Рекурсивный вызов с неправильными параметрами. Например, если функция factorial(n) будет вызывать factorial(n), то также получиться бесконечная цепочка.

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

БЫСТРОЕ ВОЗВЕДЕНИЕ В СТЕПЕНЬ

Одним из полезных применений рекурсии является алгоритм быстрого возведения в степень. Если вычислять степень числа an при помощи простого цикла, то понадобится n−1 умножение. Но можно использовать рекуррентные соотношения:

an=an−1×a, при нечетном n

an=(an/2)2, при четном n.

Это позволяет записать алгоритм, который будет выполнять не более, чем 2∗log2n умножений:

def power(a, n):
if n == 0:
return 1
elif n % 2 == 1:
return power(a, n - 1) * a
else:
return power(a, n // 2) ** 2

ХАНОЙСКИЕ БАШНИ

Другой классической задачей, решаемой при помощи рекурсии, является задача о Ханойских башнях. Головоломка “Ханойские башни” состоит из трех стержней, пронумерованных числами 1, 2, 3. На стержень 1 надета пирамидка из n дисков различного диаметра в порядке возрастания диаметра. Диски можно перекладывать с одного стержня на другой строго по одному, при этом диск нельзя класть на диск меньшего диаметра. Необходимо переложить всю пирамидку со стержня 1 на стержень 3 <b>за минимальное число перекладываний</b>.

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

Сначала нужно подумать, как переложить пирамидку из n дисков с одного стержня на другой. Для этого нужно прежде всего перенести самый большой диск. Но чтобы перенести этот диск нужно всю пирамидку без этого диска, то есть пирамидку из n−1 диска перенести на третий стержень, затем перенести один самый большой диск, затем перенести пирамидку из n−1 диска на тот стержень, на который переместили самый большой диск.

Напишем рекурсивную функцию move(n, start, finish), которая печатает последовательность перекладываний, необходимых для перемещения пирамидки из n дисков со стержня номер start на стержень номер finish. Простой случай — n==1, в этом случае рекурсия не нужна и нужно просто переместить один диск.

def move(n, start, finish):
if n == 1:
print("Перенести диск 1 со стержня", start, "на стержень", finish)
else:
temp = 6 — start — finish # Вспомогательный колышек
move(n — 1, start, temp)
print("Перенести диск", n, "со стержня", start, "на стержень", finish)
move(n — 1, temp, finish)
# Для решения головоломки из 10 дисков вызываем так:
move(10, 1, 3)

Решение можно сделать проще, если понять, что крайний случай — это случай n==0, в этом случае для перемещения пирамидки из 0 дисков… просто ничего не нужно делать!

def move(n, start, finish):
if n > 0:
temp = 6 — start — finish # Вспомогательный колышек
move(n — 1, start, temp)
print("Перенести диск", n, "со стержня", start, "на стержень", finish)
move(n — 1, temp, finish)