Recursion Advanced

Question 1

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

Answer 1

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

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

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

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

Question 2

What is the difference between recursion and iteration?

Answer 2

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

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

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

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

Question 3

What are the advantages and disadvantages of the recursion?

Answer 3

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

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

Question 4

What is backtracking?

Answer 4

Backtracking е метод за решаване на проблеми, при който намираме път в лабиринт (връщаме се назад до последното място, където е имало разклонение и е можело да сменим посоката)

Question 5

What is memoization?

Answer 5

• Мемоизация е техника за оптимизация
• Елиминира повторните извиквания на метода при аргументи, които вече са изчислени.
• Запазваме резултата от функцията при подаден този аргумент и след това, когато извикаме функцията със същия аргумент директно ползваме запазената стойност.