Как сделать рекурсию в java

Добавил пользователь Алексей Ф.
Обновлено: 04.10.2024

Я изучаю Java, используя книгу Java: полная ссылка. В настоящее время я работаю над темой Recursion.

Обратите Внимание: есть аналогичные вопросы по stackoverflow. Я обыскал их, но не нашел ответа на свой вопрос. Меня смущает логика следующей программы.

Если я запускаю приведенную ниже программу, она выдает правильный вывод, но я не понял логику.

Я не понял логика в следующей строке:результат = факт (n-1) * n;
из моих знаний, если мы передадим значение n=4, как показано в приведенной ниже программе,
затем в результате сохраняется 3 * 4, т. е. 12.
опять же, факт(n-1) называется. Тогда n становится 3.
затем 2 * 3 сохраняется в результате замены предыдущих 12.

Я думаю, вы поняли, где я застрял вверх / в замешательстве.

result локальная переменная fact метод. Поэтому каждый раз, когда вызывается метод fact, результат сохраняется в другой переменной, чем предыдущий вызов факта.

поэтому, когда факт вызывается с 3 в качестве аргумента, вы можете представить, что его результат

сначала вы должны понять, как работает factorial.

давайте 4! в качестве примера.

давайте смоделируем код, используя пример выше:

в большинстве языков программирования у нас есть то, что мы называем function stack . Это похоже на колоду карт, где каждая карта помещается над другой-и каждая карта может рассматриваться как функция, таким образом, передавая метод fact :

уровень стека 1: fact(4) // n = 4 and is not equal to 1. So we call fact(n-1)*n

стек Уровень 2: fact(3)

стек 3-го уровня: fact(2)

уровень стека 4: fact(1) / / теперь, n = 1. таким образом, мы возвращаем 1 из этой функции.

стек 3-го уровня: 2 * fact(1) = 2 * 1 = 2

уровень стека 2: 3 * fact(2) = 3 * 2 = 6

уровень стека 1: 4 * fact(3) = 4 * 6 = 24

обратите внимание на эти строки:

это вызывает функцию себя. Через 4 например,

в последовательности согласно стогам функции..

надеюсь, вы поняли.

вот еще одно объяснение того, как вычисление факториала с помощью рекурсии строительство.

давайте немного изменим исходный код:

вот расчет 3! подробнее:

ваше замешательство, я полагаю, происходит от того, что вы думаете, что есть только один result переменной, тогда как на самом деле есть result переменной для каждого вызова функции. Поэтому старые результаты не заменяются,а возвращаются.

предположим, что вызов fact(2) :

надеюсь, теперь понятнее.

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

ключевым моментом, который вам не хватает здесь, является то, что переменная " результат "является переменной стека, и как таковая она не"заменяется". Чтобы уточнить, каждый раз, когда вызывается факт, новая переменная под названием "результат" создается внутри интерпретатора и связана с этим вызовом методов. Это в отличие от полей объекта, которые связаны с экземпляром объекта, а не с конкретным вызовом метода

хотя это старый, он по-прежнему довольно хорошо подходит в google. Поэтому я решил упомянуть об этом. Никто не упоминал, чтобы проверить, когда x = 0.

Это не проверяется с предыдущими ответами и вызовет переполнение стека, если факт(0) был запущен. В любом случае простое исправление:

Рекурсия — это что-то, что описывает само себя.

Представить рекурсию проще всего на примере зеркального коридора — когда напротив друг друга стоят два зеркала. Если посмотреть в одно, то в нём будет отражение второго, во втором — отражение первого и так далее.

Второй пример, чуть более академически правильный — это фрактал. Тот же треугольник Серпинского — это пример рекурсии, потому что часть фигуры — это одновременно вся фигура.

Треугольник состоит из 3 точно таких же треугольников.

Рекурсия в программировании

В программировании под рекурсией чаще всего понимают функцию, которая вызывает саму себя.

При решении некоторых задач мы можем обнаружить, что решение можно разбить на несколько простых действий и более простой вариант той же задачи.

Например, при возведении числа в степень мы берём число, умножаем его на себя несколько раз. Эту операцию можно представить в виде:

Но это же можно представить в виде нескольких последовательных умножений на 2:

При таком представлении всё возведение в степень — это лишь умножение предыдущего результата на 2:

Именно такие задачи называются рекурсивными — когда часть условия ссылается на всю задачу в целом (или похожую на неё).

У рекурсии 2 составляющие: повторяющиеся операции и базовый случай.

Повторяющиеся операции

В примере с возведением в степень повторяющиеся операции — это умножение.

Такие операции могут быть сложными и включать в себя несколько подзадач. Такое, например, часто встречается в математике.

Знаменитая сумма всех натуральных чисел контринтуитивно равняется -1/12. А доказывается это именно рекурсивно.

Базовый случай

Вторая важная часть рекурсии — это базовый случай.

Базовый случай — это условие, при выполнении которого рекурсия заканчивается и функция больше не вызывает саму себя.

Например, при возведении в степень базовый случай наступает, когда значение степени становится равно искомому.

Как только выполнение доходит до базового случая, оно останавливается.

Без базового случая любая рекурсивная функция уйдёт в бесконечное выполнение, потому что будет вызывать себя без конца.

В JS это приводит к переполнению стека вызовов, и функция останавливается с ошибкой.

Если выполнить функцию без базового случая, которая лишь вызывает себя, получим ошибку.

Цикл и рекурсия

Из-за повторяющихся операций рекурсия схожа с циклом. Их часто считают взаимозаменяемыми, но это всё же не совсем так.

Рекурсия проигрывает циклу в следующем:

Отлаживать рекурсию значительно сложнее, чем цикл, а если функция написана плохо — то и просто читать.
Она может приводить к переполнению стека. Особенно это ощутимо в таких языках как JS, где переполнение стека может наступить раньше базового случая с высокой вероятностью.
Её выполнение может (хотя необязательно) занимать больше памяти.

Цикл же проигрывает рекурсии в таких вещах:

Его нельзя использовать в функциональном программировании, потому что он императивен.
Циклом гораздо сложнее обходить вложенные структуры данных, например, каталоги файлов.
Результат выполнения рекурсивной функции проще закэшировать, чтобы ускорить выполнение, с циклом это сделать сложнее.
При работе с общими ресурсами или асинхронными задачами чаще удобнее использовать рекурсивные функции из-за замыканий.

Давайте решим одну и ту же задачу с использованием цикла и рекурсии, чтобы увидеть разницу в подходах. Будем писать функцию для нахождения факториала.

Факториал числа — это произведение всех чисел от единицы до этого числа. Например, факториал 5 — это произведение (1 × 2 × 3 × 4 × 5) = 120.

Факториал с помощью цикла

Сперва решим задачу нахождения факториала с помощью цикла.

В этой функции мы используем цикл, чтобы умножить каждое число на результат предыдущего умножения. То же самое мы можем сделать и рекурсивно.

Факториал с помощью рекурсии

Для расчёта факториала рекурсивно мы создадим функцию, в которой в первую очередь опишем базовый случай, а уже потом — повторяющиеся действия.

Хорошим правилом при работе с рекурсией считается первым делом описывать базовый случай (как ранний выход, early return) и только потом — всё остальное. Это позволяет сделать работу с рекурсией безопаснее.

В виде блок-схемы мы можем представить алгоритм факториала как условие и под-вызов той же функции.

Кроме того, что функция стала заметно короче, она теперь выражает непосредственно математическую суть факториала.

Процесс вычисления факториала 5 будет состоять из 4 под-вызовов функции factorial() .

Разберём по шагам, что происходит с переменной n и результатом функции factorial после каждого вызова:

Минусы такой реализации:

Много областей видимости (замыканий), которые относительно требовательны к памяти.
Относительно просто читать, но сложнее отлаживать, чем цикл.

Если мы часто считаем факториалы, мы можем кэшировать результаты выполнения, чтобы не считать факториалы заново. Рекурсивная функция с кешем будет возвращать посчитанный ранее результат сразу же, цикл же будет считать заново.
Невозможно повлиять на процесс подсчёта как-то извне, замыкания не дают внешнему миру получить доступ к переменным внутри.

Рекурсивные структуры данных

Раньше мы упомянули, что в программировании чаще всего под рекурсией понимают функцию, которая вызывает сама себя. Но кроме рекурсивных функций ещё есть рекурсивные структуры данных.

Структура данных — это контейнер, который хранит данные в определённом формате. Этот контейнер решает, каким образом внешний мир может эти данные считать или изменить.

Структуры данных, части которых включают в себя такие же структуры, называются (вы угадали) рекурсивными. Работать с такими структурами в цикле не очень удобно. Чтобы понять почему, рассмотрим пример одной из рекурсивных структур данных — дерева.

Деревья

У каждого дерева есть корень — узел, из которого берут начало остальные узлы. Корень DOM-дерева выше — это элемент html .

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

С рекурсией обход дерева становится немного проще.

Рекурсивный обход

В случае с рекурсией мы можем придумать например такой алгоритм для обхода дерева:

базовый случай: если у узла дерева нет дочерних узлов вовсе, или мы обошли их все — возвращаем название этого элемента;
повторяемые операции: рекурсивно обходим каждый дочерний элемент, собирая их названия.

Таким образом, начав с элемента html , мы пройдём по каждому элементу дерева и запишем их названия. В псевдокоде это выглядело бы так:

Когда использовать рекурсию

Сама по себе рекурсия — это всего лишь инструмент. Нет чётких правил, когда её надо использовать, а когда — нет. Есть лишь некоторые рекомендации.

Преподаватель дает примеры по рекурсии. И сам я даже что-то решал. Но, убейте, до конца тему не пойму! Приведите плз., кто может 2-3 простых примера рекурсии, да таких, без заморочек, с простыми операторами, чтобы любому человеку было понятно!

Удар ногой в юнити
Как можно организовать? Пробовал на ногу круглый колайдер нацепить, вроде бьет по ригибоди.

болит зуб, что делать?
болит зуб, что делать? знаете ли Вы какие нибудь работающие способы, которыми сами пользуетесь.

Задел ногой системник, перестал включаться
В общем задел я ногой системник ( слегка, раньше не падал, ничего такого ), и теперь он не.

Образно, рекурсию можно представить ввиде подзорной трубы, возмем для примера классический алгоритм рекурсии, вычисление факториала:

Вызовем этот метод с аргументом 5, что произойдет внутри алгоритма;

1 - шаг: В начале метод проверяет не равно ли n единице, потом:

2 - шаг: Метод вызывает самого себя с аргументом 4, процесс повторяется с шага 1, и снова метод вызывает себя но, уже с аргументом 3, и цикл снова повторяется, и так до тех пор пока метод не вызовет себя с аргументом 1, что будет означать конец рекурсии и начало обратного процесса, 1 умножается на 2 и возвращается, 3 умножается на 2, потом 6 умножается на 4, и в исходном вызове (самый первый вызов с аргументом 5) 24 умножается на 5, после чего возвращается вызывающему методу.

Для наглядности: пусть у нас 4 строки. Допустим, мы не знаем сколько там всего шариков, но мы знаем, что это количество шариков в строве 4(4 штуки) + все остальные шарики в оставшемся треугольниее(уже из трех строк)
Задача немного упростилась, уже нужно посчитать количество шариков в треугольнике из трех строк, а это так же само - 3 + количество шариков в треугольнике из двух строк и так далее. Единственное, нам при рекурсии нужно как то сказать когда остановиться(задать известное/начальное значение/условие выхода из рекурсии). В данном случае можно сказать, что если в треугольнике 1 строка, то шариков 1. Можно в принципе сказать что если 0 строк то и шариков 0. Но нельзя задавать условие например если 4 строки то сумма 10 шариков, так как тогда не узнаем для меньшего числа строк.(хотя для большего годится)

как работает если подставить например 5: зашло, проверило что 5 не равно 1 и возвращает (1 + функция для четырех), дальше считается функция для четырех: проверяется что 4 не равно 1 и возвращается значение (1 + функция для трех) и т.д. пока не дойдет до вычисления функции от 1, а это уже известно, и получается 5 + 4 + 3 + 2 + 1 = 15

Нужно разобрать действие на видеоуроке, не получается зуб(
Всем привет, помогите пожалуйста разобраться с видеоуроком, не могу понять какое действие сделано.

STM32L152 проблема с таймером(ногой PB12) и DAC(PA5)
Есть проектик на STM32T152. К ноге PB12 подключен пьезик, и используется таймер TYM10 в качестве.

Отображение "зуб пилы" и сдвиги Бернулли
xn+1 = 2xn (mod 1), где x (mod 1) означает дробную часть x. В двоичной системе счисления умножение.

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

Рекурсивный возврат СТРОКИ, состоящей из последовательности от 1 до n через пробел.

4 ответа 4

Это хрестоматийная ошибка, когда не используется результат рекурсивного вызова.

Ошибка в том, что вы вызываете функцию с циклом внутри этого же цикла + пытаетесь присвоить тип (char) для переменной n. Вот рабочий код

А вот код для вашей задачи от 1 до n

Или через цикл for

UPD Рекурсивно

Важно понять смысл рекурсивного метода.

Тривиальный случай: n = 1 -> выводим 1
Нетривиальный случай: n > 1 -> уменьшаем размер задачи

Представим, что задача для n-1 уже решена.
Что нужно будет сделать, чтобы задача для n была решена тоже? Добавить пробел и n.

Я думал что рекурсия это метод вызывающий сам себя. А здесь этого не видно. ОбЪясните пожалуйста что я не понимаю

Ну, если тело цикла обозвать функцией, k - аргументом, а условие - условием выхода, то вполне себе рекурсия. Хвостовая и уже оптимизированная. Без стека и call, зато с каким-нибудь jcxz =)