Освещение рекурсии

Question

Я просто хотел удостовериться, что я полностью уверен в рекурсии. Я использовал его в нескольких приложениях, но понял, что, когда кто-то попросил меня определить его (более новый программист спросил об этом), я немного пошатнулся в определении и немного разобрался с ним. Я просто хотел связаться с большим сообществом разработчиков, чтобы убедиться, что я на правильном пути.

Из того, что я знаю, рекурсия в информатике - это когда некоторые ответы на заданную проблему или проверку (то есть оператор if) зависят от чего-то другого, связанного с тем же методом. Одним из способов решения этой проблемы может быть функция, вызывающая себя (которая поддерживается большинством языков программирования). Я написал простую программу Фибоначчи ниже:

public int fib(int n) { 
    if(n <= 1) { 
     return n; 
    } else { 
     return fib(n - 1) + fib(n - 2); 
    } 
} 

Дайте мне знать, если я на правильном пути. Кроме того, я знаю, что есть похожие вопросы по рекурсии, но, пожалуйста, не закрывайте этот вопрос как дубликат, потому что это более общий вопрос, не ограничиваясь конкретным языком, а скорее понятие о том, что такое рекурсия.

Спасибо,

brld

Answer 1

Вы находитесь на правильном пути. Я бы разбил это на части:

1. Определение: По определению словаря рекурсия - это процесс, называющий себя. Этот вызов обычно прямой, как в вашем примере, но также может быть косвенным: f1 и f2 называют друг друга, но не сами.
2. Пример: Так же, как вы это сделали ... показать известную функцию с понятным рекурсивным определением. Я обычно использую факториал, поскольку он имеет только один рекурсивный вызов; то я представляю случай Фибоначчи.
3. Механика: Опишите критические свойства базового футляра (что заставило его остановиться, наконец) и упрощение (уменьшите проблему до повторения).
4. Правильное использование: Практически любое реальное приложение для программирования с рекурсивным описанием будет иметь итеративное (циклическое) решение, которое занимает меньше вычислительного времени. Однако, если описание natural является рекурсивным, вполне возможно, что наиболее эффективное решение в конечном итоге является рекурсивным. Рассмотрите ресурсы ремонта и обслуживания в дополнение к простым циклам выполнения и помните, что FLOPS дешевле каждый месяц.