Recursion

Question 1

What is recursion?

Answer 1

• Техника(концепция) за решаване на проблеми, при която проблемът се свежда до по-малък проблем от същото естество.
• Метод, който извиква себе си, до момент, в който вече не извиква себе си (достигнал е базовия случай/дъно на рекурсията).
• Съществуват 2 вида рекурсия:
  -> Директна рекурсия (извиква себе си)
  -> Индиректна рекурсия (през други методи извиква себе си)

Примери за рекурсивни алгиритми: Merge Sort, Quick Sort, Tower of Hanoi, Fibonacci Series, Factorial Problem

Question 2

What is the structure of a recursion method?

Answer 2

Структурата на рекурсивен метод обикновено включва следните компоненти:
1. Базов случай:
- Условие, което спира рекурсивните извиквания и предоставя директно решение на подпроблема. Осигурява изход от рекурсията.
2. Рекурсивен случай:
- Част от метода, която извиква самия метод с модифицирани параметри. Този случай трябва да се приближава към базовия случай.

Question 3

Explain/illustrate the execution model of a recursion method.

Answer 3

Модел на изпълнение на рекурсивен метод:
1. Начало на рекурсивно извикване:
- Методът е извикан с определени аргументи. Започва изпълнение на метода.
2. Базов случай:
- Методът проверява дали е достигнат базовият случай. Ако да, връща резултат и спира рекурсията.
3. Рекурсивен случай:
- Ако базовият случай не е достигнат, методът извиква самия себе си с нови аргументи. Започва ново извикване на метода.
4. Стек на рекурсия:
- Всеки рекурсивен случай създава нова рамка на метод на стека за изпълнение.
- Всяка рамка съдържа текущите параметри и състоянието на метода.
5. Изпълнение на рекурсивни извиквания:
- Методът продължава да извиква самия себе си, докато не бъде достигнат базовият случай. Всеки рекурсивен случай създава нова рамка на стека.
6. Връщане на резултат:
- Когато базовият случай бъде достигнат, методът връща резултат. Резултатът се връща на предходното извикване на метода.
7. Премахване от стека:
- След като резултатът е връщан на предходното извикване, рамката на стека за текущото извикване се премахва. Процесът продължава, докато всички извиквания на метода не бъдат завършени.

Question 4

Why is recursion important, when to use it and when to avoid it?

Answer 4

Значение на рекурсията:
- Разделя проблемите на по-малки подпроблеми.
- Подходяща за дървовидни структури и самоподобни задачи.

Защо?
- чрез рекурсия можем да постигнем елегентни решения на дадени проблеми
- рекурсията е доста мощен инструмент
- рекурсията се среща на много места в света на програмирането

Кога да използвате:
- За проблеми с дървета и графи.
- Когато рекурсията прави кода по-ясен.
- алгоритми „разделяй и владей“.
- динамично програмиране (рекурсия и мемоизация)

Кога да избегнете:
- рекурсията има недостатъци по отношение на производителност и използването на памет
- При дълбока рекурсия (може да доведе до StackOverflowError).
- трябва да избягваме рекурсия, когато имаме голям размер на входните данни
- Ако е по-малко ефективна от итеративно решение.
- ако езикът, който използваме не поддържа актуализация на рекурсията

Question 5

What are the advantages and disadvantages of the recursion?

Answer 5

Предимства:
- прост и ясен код;
- рекурсията е интуитивна за проблеми, които могат да бъдат разделени на по-малки такива или имат самоподобна структура;
- разрешаване на сложни проблеми с малко усилия;
- модулност – рекурсивните функции разграничават логиката на основния проблем от тази на подпроблемите. Това прави кода по-модулен и лесен за разширяване;

Недостатъци:
- прекомерно използване на памет;
- ниска ефективност при големи входни данни;
- трудности при дебъгване;

Question 6

What is the difference between recursion and iteration?

Answer 6

Рекурсия:
- Определение: Функция извиква сама себе си, за да реши подпроблеми.
- Изпълнение: Всяко извикване на рекурсията създава нов Stack frame в Stack memory, което увеличава риска от Stack Overflow; По-бавна е, ако не е оптимизирана (чрез мемоизация)
- Подходяща: За проблеми, които естествено се разделят на по-малки подпроблеми (например, дървовидни структури).
- Недостатъци: Може да доведе до дълбочина на стека и StackOverflowError. Може да бъде по-малко ефективна от итерацията. По-сложни са за дебъгване и проследяване, когато е дълбока рекурсия

Итерация:
- Определение: Повтаря блок от код (например, с цикли) до постигане на условие.
- Изпълнение: Използва фиксирани ресурси без създаване на нови рамки на стека.; По-бърза (линейна сложност), тъй като не изискват извикване на функции и заделяне на памет в Stack(Stack frame)
- Подходяща: За проблеми, където повтарящите се действия са по-лесни за управление (например, обхождане на списък).
- Предимства: По-ефективна по отношение на паметта, не води до StackOverflowError. По-лесно за дебъг, тъй като се случва в един блок от код и промените в променливите са забележими
- Недостатък: Ако условието за изход на цикъла не е добре дефинирано може да се стигне до бекраен цикъл, което ще задържи програмата в неактивно състояние

Кратко сравнение:
- Рекурсия: Нови стаковете на изпълнение; по-чист код за сложни задачи.
- Итерация: Фиксирани ресурси; по-ефективна за директни повторения.

NB!!! Смята се, че всяка рекурсивна имплементация може да се изпълни чрез итериране и обратното!!!