Обяснете концепцията за рекурсивните функции и как работят

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

Принцип на работа:

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

Пример: изчисляване на факториела на число n (n!)

def factorial(n):
    if n == 0:
        return 1  # базов случай
    else:
        return n * factorial(n - 1)  # рекурсивно извикване

Тук factorial се извиква сама с n-1, докато не достигне 0, след което започва да връща стойности нагоре по веригата.

Рекурсията е полезна за задачи, които естествено се разделят на подобни подзадачи, като обход на дървета, изчисляване на числа на Фибоначи, сортиране и др.