Решение модуля 7.8 Инди-курс программирования на Python

Модуль 7.8 (Рекурсия в Python. Рекурсивная функция Часть 1). Рекурсия – определение, описание, изображение какого-либо объекта или процесса внутри самого этого объекта или процесса, то есть ситуация, когда объект является частью самого себя.

Что произойдет, если в рекурсивной функции не будет условия выхода?

RecursionError: maximum recursion

RecursionError: maximum recursion

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

Определите функцию print_from, которая принимает одно натуральное число n и распечатывает на экране убывающую последовательность целых чисел от n до 1 включительно. Каждое число необходимо выводить на отдельной строке. 

Ваша задача только написать определение функции print_from

def print_from(n: int) -> None:
    print(n)     # выводим первое число
    if n > 1:    # если число больше 1, вызываем саму функцию, но число уменьшаем на 1
        print_from(n - 1)

def print_from(n: int) -> None:
print(n) #выводим первое число
if n > 1: #если число больше 1, вызываем саму функцию, но число уменьшаем на 1
print_from(n — 1)

def print_to(n: int) -> None:
    if n > 0:             # если заданное число больше нуля
        print_to(n - 1)   # вызываем функцию но переданную 
        print(n)          # выводим числа от 1 до заданного числа

Дано натуральное число N и последовательность из N элементов. Требуется вывести эту последовательность в обратном порядке.

def rev(n):      # объявляем функцию
    if n > 0:    # условие выхода из рекурсии. Пока n > 0 буем выполнять все что ниже в ветке if 
        rev(n-1) # рекурсивный вызов функцию rev(n-1). Когда мы в коде натыкаемся на эту строчку ev(n-1) выполнение программы прерывается и в стек сохраняется исходный аргумент {n}, а сам рекурсивный вызов функции происходи при (n-1) и так по кругу пока не достигнем нуля (n = 0). В этот момент рекурсивный вызов прерывается (так как сработало условие if) и исполнение кода наконец-то переходит к строке print.
        print(sp[-n], end=" ") # выводим данную последовательность

N = int(input()) # получаем натуральное число N
sp = list(map(int, input().split())) #и получаем последовательность из N элементов. Сразу создаем список
rev(N)           # Вызываем функцию 

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

double_fact(7) => 105
double_fact(4) => 8
double_fact(1) => 1
double_fact(10) => 3840

Ваша задача только написать определение функции double_fact

def double_fact(n):             # объявляем функцию
    if n == 1:                  # условие выхода из рекурсии при n =1
        return 1                # возвращаем 1
    if n == 2:                  # еще одно условие выхода из рекурсии при n =2
        return 2                # возвращаем 2
    f = n * double_fact(n - 2)  # рекурсивный вызов функцию double_fact(n - 2)
    return f                    # возвращение результата вычисления

Последовательностью Фибоначчи называется последовательность чисел a₀, a₁, …, a_n, …, где число, стоящее на n-ой позиции можно вычислить по формуле:

Требуется найти N-е число Фибоначчи.

def fib(n):
    if n==0:                 # если порядковый номер(введенный) равен 0, то возвращаем ноль
        return 0
    if n==1:                 # если  порядковый номер(введенный) равен 1, выводим 1
        return 1
    return fib(n-1) + fib(n-2) # иначе вызываем сумму функций с числом уменьшенным на 1 и числом уменьшенным на 2

print(fib(int(input ())))    # вызываем функцию

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

Вот примере вызовов:

tribonacci(0) => 0
tribonacci(2) => 1
tribonacci(4) => 2
tribonacci(6) => 7
tribonacci(7) => > 13

Ваша задача только написать определение функции tribonacci

def tribonacci(n):  # объявляем функцию, принимающую порядковый номер нужного числа из ряда Трибоначчи 
    if n==0:        # если задали 0 - возвращаем 0, т.к. первое(с индексом 0) число в ряду - 0 
        return 0
    if n==1:        # если задали 1 - возвращаем 0, т.к. второе(с индексом 1) число в ряду - 0
        return 0
    if n==2:        # если задали 2 - возвращаем 1, т.к. третье(с индексом 2) число в ряду - 1
        return 1
    return tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3)  # иначе если задали число больше 2, возвращаем сумму функций с уменьшенным числом на 1, на 2, на 3

Описать рекурсивную функцию get_combin, которая принимает на вход два целых числа  и находит C(N,K) — число сочетаний из N элементов по K — с помощью рекуррентного соотношения:

При этом гарантируется, что входные значения n и k будут удовлетворять следующим условиям:

• n > 0
• 0 ≤ k ≤ n

Вот примеры вызовов:

get_combin(5, 5) => 1
get_combin(5, 2) => 10
get_combin(3, 1) => 3
get_combin(7, 0) => 1

Ваша задача только написать определение функции get_combin

def get_combin(n: int, k:int) -> int:  # объявляем функцию которая принимает 2 числа
    if k == 0 or n == 0: # если какое то из заданных чисел  равно 0 - возвращаем 1
        return 1
    if k == n:           # если 2 числа равны - возвращаем 1
        return 1
    return get_combin(n-1, k) + get_combin(n-1, k-1) # иначе возвращаем сумму результатов выполнения функций с уменьшенным первым числом на 1, и с функцией, у которого уменьшены оба числа на 1

Описать рекурсивную функцию ackermann, которая принимает на вход два целых числа  m и n находит значение, определенное следующим образом:

Найденное значение функция ackermann должна вернуть в качестве результата

ackermann(3, 2) => 29
ackermann(3, 0) => 5
ackermann(1, 0) => 2
ackermann(3, 5) => 253

Ваша задача только написать определение функции ackermann

В тестовых примерах сперва поступает на вход значение аргумента m, затем аргумента n.

def ackermann(m: int, n: int) -> int: # объявляем функцию которая принимает 2 числа
    if m == 0:             # если первое число равно 0, то возвращаем второе число увеличенное на 1
        return n + 1
    if m > 0 and n == 0:   # если первое число положительное и второе число равно 0, вызываем функцию с уменьшенным на 1 первым числом
        return ackermann(m - 1, 1)
    return ackermann(m - 1, ackermann(m, n - 1))  # иначе вызываем функцию с уменьшенным на 1 первое число и в качестве второго числа вызываем функцию с уменьшенным вторым числом на 1

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

Ваша задача только написать определение функции list_sum_recursive

def list_sum_recursive(a: list) -> int:     # объявляем функцию, которая принимает список чисел
    if len(a) == 0:     # если длина переданного списка равно 0, то и сумма будет равна нулю
        return 0
    if len(a) == 1:     # если длина переданного списка равна 1, то и сумма будет равна этому одному числу
        return a[0]
    return a[0] + list_sum_recursive(a[1:]) # иначе сумма первого числа и функции в которую передаётся список уже без первого числа (которая вызывает ещё 1 функцию, и так складываются все числа)

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

flatten([1, [2, 3, [4]], 5]) => [1, 2, 3, 4, 5]
flatten([1, [2, 3], [[2], 5], 6]) => [1, 2, 3, 2, 5, 6]
flatten([[[[9]]], [1, 2], [[8]]]) => [9, 1, 2, 8]

Ваша задача только написать определение функции flatten

def flatten(sp: list) -> list: # объявляем функцию, которая принимает вложенный список
    new = []               # создаем пустой список, для создавания линейного списка
    for i in sp:           # проходимся по введенному списку
        if type(i) is int: # если тип элемента число, то добавляем в новый список это число
            new.append(i)
        else:              # иначе если это ещё 1 список, то  для него вызываем функцию, которая добавить числа из него в новый список
            new += flatten(i)
    return new             # возвращаем полученный список