Вредоносное ПО (malware) - это назойливые или опасные программы,...
Varg говорит:
Добрый день, упорото ни могу понять как производит вычисления данная функция
{
if (n==1) return 1; //если новое значение 1, то будем складывать его с 1, а не с предыдущим. т.к. предыдущее - это ноль. и сложение 1+0 будет бесконечным.
else return sum(n-1)+n; //но если n>1, то складываем его с предыдущим значением, равным сумме всех элементов до n
}
По моему разумению в n находиться 5 условие не совпадает тогда выполняется данный код sum(n-1)+n то есть к 5 прибавляется что то полученное в скобках путем вычитания но что (5 - 1)+5 и если так то что останавливает данное арифметическое действие:?: :?: :?: Что за предыдущее значение, откуда оно берется чему равно:?: :?: :?:
Да почти все так как я и понял (в последнем абзаце вы показали рекурсию))), но остаться вопрос как получается сумма, которая потом вы водиться на экран?
Я работаю с Dev C++ у меня данный пример выводит сумму ==15, если по считать как написано в примере то сумма получается другой.
Я писал выше вот возьмем (5-1)+5=4+5=9
:
1+2+3+4+5 = 15. Пример правильно выводит.(5) //В функцию дали 5, проверили ее на равенство с единицей. не равно, вызвали функцию снова, отдав в нее 5-1
(5-1+(5)) //...
(4-1+(5-1+(5)))
(3-1+(4-1+(5-1+(5))))
(2-1+(3-1+(4-1+(5-1+(5)))))2-1 == 1, закончили вызывать функцию.
(2-1+(3-1+(4-1+(5-1+(5))))) == 15
это и есть результат.
Здесь результат работы функции - это разность первых двух чисел, а n - это вся остальная часть справа
__________________________________
Просто нужно функцию правильно понимать и принимать как вычисляемое значение и не понимать ее как переменную. Она похожа на переменную, но ближе к вычисляемой константе., хотя константой и не является, просто воспринимать так удобнее.
Да да да не успел написать, что понял, все верно, что то сразу не дошло. Спасибо вам хороший сайт))
И еще не совсем логично получается в 8й строке если поменять возвращаемое число с return 1 на 2 сумма меняется на 16 как это условие связано с 9й строкой?
С этим тоже все понятно просто return 2 добавляет к сумме так сказать свою лишению денницу.
:
не лишнюю денницу, а эту двойку, а если написать -3, то при сложении один раз будет отнимать тройку и т.д.
Вся логика в том, что любой рекурсивной функции нужна точка возврата.
Связь с девятой строкой в том, что в функцию sum при вызове её из внутри main передается число, при рекурсивных вызовах это число каждый раз уменьшается на единицу (n-1), этот результат n-1 проверяется на равенство с единицей и если равенство истинно, то вся полученная сумма будет просуммирована с тем числом, который в том return. иначе вся общая сумма будет просуммирована с этим новым n-1
Здравствуй Хабрахабр!
В этой статье речь пойдет о задачах на рекурсию и о том как их решать.
Кратко о рекурсии
Рекурсия достаточно распространённое явление, которое встречается не только в областях науки, но и в повседневной жизни. Например, эффект Дросте, треугольник Серпинского и т. д. Один из вариантов увидеть рекурсию – это навести Web-камеру на экран монитора компьютера, естественно, предварительно её включив. Таким образом, камера будет записывать изображение экрана компьютера, и выводить его же на этот экран, получится что-то вроде замкнутого цикла. В итоге мы будем наблюдать нечто похожее на тоннель.В программировании рекурсия тесно связана с функциями, точнее именно благодаря функциям в программировании существует такое понятие как рекурсия или рекурсивная функция. Простыми словами, рекурсия – определение части функции (метода) через саму себя, то есть это функция, которая вызывает саму себя, непосредственно (в своём теле) или косвенно (через другую функцию).
О рекурсии сказано много. Вот несколько хороших ресурсов:
- Рекурсия и рекурсивные задачи. Области применение рекурсии
Задачи
При изучении рекурсии наиболее эффективным для понимания рекурсии является решение задач.Как же решать задачи на рекурсию?
В первую очередь надо понимать что рекурсия это своего рода перебор. Вообще говоря, всё то, что решается итеративно можно решить рекурсивно, то есть с использованием рекурсивной функции.из сети
Любой алгоритм, реализованный в рекурсивной форме, может быть переписан в итерационном виде и наоборот. Останется вопрос, надо ли это, и насколько это будет это эффективно.
Для обоснования можно привести такие доводы.
Для начала можно вспомнить определение рекурсии и итерации. Рекурсия - это такой способ организации обработки данных, при котором программа вызывает сама себя непосредственно, либо с помощью других программ. Итерация - это способ организации обработки данных, при котором определенные действия повторяются многократно, не приводя при этом к рекурсивным вызовам программ.
После чего можно сделать вывод, что они взаимно заменимы, но не всегда с одинаковыми затратами по ресурсам и скорости. Для обоснования можно привести такой пример: имеется функция, в которой для организации некого алгоритма имеется цикл, выполняющий последовательность действий в зависимости от текущего значения счетчика (может от него и не зависеть). Раз имеется цикл, значит, в теле повторяется последовательность действий - итерации цикла. Можно вынести операции в отдельную подпрограмму и передавать ей значение счетчика, если таковое есть. По завершению выполнения подпрограммы мы проверяем условия выполнения цикла, и если оно верно, переходим к новому вызову подпрограммы, если ложно - завершаем выполнение. Т.к. все содержание цикла мы поместили в подпрограмму, значит, условие на выполнение цикла помещено также в подпрограмму, и получить его можно через возвращающее значение функции, параметры передающееся по ссылке или указателю в подпрограмму, а также глобальные переменные. Далее легко показать, что вызов данной подпрограммы из цикла легко переделать на вызов, или не вызов (возврата значения или просто завершения работы) подпрограммы из нее самой, руководствуясь какими-либо условиями (теми, что раньше были в условии цикла). Теперь, если посмотреть на нашу абстрактную программу, она примерно выглядит как передача значений подпрограмме и их использование, которые изменит подпрограмма по завершению, т.е. мы заменили итеративный цикл на рекурсивный вызов подпрограммы для решения данного алгоритма.
Задача по приведению рекурсии к итеративному подходу симметрична.
Подводя итог, можно выразить такие мысли: для каждого подхода существует свой класс задач, который определяется по конкретным требованиям к конкретной задаче.
Более подробно с этим можно познакомиться
Так же как и у перебора (цикла) у рекурсии должно быть условие остановки - Базовый случай (иначе также как и цикл рекурсия будет работать вечно - infinite). Это условие и является тем случаем к которому рекурсия идет (шаг рекурсии). При каждом шаге вызывается рекурсивная функция до тех пор пока при следующем вызове не сработает базовое условие и произойдет остановка рекурсии(а точнее возврат к последнему вызову функции). Всё решение сводится к решению базового случая. В случае, когда рекурсивная функция вызывается для решения сложной задачи (не базового случая) выполняется некоторое количество рекурсивных вызовов или шагов, с целью сведения задачи к более простой. И так до тех пор пока не получим базовое решение.
Итак рекурсивная функция состоит из
- Условие остановки или же Базовый случай
- Условие продолжения или Шаг рекурсии - способ сведения задачи к более простым.
Public class Solution { public static int recursion(int n) { // условие выхода // Базовый случай // когда остановиться повторять рекурсию? if (n == 1) { return 1; } // Шаг рекурсии / рекурсивное условие return recursion(n - 1) * n; } public static void main(String args) { System.out.println(recursion(5)); // вызов рекурсивной функции } }
Тут Базовым условием является условие когда n=1. Так как мы знаем что 1!=1 и для вычисления 1! нам ни чего не нужно. Чтобы вычислить 2! мы можем использовать 1!, т.е. 2!=1!*2. Чтобы вычислить 3! нам нужно 2!*3… Чтобы вычислить n! нам нужно (n-1)!*n. Это и является шагом рекурсии. Иными словами, чтобы получить значение факториала от числа n, достаточно умножить на n значение факториала от предыдущего числа.
Теги: Добавить метки
Рекурсивным называют метод, который прямо (непосредственно) или косвенно вызывает самого себя. Метод называют косвенно рекурсивным, если он содержит обращение к другому методу, содержащему прямой или косвенный вызов определяемого (первого) метода. В случае косвенной рекурсивности по тексту определения метода его рекурсивность может быть не видна. Если в теле метода явно используется обращение к этому методу, то имеет место прямая рекурсия. В этом случае говорят, что метод самовызывающий (self-calling). Именно самовызывающие методы ~ будем называть рекурсивными, а для методов с косвенной рекурсией будем использовать термин косвенно рекурсивные методы.
Классический пример рекурсивного метода - функция для вычисления факториала неотрицательного целого числа. На языке С# её можно записать таким образом (программа 09_16.cs):
static long fact(int k)
if (k < 0) return 0;
if (k == 0 || k == 1)
return k * fact(k - 1);
static void Main09_16()
Console.WriteLine("fact(5)=" + fact(5));
Для отрицательного аргумента результат (по определению факториала) не существует. В этом случае функция возвращает нулевое значение (можно было бы возвращать, например, отрицательное значение). Для нулевого и единичного аргумента по определению факториала возвращаемое значение равно 1. Если k >1, то вызывается та же функция с уменьшенным на 1 значением параметра и возвращаемое ею значение умножается на текущее значение параметра k. Тем самым организуется вычисление произведения 1*2*3*. ..*(k -2)*(k -1)* k .
При проектировании рекурсивного метода нужно убедиться
Что он может завершить работу, т.е. невозможно возникновение зацикливания;
Что метод приводит к получению правильных результатов.
Для удовлетворения первого требования должны соблюдаться два правила:
В последовательности рекурсивных вызовов должен быть явный разрыв, то есть самовызовы должны выполняться до тех пор, пока истинно значение некоторого выражения, операнды которого изменяются от вызова к вызову.
При самовызовах должны происходить изменения параметров и эти изменения после конечного числа вызовов должны привести к нарушению проверяемого условия из пункта 1.
В нашем примере условием выхода из цепочки рекурсивных вызовов является истинность выражения (k==0 || k==1). Так как значение k конечно и параметр при каждом следующем вызове уменьшается на 1, то цепочка самовызовов конечна. Идя от конца цепочки, т.е. от 1 != 1, к началу, можно убедиться, что все вызовы работают верно и метод в целом работает правильно.
Иллюстрация цепочки самовызовов для метода вычисления факториала fact (4)
Эффективность рекурсивного метода зачастую определяется глубиной рекурсии, т.е. количеством самовызовов в одной цепочке при обращении к методу.
В качестве примера рекурсивной процедуры приведём метод, преобразующий все цифры натурального числа в соответствующие им символы. Параметры метода - целое число типа int и массив результатов char. Текст метода (программа 09_17.cs):
// Метод для символьного представления цифр натурального числа
static void numbers(int n, char ch)
int ind = (int)Math.Log10((double)n);
ch = (char)(n + (int)"0");
numbers(n / 10, ch);
ch = (char)(n % 10 + (int)"0");
static void Main09_17()
char ch = new char;
numbers(523, ch);
Console.WriteLine("Цифры=" + new String(ch));
Ограничение : при обращении к методу необходимо, чтобы размер символьного массива-аргумента для представления результатов был не менее разрядности числа.
В теле метода значение переменной ind на 1 меньше разрядности числового значения аргумента int n. Если n<10, то ind=O и выполняются операторы
с = (char)(n + (int)"0"); return;
Оператор return завершает выполнение очередного экземпляра процедуры и тем самым прерывается цепочка её самовызовов. В противном случае выполняется оператор numbers(n/10, ch);. Это самовызов, в котором параметр п уменьшен в 10 раз, то есть в анализируемом числе отброшен младший разряд. Обратите внимание, что оператор ch = (char)(n%10 + (int)"0"); не выполнен - его исполнение отложено до завершения вызова numbers(n/10, ch). А завершение, т.е. разрыв цепочки самовызовов, наступит, когда значением аргумента будет число из одной цифры. Это значение - старшая цифра исходного числа - преобразуется к символьному виду и присваивается элементу ch[O]. После возврата из "самого глубокого" обращения к методу выполняется оператор
ch = (char)(n%10 + (int)"0");
Переменная п представляет в этом случае двухразрядное число и элементу массива ch присваивается изображение второй (слева) цифры числа и т.д.
Многие задачи, требующие циклического повторения операций, могут быть представлены как рекурсивными, так и итерационными алгоритмами. Основной для рекурсивного алгоритма является его самовызов, а для итерационного алгоритма - цикл.
В качестве иллюстрации приведём рекурсивный метод (процедуру) для вывода на консольный экран значений элементов символьного массива. Напомним, что при создании символьного массива без явной инициализации его элементам по умолчанию присваиваются значения "\0". Выводятся элементы массива, начиная с заданного. Окончание вывода - конец массива либо терминальный символ "\0" в качестве значения очередного элемента (программа 09_17.cs).
// Метод для печати элементов символьного массива
static void chPrint(char ch, int beg)
if (beg >= ch.Length - 1 | ch == "\0")
Console.WriteLine();
Console.Write(ch + " ");
chPrint(ch, beg + 1);
Первый параметр метода char ch - ссылка на обрабатываемый символьный массив. Второй параметр int beg - индекс элемента, начиная с которого выводятся значения. Условие выхода из метода - достижение конца массива beg >= ch.Length-1 или значение "\0" элемента с индексом beg. Если условие выхода не достигнуто, выполняются операторы:
Console.Write(ch + " ");
chPrint(ch, beg + 1);
Тем самым первым выводится значение начального элемента массива и происходит самовызов метода для следующего значения второго параметра. И т.д....
Вызов последнего отличного от "\0" элемента массива завершает цепочку рекурсивных обращений.
Пример использования приведённых методов (09_17.cs):
static void Main09_17()
char simbols = new char;
numbers(13579, simbols);
chPrint(simbols, 0);
Результат выполнения программы:
Обратите внимание, что при обращении к методу chPrint() второй аргумент равен 0, т.е. вывод идёт с начала массива.
