На додаток до відповіді @Harry.
види рекурсії
Рекурсивні функції можна виділити кілька видів:
- лінійна рекурсія. при якій рекурсивні виклики на будь-якому рекурсивном зрізі, ініціюють не більше одного подальшого рекурсивного виклику. (як в прикладі у @Harry)
- хвостова рекурсія (окремий випадок лінійної рекурсії), при якій рекурсивний виклик функції відбувається в кінці її роботи. (Як в прикладі у @Harry).
- нелінійна або паралельна рекурсія. при якій рекурсивні виклики на будь-якому рекурсивном зрізі, ініціюють більше одного подальшого рекурсивного виклику.
Хороший приклад даного виду - це обчислення n-го члена ряду Фібоначчі:
- взаємна або непряма рекурсія. при якій рекурсивний виклик даної функції відбувається з будь-якої іншої функції, яка сама викликалася з даної функції.
Коли варто використовувати рекурсію?
Користуйтеся рекурсією, якщо:
- задача розбивається на зменшені копії самої себе, і немає очевидного способу розв'язати цю проблему написанням циклу;
- ви працюєте з рекурсивної структурою даних, наприклад із зв'язаними списками
АЛЕ: Якщо завдання можна вирішити итеративно, то користуйтеся итерацией.
Як уникнути переповнення при рекурсії?
- Обов'язково має бути присутнім умова виходу з рекурсії.
- Якщо правило 1 задоволено, але все одно відбувається переповнення, то варто відмовитися від використання рекурсії і реалізувати алгоритм итеративно. (Цикли і динамічне програмування вам на допомогу)
Приклад ітеративного обчислення факторіала:
Наостанок, краще розуміння теорії досягається шляхом її застосування на практиці.