рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Recursive factorials

Recursive factorials - раздел Философия, Unit 3. Recursion 3.1 The Basic Concept Of Recurs...

Unit 3. Recursion 3.1 The Basic Concept of Recursion 3.2 Problem Solving with Recursion
Recursive Functions A recursive function is a function that calls itself. The use of recursive functions, called recursion, can yield elegant solutions to otherwise complex problems. C++, like many other programming languages, supports recursion. A programmer must define recursive functions carefully in order to avoid creating a function that repeatedly calls itself forever. A pseudocode version of a typical recursive function looks like the following example. if (simplest case) then solve directly else make recursive call to a simpler case Example 1 A typical recursive function A key to creating and using effective recursive functions is learning to think of a problem in terms of a similar, but smaller problem. Eventually, a problem becomes small enough that a function can solve it without using recursion. This is called the base case. Calculating factorials is one example of a problem that we can solve using recursion. The factorial of a number is the product of all the integers from that number to one. For example, the factorial of five (often called "five factorial") equals 5 * 4 * 3 * 2 * 1. This evaluates to 120. Three factorial (3 * 2 * 1) equals the value 6. An exclamation point denotes the factorial of a number. Thus, "five factorial" can be expressed as 5!. Example 2 lists some of the first several positive integers and the calculation of their factorials. The factorial for zero is a special case and is defined to equal 1. 5! = 5 * 4 * 3 * 2 * 1 = 120 4! = 4 * 3 * 2 * 1 = 24 3! = 3 * 2 * 1 = 6 2! = 2 * 1 = 2 1! = 1 0! = 1 Example 2 Some factorials We can express factorials recursively, that is, in terms of other factorials. Consider the factorial calculation for the value 5. From Example 2, the calculation is 5! = 5 * 4 * 3 * 2 * 1. But, from examining the factorial calculation for 4, we know that 4! = 4 * 3 * 2 * 1. Recursively then, 5! = 5 * 4!. Example 3 lists the recursive definitions of the same numbers from Example 2. Since we cannot express zero factorial recursively, it is the base case. 5! = 5 * 4! 4! = 4 * 3! 3! = 3 * 2! 2! = 2 * 1! 1! = 1 * 0! 0! = 1 Example 3 Recursive factorials Listing 1 contains C++ code that recursively calculates factorials. Notice that function factorial follows the recursive function pattern outlined in Example 1.
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: #include <iostream> #include <cstdlib> #include <string>   using namespace std;   int factorial(int n) {   if (n == 0) { // base case return 1; } else { // recursive call int value = factorial(n - 1); return n * value; } }   int main(int argc, char* argv[]) {   cout << factorial(5) << endl; return EXIT_SUCCESS; }
Listing 1Calculating a factorial recursively

Execution of the program in Listing 1 outputs the expected value of 120. We know this is correct, but how did the function achieve this result? Adding output statements to function factorial gives us a better idea how this example works. Listing 2 contains an updated function factorial that outputs a line indicating when an instance of the function begins and when an instance of the function is about to end. This modified version also outputs the return value of function factorial.

1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: int factorial(int n) {   cerr << "factorial(" << n << ") begin" << endl;   if (n == 0) { cerr << "factorial(" << n << ") returns 1" << endl; return 1; // base case } else { int ret = n * factorial(n - 1); // recursive call cerr << "factorial(" << n << ") returns " << ret << endl; return ret; } }
Listing 2A verbose function factorial

Example 4 contains the output of the factorial program after the addition of the output statements to function factorial.

factorial(5) begin factorial(4) begin factorial(3) begin factorial(2) begin factorial(1) begin factorial(0) begin factorial(0) returns 1 factorial(1) returns 1 factorial(2) returns 2 factorial(3) returns 6 factorial(4) returns 24 factorial(5) returns 120
Example 4 Output of Listing 2

The output in Example 4 shows that the program first calls function factorial with the argument 5. Function main performs this initial call. During the execution of factorial(5) it makes a call to function factorial with an argument value of 4. The instance of factorial(4) then begins execution and makes a call to factorial(3), which in turn makes a call to factorial(2). This behavior continues until factorial(0) begins and returns the value 1. After this, factorial(1) returns to factorial(2) the value 1, factorial(2) returns to factorial(3) the value 2, and so on until factorial(5) returns to main the value 120.

The Call Stack

Stepping through the function calls in Listing 3 demonstrates how a program uses the call stack to manage the function calls in a program. As in… Figure 1 The call stack during various… When main calls function method1, the run-time system pushes an activation record for method1 onto the top of the…

Removing Recursion

For example, the following loop-based factorial function is guaranteed to execute faster and consume less memory (in the call stack) than the… It is always possible to eliminate recursion, and it is worthwhile to think…  

Problem Solving with Recursion

Divide and Conquer

Figure 1 Dividing a problem Generally, divide and conquer algorithms utilize two recursive function… Figure 2 The combined solution

Backtracking. The Concept

Figure 1 A maze Backtracking involves pursuing one possible solution until the algorithm… Backtracking algorithms that use recursion operate basically the same way as other recursive algorithms. Similar to…

The Problem

The game of chess is played on a board containing 64 squares of alternating color. Two players take turns moving a set of pieces on these squares.… Figure 2 Queens attack in two different ways Combining these two methods together, we see (again in red) all the squares on a chessboard that a queen can attack…

The Solution

Figure 6 Seven queens placed, but we must backtrack The backtracking portion of the algorithm would then attempt to move the… The above implementation of the Eight Queens problem outputs the first solution it finds and then terminates. As an…

The Call Stack

Продвижение посредством вызовов функции в листинге 3 демонстрирует, как программа использует стек вызовов, чтобы управлять вызовами функции в… Figure 1 The call stack during various points of Listing 3 Когда main функция вызывает method1, система времени выполнения вталкивает активацию записи method1 на вершину стека…

Замена рекурсии

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

Решение задач с Рекурсией

Разделяй и властвуй

Последовательность разделяй и властвуй использует рекурсию, чтобы решать проблемы, "деля" задачу на меньшие подзадачи. Base case рекурсии решает группу самых маленьких подзадач. "Властвовать" часть этой проблемы, которая происходит когда метод комбинирует эти решения создавая решение исходной проблемы.


Рисунок 1 Разделение проблемы

Обычно, алгоритмы «разделяй и властвуй» используют два вызова рекурсивной функции. Наличие двух рекурсивных вызовов непрерывно делит пространство задач на две части. Рисунок 1 иллюстрирует типичный шаг "дележа", который использует два рекурсивных вызова. Когда рекурсия достигает base case, подзадача решается непосредственно. Решения этих подзадач объединяются вместе (поскольку рекурсия раскручивается), и в конечном счете обеспечивают решение исходной проблемы. Рисунок 2 показывает решенные подзадачи, объединенные в решение для исходной проблемы.

 


Рисунок 2 объединенное решение

Рассмотрим проблему вычисления суммы квадратов диапазона целых чисел. Мы можем применить разделение и использовать подход, чтобы уменьшать диапазон непрерывно, пока мы не достигаем подзадачи размера, который легко вычисляется. Листинг 1 содержит исходный код для этого рекурсивного, основанного алгоритма разделяй и властвуй.

1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: #include <iostream> #include <cstdlib>   using namespace std;   int ssq(int m, int n) {   if (m == n) { return m * m; // base case } else { int middle = (m + n) / 2; // recursive divide return ssq(m, middle) + ssq(middle + 1, n); } }   int main(int argc, char* argv[]) {   cout << "ssq(1,10) = " << ssq(1, 10) << endl;   return EXIT_SUCCESS; }
Listing 1Finding the sum of the squares of a range of integers

Другой пример простого и эффективного алгоритма разделяй и властвуй, приведен в листинге 2.

1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: #include <iostream> #include <cstdlib>   using namespace std;   int find_smallest(int a[], int size) {   if (size == 1) { return a[0]; // base case } else {   // Search the first half of the array for the smallest element. int s1 = find_smallest(a, size / 2);   // Search the second half of the array for the smallest element. int s2 = find_smallest(a + size / 2, size - size / 2);   return (s1 < s2) ? s1 : s2; } }   int main(int argc, char* argv[]) {   int arr[] = {13, 19, 12, 11, 15, 19, 23, 12, 13, 22, 18, 19, 14, 17, 23, 21};   cout << "smallest: " << find_smallest(arr, 16) << endl;   return EXIT_SUCCESS; }
Listing 2Finding the smallest element in an array

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

Отслеживание в обратном порядке. Понятие

Рисунок 1 лабиринт Отслеживание в обратном порядке включает преследование одного возможного… Алгоритмы «отслеживание в обратном порядке», которые используют рекурсию, управляет в основном тем же самым путем…

Проблема

В игру шахмат играют на доске, содержащей 64 квадрата переменного цвета. Два игрока поочередно передвигают ряд фигур по этим квадратам. Цель игры… Рисунок 2 атака Куинса двумя различными способами Комбинируя эти два метода вместе, мы видим (снова в красном) все квадраты на шахматной доске, которую королева может…

Решение

Рисунок 6, Seven queens placed, but we must backtrack Часть отслеживания в обратном порядке алгоритма тогда попыталась бы… Вышеупомянутая реализация проблем Восьми Королев выводит первое решение, которое это находит и затем завершает. Как …
Развернуть
Открыть в широком формате

– Конец работы –

Используемые теги: Recursive, factorials0.054

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Recursive factorials

Что будем делать с полученным материалом:

Если этот материал оказался полезным для Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Еще рефераты, курсовые, дипломные работы на эту тему:

0.025
Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • По категориям
  • По работам