C++ Рекурсія
Рекурсія
Рекурсія — це техніка здійснення самого виклику функції. Ця техніка дає змогу розділити складні проблеми на прості, які легше вирішити.
Рекурсія може бути трохи складною для розуміння. Найкращий спосіб зрозуміти, як це працює, — поекспериментувати з нею.
Приклад рекурсії
Скласти два числа легко, але додати діапазон чисел складніше. У наведеному нижче прикладі рекурсія використовується для додавання діапазону чисел шляхом розбиття її на просте завдання додавання двох чисел:
Приклад
int sum(int k) {
if (k > 0) {
return k + sum(k - 1);
} else {
return 0;
}
}
int main() {
int result = sum(10);
cout << result;
return 0;
}
Спробуйте самі »
Пояснення прикладу
Коли викликається функція sum(), вона додає параметр k до суми всіх чисел, менших за k і повертає результат. Коли k стає 0, функція просто повертає 0. Під час роботи програма виконує такі дії:
10 + ( 9 + sum(8) )
10 + ( 9 + ( 8 + sum(7) ) )
...
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + sum(0)
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 0
Оскільки функція не викликає сама себе, коли k дорівнює 0, програма зупиняється на цьому та повертає результат.
Розробник має бути обережним із рекурсією, оскільки може бути дуже легко скользнути до написання функції, яка ніколи не завершується, або такої, яка використовує надлишкові обсяги пам’яті чи потужності процесора. Однак, коли написана правильна рекурсія, вона може бути дуже ефективним і математично елегантним підходом до програмування.
