Форум программистов, компьютерный форум CyberForum.ru

Рекурсия: вычисление суммы ряда - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Win32API http://www.cyberforum.ru/cpp-beginners/thread294887.html
Как делать анимацию в Win32API ? можно обяснить ето на небольшом примере?
C++ Как удалить первый элемент из std::list? Скажите как удалить первый элемент из лист ругается вот как 181 C:\Documents and Settings\Loner\Рабочий стол\5.37\Bin.cpp 'class std::list<unsigned char, std::allocator<unsigned char> >' has no member named 'next' http://www.cyberforum.ru/cpp-beginners/thread294882.html
Дан одномерный массив A[N]. Найти max(a2,a4,...a2*k)+min(a1,a3,...,a2*k+1 C++
Дан одномерный массив A. Найти max(a2,a4,...a2*k)+min(a1,a3,...,a2*k+1=-O)
C++ свой строковой тип
помогите пожалуйста разобраться со строковым типом! пишу свой класс строки, запнулся на реализации оператора + есть вот такие виды операторов + и = void operator =(const WCHAR *val); void operator =(const MyStr &val); const MyStr operator +(const WCHAR *val); const MyStr operator +(const MyStr &val); теперь пишу следующее: MyStr s; s=L"Привет ";
C++ Определить, сколько среди чисел меньших К, равных К и больших К http://www.cyberforum.ru/cpp-beginners/thread294862.html
Задана последовательность из N вещественных чисел. Определить, сколько среди них чисел меньших К, равных К и больших К.
C++ Сортировка слов по алфавиту с ипользованием классов Есть задание - написать программу, которая бы сортировала слова в строке по алфавиту. У меня есть такой вот алгоритм. Надо его усовершенствовать так, что бы он сортировал еще и русские слова, а так же использовать классы. #include <string> #include <iostream> using namespace std; string sorting(string str) { int k=0; //считаем пробелы подробнее

Показать сообщение отдельно
ValeryLaptev
Эксперт C++
1004 / 783 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
13.05.2011, 19:06     Рекурсия: вычисление суммы ряда
Вот тебе ликбез.

Рекурсивные функции
Язык C++ предоставляет возможность написания рекурсивных функций, однако целесообразность применения рекурсии оставляется на усмотрение программиста. Как правило, рекурсивные алгоритмы применяются там, где имеется явное рекурсивное определение обрабатываемых данных. Не будем отступать от традиции и рассмотрим функцию факториала n!. Как правило, в программировании её определяют как произведение первых n целых чисел:
n! = 1 * 2 * 3 * ... * n
Такое произведение можно легко вычислить с помощью итеративных конструкций, например, оператора цикла for (листинг 7.14).
C++
1
2
3
4
5
Листинг 7.14. Итеративная функция вычисления факториала
long Fact(int k)
{ long f; int i;  for(f = 1, i = 1; i<k; i++) f*= i;
  return f;
}
Однако существует также другое (математическое) определение факториала, в котором используется рекуррентная формула и которое имеет такой вид:
0! = 1
n > 0 n! = n*(n-1)!
Если для факториала первое (итеративное) определение может показаться проще, то для чисел Фибоначчи рекурсивное определение
F(1) = 1,
F(2) = 1,
 n > 2 F(n) = F(n-1) + F(n-2)
выглядит для вычислений гораздо лучше, чем прямая формула.
Понятно, что организовать вычисления по рекуррентным формулам можно и без использования рекурсии. Однако, как видно на примерах, представленных в [Шалыто-Программист], преобразование естественной рекурсивной формы в итеративную – довольно сложная задача. Использование рекурсии позволяет легко (почти автоматически) запрограммировать вычисления по рекуррентным формулам. Например, рекурсивная функция для вычисления факториала n! имеет следующий вид (листинг 7.15).
C++
1
2
3
4
5
Листинг 7.15. Рекурсивная функция вычисления факториала
long Fact(int k)
{ if (k==0) return 1;
  return (k*Fact(k-1));     // рекурсивный вызов !
}
Аналогично, по указанному определению легко написать функцию вычисления чисел Фибоначчи (листинг 7.16).
C++
1
2
3
4
5
Листинг 7.16. Рекурсивная функция вычисления чисел Фибоначчи
long Fibo(int k)
{ if ((k==2)||(k==1)) return 1;
  return (Fibo(k-1)+Fibo(k-2)); // рекурсивный вызов !
}
Рекурсивной функцией называется функция, вызывающая саму себя в своем теле. Необходимо ещё раз подчеркнуть, что «самовызов» будет рекурсивным только в том случае, если находится в теле функции. Как мы видели ранее, «самовызов» в списке параметров не является рекурсивным.
Обычно различают прямую и косвенную рекурсию. Если в теле функции явно используется вызов той же самой функции, то имеет место прямая рекурсия (self-calling), как в приведенных примерах. Если две или более функций взаимно вызывают друг друга, то имеет место косвенная рекурсия. Обычно косвенная рекурсия возникает при реализации программ синтаксического анализа методом рекурсивного спуска.
Прекрасным примером рекурсивной функции является быстрая сортировка Хоора. Сама схема алгоритма является рекурсивной, поэтому написать итеративную программу достаточно сложно, что можно увидеть в книге Н.Вирта [9] и в [30]. Схема функции выглядит так:
C++
1
2
3
4
5
6
void QuickSort(A, 1, n)
{  //--Выбрать разделяющий элемент с номером  1<k<n
   //--Разделить массив А относительно k-го элемента
   QuickSort(A, 1, k-1);    //-рекурсивный вызов с левой частью
   QuickSort(A, k+1, n);   //-рекурсивный вызов с правой частью
}
Есть большое количество традиционных «игрушечных» задач (ханойские башни, расстановка ферзей и т.п.), которые анализируются в литературе [9,34] для демонстрации рекурсии. Мы не будем на них останавливаться — гораздо интереснее рассмотреть типично итеративные алгоритмы, которые можно представить рекурсивным образом. В принципе, любой цикл можно заменить эквивалентной рекурсивной программой. В качестве примера рассмотрим рекурсивную реализацию (листинг 7.17) функции вычисления длины строки (см. листинг 3.11).
C++
1
2
3
4
5
Листинг 7.17. Рекурсивная функция вычисления длины строки
unsigned int Length (char *s)
{ if (*s==0) return 0;      // можно просто !(*s)
  else return 1+Len(s+1);
}
Вызов такой функции абсолютно ни в чём не отличается от вызова аналогичной итеративной, например:
C++
1
cout<<Len(1234567890);
на экран совершенно правильно выводится 10. Работа рекурсивных функций обычно имеет несколько «мистический» оттенок, поэтому не будем пока в деталях разбирать работу этой функции, но обратим внимание на несколько важных моментов:
1. Цикла в функции нет – вместо него у нас имеется рекурсивный вызов. Таким образом, явное повторение заменяется неявным – рекурсивным.
2. Параметр, который является указателем, в рекурсивном вызове увеличивается, перемещаясь к следующему символу.
3. Чтобы такое увеличение не происходило до бесконечности, имеется в наличии условие окончания рекурсии — в операторе if проверяется достижение конца строки.
Эту же функцию можно написать несколько иначе:
C++
1
2
3
4
unsigned int Length (char *s)
{ if (*s) return 1+Len(s+1);
  else return 0;
}
И здесь мы наблюдаем те же три перечисленных выше особенности:
1. Вместо цикла имеется рекурсивный вызов;
2. Параметр в рекурсивном вызове изменяется;
3. Условие окончания заменено условием продолжения.
Прежде, чем делать выводы, рассмотрим еще один пример – последовательную обработку файла. Пусть открытие и закрытие файла выполняются в главной программе, а обработка – в отдельной функции, которая последовательно читает записи файла и обрабатывает их. Традиционно такая обработка выполняется в цикле следующего вида:
C++
1
2
3
4
while (не конец файла)
{   //-- читать запись
    //--обработать запись
}
Попробуем написать рекурсивную процедуру без использования цикла. Пусть потоковая переменная имеет имя f. Файл представляет собой файл строк – исходный текст самой этой программы, который находится в том же каталоге, что и исполняемая программа (листинг 7.18).
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Листинг 7.18. Рекурсивная функция обработки текстового файла
void ReadFile(ifstream &f)
{  char s[100];         //--буфер для строки    
    getline(f,s);           //--читаем строку   
    cout<<s;                //--обработка строки
    if (!f.eof())           //-пока не конец файла 
        ReadFile(f);        //--рекурсивный вызов
}
int main(void)
{   ifstream f("recurs.cpp");
    ReadFile(f);
    f.close();
    return 0;
}
Как мы видим, функция ReadFile несколько отличается от приведенных выше функций – отсутствует явное изменение параметра. Параметр-то все равно изменяется, но неявно — как состояние потока f при чтении. Как и в предыдущих случаях, цикл заменен рекурсивным вызовом, и присутствует условие продолжения.

Формы рекурсивных функций
В общем случае любая рекурсивная функция Rec включает в себя некоторое множество операторов S и один или несколько операторов рекурсивного вызова Rec. Как мы видели на примерах, рекурсивный вызов обязательно сопровождался некоторым условием: либо условием окончания, либо условием продолжения. Это понятно, поскольку безусловные рекурсивные вызовы приводят к бесконечным процессам – они сродни бесконечному циклу. Вспомните детский стишок «У попа была собака…» — это как раз случай бесконечной рекурсии. Если реализовать вывод этого стишка как рекурсивную функцию, то она может выглядеть так.
C++
1
2
3
4
5
6
void PriestAndDog(void)                           
{   сout<<“У попа была собака, он ее любил.”;   
    сout<<“Она съела кусок мяса, он ее убил,”;  
    сout<<“вырыл яму, закопал и на камне написал:;       
  PriestAndDog();                                   
}
Теоретически работа этой функции никогда не завершится. На практике программа закончится аварийно по причине переполнения стека (кто хочет – может проверить). Следовательно, главное требование к рекурсивным функциям заключается в том, что вызов рекурсивной функции должен выполняться по условию. Это условие прописывается в операторе if и может быть либо условием продолжения, либо условием окончания. В первом случае в if пишется рекурсивный вызов, во втором — оператор возврата.

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

Структура рекурсивной функции может принимать три разных формы (используем условие продолжения):
- форма с выполнением действий до рекурсивного вызова (на рекурсивном спуске):
C++
1
void Rec(void) { S; if (условие) Rec(); }
- форма с выполнением действий после рекурсивного вызова (на рекурсивном возврате — подъеме):
C++
1
void Rec(void) { if (условие) Rec(); S; }
- форма с выполнением действий как до (на рекурсивном спуске), так и после рекурсивного вызова (на рекурсивном возврате):
C++
1
void Rec(void) { S1; if (условие) Rec(); S2; }
В образцах указан заголовок
C++
1
void Rec(void)
поскольку в данном случае нам важно было продемонстрировать именно формы рекурсивных функций, не отвлекаясь на другие детали. Названия «рекурсивный спуск» и «рекурсивный подъем» связаны с понятием глубины рекурсии (см. далее) – функция спускается на глубину рекурсии и поднимается «оттуда».
Функция вычисления факториала написана в первой форме. Нам удалось написать вторую форму функции, вычисляющей длину строки. Аналогично, поменяв условие, можно преобразовать и функцию вычисления факториала (листинг 7.19).
C++
1
2
3
4
5
Листинг 7.19. Вторая форма рекурсивной функции вычисления факториала
long Fact(int k)
{ if (k>0) return (k*Fact(k-1));        // рекурсивный вызов !
  else     return 1;    
}
Однако переделать функцию чтения файла нам так просто не удастся. Попытка в «лоб» не приносит успеха:
C++
1
2
3
4
5
6
7
void ReadFile(ifstream &f)
{  char s[100];         //--буфер для строки    
    if (!f.eof())           //-пока не конец файла 
        ReadFile(f);        //--рекурсивный вызов 
    getline(f,s);           //--читаем строку   
    cout<<s;                //--обработка строки
}
Функция становится бесконечной. Конец файла никогда не достигается, поскольку до рекурсивного вызова не выполняется операция чтения. Это наводит на мысль о возможности преобразования данной функции в третью форму – чтение строки выполнять до проверки условия, а вывод строки – после рекурсивного вызова. Попробуем и посмотрим, что получится.
C++
1
2
3
4
5
6
7
void ReadFile(ifstream &f)
{  char s[100];         //--буфер для строки    
   getline(f,s);            //--читаем строку       
   if (!f.eof())            //-пока не конец файла 
        ReadFile(f);        //--рекурсивный вызов 
   cout<<s;             //--обработка строки
 }
Функция работает, но совсем не так как, ожидалось. Строки файла выводятся на экран в обратном порядке! Таким образом, для некоторой рекурсивной задачи подходит отнюдь не любая форма рекурсивной функции. Можно сказать, что для всякой рекурсивной задачи существует естественная для нее форма рекурсивной функции.
 
Текущее время: 23:42. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru