Урок Python 41: Рекурсия. Рекурсивная функция Часть 1 | Уроки по программированию | Дзен

• Рекурсия - это ситуация, когда функция вызывает саму себя.  

• Пример: функция "рек" вызывает себя с тем же аргументом.  

• В Python есть ограничения на глубину рекурсии.  

• Программа с рекурсией может вызвать ошибку из-за ограничений.  

• Пример: функция "рек" вызывает себя до 1000 раз, затем возникает ошибка.  

• Важно иметь условие для выхода из рекурсии.  

• Условие выхода: если число меньше 4, вызываем рекурсию, иначе выходим.  

• Пример: функция "рек" печатает число и вызывает себя, если оно меньше 4.  

• При достижении 4 происходит выход из рекурсии.  

• Стек вызовов хранит информацию о том, какая функция вызывала другую.  

• Пример: функция "рек-4" вызывает "рек-3", которая вызывает "рек-2", которая вызывает "рек-1".  

• При завершении функции "рек-4" возвращается к "рек-3".  

• Пример: нахождение факториала с помощью рекурсии.  

• Факториал n включает в себя факториал n-1, умноженный на n.  

• Рекурсия позволяет свести большую задачу к более мелким подзадачам.  

• Функция "факт" проверяет, равен ли аргумент 1, и возвращает 1.  

• В противном случае вызывает себя с аргументом на единицу меньше.  

• Пример: факториал 4 равен 24, так как 4! = 3! * 4.  

• Пример: нахождение чисел Фибоначчи с помощью рекурсии.  

• Числа Фибоначчи растут по формуле: F1 = 1, F2 = 1, F3 = F2 + F1.  

• Рекурсия позволяет решать задачи, сводя их к более мелким подзадачам.  

• Числа Фибоначчи начинаются с нуля и единицы.  

• Каждое следующее число получается сложением двух предыдущих.  

• Ряд чисел Фибоначчи бесконечен и имеет порядковые номера.  

• Для нахождения числа Фибоначчи с порядковым номером n, нужно сложить предыдущее число с числом на два номера меньше.  

• Формула: n-е число Фибоначчи равно нулю для n=1, единице для n=2, и сумме двух предыдущих чисел для всех остальных n.  

• Функция фип принимает порядковый номер числа Фибоначчи и возвращает его значение.  

• Для n=1 и n=2 возвращаем ноль и единицу соответственно.  

• Для всех остальных n рекурсивно вызываем функцию с параметром на единицу меньше и складываем с функцией с параметром на два меньше.  

• Пример вызова функции для нахождения пятого числа Фибоначчи.  

• Функция вызывает себя рекурсивно, складывая предыдущие значения.  

• Важно понимать, что вызовы происходят не одновременно, а последовательно.  

• При расчете чисел Фибоначчи повторяются вызовы, что замедляет работу программы.  

• Для больших чисел Фибоначчи программа работает медленно.  

• Существуют более эффективные способы работы с числами Фибоначчи.  

• Палиндром — это строка, читаемая одинаково слева направо и справа налево.  

• Рекурсия используется для проверки, является ли строка палиндромом.  

• Если первый и последний символы совпадают, строка считается палиндромом.  

• Функция палиндром принимает строку и проверяет, совпадает ли первый и последний символы.  

• Если символы совпадают, строка рекурсивно проверяется для оставшейся части.  

• Если символы не совпадают, возвращается false.  

• Проверка строки "шалаш" показывает, что она является палиндромом.  

• Проверка строки с одной буквой показывает, что она также является палиндромом.  

• Проверка пустой строки и строки из двух одинаковых букв также показывает, что они являются палиндромами.  

• Тема рекурсии сложна для понимания, поэтому будет продолжение с дополнительными примерами.  

• Цель — закрепить идеи рекурсии