В этом блоге я собираюсь описать рекурсию, и в результате вы сможете узнать — —
Что такое рекурсия?
Почему мы используем рекурсию?
Как использовать рекурсию в программировании?
Как работает рекурсия?
Чем рекурсия отличается от циклов?
Давайте посмотрим, что такое рекурсия, на примере реального мира. Предположим, ваш отец поручил вам наполнить бутылку водой. Сейчас ты так занят, что поручил эту работу своему младшему брату. Твой брат тоже занят, поэтому он попросил маму сделать то же задание. Поскольку ваша мама занимается другой работой, она снова передает работу по наполнению бутылки с водой вашему папе. Теперь снова твой отец приказал тебе выполнить ту же задачу. Здесь вы можете видеть, что работа передается от одного человека к другому, и этот процесс передачи работы можно рассматривать как цикл.
Теперь возникает вопрос, если все люди заняты, то как задача будет выполнена. Каким будет решение этой проблемы? Решений для этого может быть много, одно из них, человек может оставить свою работу и выполнить эту задачу в первую очередь. Но в этой ситуации, как видите, ему или ей приходится оставить свою работу. Другой вариант — можно закончить свою работу и выполнить эту задачу позже. Но проблема в том, что это тоже важная работа.
Теперь появляется лучшая альтернатива: всякий раз, когда задача передается другому человеку, одна бутылка должна быть заполнена водой. Ваш отец наполняет одну бутылку, затем снова передает вам, вы наполняете другую бутылку с водой и поручаете работу своему брату, затем он наполняет одну бутылку и просит маму сделать то же самое. После одного цикла, двух циклов, трех циклов или четырех циклов переноса работы за один раз не останется ни одной бутылки с водой, которую можно было бы наполнить. Вот что такое рекурсия. Дело в том, что работа была проделана после создания цикла той же обработки. Условие остановки цикла называется базовым случаем или случаем завершения.
Рекурсия означает, что функция вызывает себя снова и снова, пока не будет получен желаемый результат.
Мы можем сказать, что «рекурсия — это метод функции для достижения желаемых целей путем манипулирования ее входными параметрами каждый раз, когда она вызывает себя».
Почему мы используем рекурсию?
Проще говоря, мы используем рекурсию для выполнения одной и той же задачи повторения. В приведенном выше примере наполнение бутылок — это одна и та же повторяющаяся задача, выполняемая разными людьми. Так же, как рекурсия работает в программировании. Это делается так же, как и в первый раз, но с другими параметрами функций или значениями.
В вашей голове возникает вопрос: если нам нужно выполнить повторение, а затем завершить эту повторяющуюся задачу, мы можем использовать циклы вместо рекурсии. Так что не волнуйтесь, позже в этой статье я также определю, чем рекурсия отличается от рекурсии. петли, как и где мы должны использовать какие методы для решения проблемы.
Рекурсия через программирование
Напишите программу, используя функцию для печати «Hello World».
может быть, вы пишете так же, как показано ниже: -
static void show(){ // function
System.out.println("Hello World");
}
public static void main(String[] args) {
show();
}
А что, если я попрошу вас напечатать «Hello World» 5 раз на экране,
Может быть, вы напишете или придумаете одно из решений, как показано ниже: -
//1.
static void show(){ // function
System.out.println("Hello World");
}
public static void main(String[] args) {
show();
show();
show();
show();
show();
}
//2.
static void show(){ // function
System.out.println("Hello World");
System.out.println("Hello World");
System.out.println("Hello World");
System.out.println("Hello World");
System.out.println("Hello World");
}
public static void main(String[] args) {
show();
}
а также вы можете иметь в уме другое решение, такое же, как и ниже — — —
//3.
static void show1() { // function 1
System.out.println("Hello World");
show2();
}
static void show2() { // function 2
System.out.println("Hello World");
show3();
}
static void show3() { // function 3
System.out.println("Hello World");
show4();
}
static void show4() { // function 4
System.out.println("Hello World");
show5();
}
static void show5() { // function 5
System.out.println("Hello World");
}
public static void main(String[] args) { // main function
show1();
}
Недостатком приведенных выше примеров являются — —
› Одни и те же строки написаны много раз
›Написание и выполнение заняло слишком много времени, если мне нужно напечатать «Hello World» 50 раз, 100 раз, 1000 раз, 1200 раз и так далее.
› Это также нарушает СУХОЕ (не повторять себя) правило программирования.
Итак, мы уже читали, что рекурсия — это функция, вызывающая сама себя. Так что давайте напишем это также в программировании, чтобы напечатать «Hello World».
static void show() { // function
System.out.println("Hello World");
show(); //function calling again itself
}
public static void main(String[] args) {
show(); // function calling in main
}
Здесь вы можете заметить — —
› основная функция вызова вызова
› show call show function для печати «Hello World»
› снова вызовите себя для печати
Функция вызывает сама себя и делает повторение. Этот процесс известен как цикл. Теперь возникает вопрос, где заканчивается этот цикл и что произойдет, если этот цикл не остановится? Чтобы узнать это, сначала нам нужно немного узнать о том, как работает фоновая обработка всякий раз, когда запускается программа.
Когда мы нажимаем на файл Java для запуска, классы и объекты загружаются в кучу, а функции и ссылочные переменные сохраняются в стеке.
Эти функции загружаются в стеки таким образом, что вызов функции сначала происходит в стеке, а затем завершается последним. Это то же самое, что прийти первым и уйти последним.
Если мы вернемся к приведенному выше примеру, цикл генерирует вызов одной и той же функции, то есть show(). Посмотрите на изображение ниже, как JVM будет загружать функции одну за другой в стек.
Процесс загрузки одной функции рассматривается как push, а завершение работы одной функции после нарушения условия считается pop.
Эта последовательность загрузки функций в стек называется сборкой стека, а завершающая последовательность функций называется падением стека.
Благодаря свойствам создания стека в памяти, push, pop, build , fall и LIFO этот процесс известен как CALL STACK.
Вернемся к вопросу, где заканчивается этот цикл и что произойдет, если это не так? Так как мы знаем, что функции вызываются один за другим последовательно в стеке. Давайте возьмем реальный пример, чтобы понять это, предположим, что у вас есть школьная сумка, и вы должны хранить в ней книги. Вы возьмете сумку и начнете складывать в нее книги одну за другой, вы легко поместите 1-ю книгу, затем 2-ю, затем 3-ю, 4-ю, 5-ю, 6-ю, 7-ю… и так далее, в один момент емкость сумки будет заполнена. Теперь, если вы попытаетесь положить в сумку больше книг, это невозможно, так как емкость уже заполнена.
То же самое происходит в стеке, если вы вызываете много функций внутри стека, а затем оставляете их занимающими место в памяти, в какой-то момент емкость стека будет заполнена, и будет сгенерирована ошибка java.lang.StackOverflowError
Другой вопрос, как остановить этот цикл, вернемся к приведенному выше примеру заполнения бутыли, там в решении мы поставили условие наполнять хотя бы одну бутылку каждый раз, когда будет перенос работы. Одно время не было бутылки.
То же самое мы сделаем с циклом, мы зададим условие внутри функции, чтобы она перестала вызывать себя, всякий раз, когда это условие нарушается, функция начинает завершать свои загруженные функции в стеке. Это условие называется базовым случаем или условием завершения.
Итак, если мы хотим напечатать «Hello World» 5 раз, мы создадим базовый вариант для его завершения.
static void show(int base) { // function
if(base>5){ // base condition
return;
}
System.out.println("Hello World");
show(base+1);
}
public static void main(String[] args) {
show(1);
}
Вот как работает стек вызовов, когда выполняется приведенный выше код.
Теперь вы можете заметить — —
- У нас есть одна фаза, идущая к базовому случаю.
- У нас есть еще одна фаза, возвращающаяся из базового случая.
Первая фаза перехода от исходного рекурсивного вызова к базовому варианту известна как фаза вызова.
Второй этап возврата от базового случая к исходному рекурсивному вызову известен как фаза возврата.
Эта фаза возврата недоступна в циклах, и именно поэтому рекурсия лучше, чем циклы.
Давайте разберемся, как мы можем использовать эту фазу возврата в программировании —
Пример — — Напишите программу для печати от 1 до 10 с использованием рекурсии, приняв параметр как 10 в функции.
static void printvalue(int num){
if(num==0){
return;
}
printvalue(num-1);
//printing here while stack is falling ----returning phase
System.out.println(num);
}
public static void main(String[] args) {
printvalue(10);
}
Сводка
- Рекурсия — это функция, вызывающая сама себя.
- Рекурсия состоит из двух фаз: фазы вызова и фазы возврата, что делает ее более продвинутой, чем циклы.
