Искате ли да научите всичко за рекурсията в програмирането? Този урок за рекурсия в Python ще ви помогне да започнете.
Рекурсията е супер полезна техника за решаване на проблеми, която да добавите към инструментариума на вашия програмист. Въпреки че първоначално често е трудно да се разберете, рекурсията може да ви помогне да измислите по-елегантни решения на сложни проблеми.
В този урок ще използваме подход на първо място с код за изучаване на рекурсия с помощта на Python. По-специално ще разгледаме:
- Основите на рекурсията
- Рекурсивни функции и как работят
- Реализация на рекурсивни функции в Python
- Разлики между итеративни и рекурсивни подходи за решаване на проблеми
Да започваме!
Съдържание
Какво е рекурсия?
Рекурсията е техника за програмиране, при която функция се извиква многократно, за да разреши проблем.
В основата си рекурсията е подход за решаване на проблеми, който включва разбиване на сложен проблем на по-малки, идентични подпроблеми. По същество той ви позволява да разрешите проблем от гледна точка на по-прости версии на себе си.
И така, как да внедрим рекурсия в код? За да направите това, нека разберем как работят рекурсивните функции.
Разбиране на рекурсивните функции
Ние дефинираме рекурсивна функция, която се самоизвиква в своята дефиниция. Всяко рекурсивно повикване представлява по-малка или по-проста версия на първоначалния проблем.
За да се гарантира, че рекурсията в крайна сметка прекратява, рекурсивните функции трябва да включват един или повече базови случаи – условия, при които функцията спира да се самоизвиква и връща резултат.
Нека разбием това по-нататък. Рекурсивната функция се състои от:
- Базов случай: Базовият случай е условие (или условия), които определят кога рекурсията трябва да спре. Когато базовият случай е изпълнен, функцията връща резултат, без да прави допълнителни рекурсивни извиквания. Основният случай е от съществено значение за предотвратяване на безкрайна рекурсия.
- Рекурсивен случай: Рекурсивният случай дефинира как да разбиете проблема на по-малки подпроблеми. В тази част на функцията функцията се извиква сама с модифицирани входове. Следователно всяко рекурсивно повикване е стъпка към достигане на основния случай.
След това нека обсъдим какво се случва, когато извикате рекурсивна функция.
Как работи рекурсията под капака
Когато се извика функция, запис на нейния контекст на изпълнение се поставя в стека за извикване. Този запис включва информация за аргументите на функцията, локалните променливи и местоположението, което да се върне, след като функцията завърши изпълнението.
В случай на рекурсивни функции, когато функция извиква сама себе си, нов запис се избутва в стека за извикване, ефективно спирайки изпълнението на текущата функция. Стекът позволява на Python да следи всички чакащи извиквания на функции, включително тези от рекурсивни повиквания.
Докато се достигне базовият случай, рекурсията продължава. Когато основният случай върне резултат, извикванията на функцията се разрешават едно по едно, като всяка функция връща своя резултат на предишното ниво на стека на извикванията. Този процес продължава, докато първоначалното извикване на функция завърши.
Внедряване на рекурсия в Python
В този раздел ще разгледаме три прости примера за рекурсия:
За всеки пример ще посочим проблема, ще предоставим рекурсивната реализация на Python и след това ще обясним как работи рекурсивната реализация.
#1. Факторно изчисление с помощта на рекурсия
Задача: Изчислете факториела на цяло неотрицателно число n, означено като n!. Математически факториелът на число n е произведението на всички положителни цели числа от 1 до n.
Факторното изчисление се поддава добре на рекурсия, както е показано:
Ето рекурсивната функция за изчисляване на факториела на дадено число n:
def factorial(n):
# Base case
if n == 0 or n == 1:
return 1
# Recursive case: n! = n * (n-1)!
else:
return n * factorial(n - 1)
Нека изчислим 5! използвайки функцията factorial():
factorial_5 = factorial(5) print(factorial(5)) # Output: 120
Сега да видим как работи функцията:
- Имаме основен случай, който проверява дали n е равно на 0 или 1. Ако условието е изпълнено, функциите връщат 1. Припомнете си, че 0! е 1, както и 1!.
- Ако n е по-голямо от 1, изчисляваме n! чрез умножаване на n с факториела на n-1. Това се изразява като n * факториел (n – 1).
- Функцията продължава да прави рекурсивни извиквания с намаляващи стойности на n, докато достигне основния случай.
#2. Числа на Фибоначи с рекурсия
Проблем: Намерете термина на n-тия индекс в Ред на Фибоначи. Последователността на Фибоначи се дефинира, както следва: F(0) = 0, F(1) = 1 и F(n) = F(n-1) + F(n-2) за n >= 2.
def fibonacciSeq(n):
# Base cases
if n == 0:
return 0
elif n == 1:
return 1
# Recursion: F(n) = F(n-1) + F(n-2)
else:
return fibonacciSeq(n - 1) + fibonacciSeq(n - 2)
Нека стартираме функцията:
fib_5 = fibonacciSeq(5) print(fib_5) # Output: 5
Ето как работи функцията:
- Нека започнем с обсъждане на основните случаи. Ако n е 0, връща 0. И ако n е 1, връща 1. Припомнете си F(0) = 0 и F(1) = 1.
- В рекурсивния случай, ако n е по-голямо от 1, функцията изчислява F(n) чрез добавяне на членовете F(n-1) и F(n-2). Това се изразява като fibonacciSeq(n – 1) + fibonacciSeq(n – 2).
- Функцията продължава да прави рекурсивни извиквания с намаляващи стойности на n, докато достигне базовите случаи.
#3. Рекурсивна реализация на двоично търсене
Проблем: Приложете алгоритъм за двоично търсене, използвайки рекурсия, за да намерите позицията на целевия елемент в сортиран списък.
Ето рекурсивната реализация на двоично търсене:
def binarySearch(arr, target, low, high):
# Base case: target not found
if low > high:
return -1
mid = (low + high) // 2
# Base case: target found
if arr[mid] == target:
return mid
# Recursive case: search left or right half of the array
elif arr[mid] > target:
return binarySearch(arr, target, low, mid - 1)
else:
return binarySearch(arr, target, mid + 1, high)
Функцията binarySearch продължава да разделя интервала на търсене наполовина с всяко рекурсивно извикване, докато или намери целта, или установи, че целта не е в списъка.
Ето примерно изпълнение на функцията:
arr = [5, 8, 13, 24, 37, 49, 51, 64, 72, 88, 96] target = 37 idx = binarySearch(arr, target, 0, len(arr)-1) print(idx) # Output: 4
Нека разбием какво прави функцията:
- В рекурсивната реализация на двоично търсене имаме два основни случая. Първо, ако ниското стане по-голямо от високото, това означава, че целевият елемент не е в списъка. И така, връщаме -1, за да покажем, че целта не е намерена.
- Другият базов случай проверява дали елементът в средата на средния индекс на текущия интервал на търсене е равен на целта. Ако съвпадат, връщаме индекса в средата, което показва, че сме намерили целта.
- В рекурсивния случай, ако средният елемент е по-голям от целта, ние търсим рекурсивно в лявата половина на масива, като извикаме binarySearch(arr, target, low, mid – 1). Ако средният елемент е по-малък от целта, търсим дясната половина, като извикаме binarySearch(arr, target, mid + 1, high).
Рекурсивен срещу итеративен подход
Итеративният подход – използване на цикли – е друг общ подход за решаване на проблеми. И така, как се различава от рекурсията? Нека разберем.
Първо, сравняваме рекурсивни и итеративни решения на общ проблем: изчисляване на факториела на число.
Ето рекурсивната реализация на факториалното изчисление:
def factorialRec(n):
# Base case
if n == 0 or n == 1:
return 1
# Recursive case: n! = n * (n-1)!
else:
return n * factorial(n - 1)
Тъй като знаем, че факториелът на неотрицателно число е произведението на всички числа от 1 до n, можем също да напишем итеративна реализация, използвайки цикли.
def factorialIter(n):
result = 1
for i in range(1, n + 1):
result *= i
return result
И двете реализации дават идентични резултати.
factorial_5 = factorialRec(5) print(factorial_5) # Output: 120 factorial_5 = factorialIter(5) print(factorial_0) # Output: 120
Но предпочитан ли е итеративният подход пред рекурсията? Когато има дълбока рекурсия — с твърде много извиквания на функции — може да попаднете на грешки поради превишаване на дълбочината на рекурсия. Цикълът е по-добър вариант за проблеми, чиято рекурсивна реализация изисква твърде много извиквания на функции, за да се достигне до основния случай.
Нека обобщим разликите между итеративни и рекурсивни реализации:
ХарактеристикаРекурсивен подходИтеративен подходСтруктураИзползва рекурсивни извиквания на функции и разчита на стека за извикване. Използва цикли за итерация без допълнителни извиквания на функции. Основни случаи Изисква изрични базови случаи за спиране на рекурсията. Обикновено използва условия за цикъл за прекратяване. Производителността може да бъде по-малко ефективна от паметта поради стека за извикване . Дълбоката рекурсия понякога може да доведе до грешки при препълване на стека. Обикновено по-ефективно за паметта и по-малко склонни към грешки при препълване на стека. Отстраняването на грешки може да бъде предизвикателство за отстраняване на грешки поради множество извиквания на функции и вложени контексти на изпълнение. Обикновено по-лесно за отстраняване на грешки поради директния линеен поток на изпълнение .Итеративен срещу рекурсивен подход
Заключение
В тази статия започнахме, като научихме какво е рекурсия и как да дефинираме рекурсивни функции с основни случаи и рекурентни отношения.
След това написахме код на Python — рекурсивни реализации на общи проблеми с програмирането. Накрая научихме разликите между итеративния и рекурсивния подход и плюсовете и минусите на всеки от тези подходи.
След това вижте този списък с въпроси за интервю за Python.