На занятии в будущую субботу, разбирая внутреннюю жизнь стека вызовов, мы затронем тему рекурсии. Я люблю рекурсию - на мой взгляд, она делает программу красивее, а местами - понятнее. Поэтому предлагаю для закрепления материала сделать небольшую программку.
Когда я искал аналогии для объяснения смысла рекурсии, мне в голову пришел пример расшифровки названия PHP (кто не знает - погуглите). Соответственно, напишите мне консольную программку на C#, которая печатает следующий текст:
10 раз. Сделайте это не циклом, а рекурсивным вызовом функции (а отдельные красавцы и красавицы могут сделать и циклом, и рекурсией). Листинги публикуйте тут в камментах или приносите распечатанными на следующее занятие, обсудим.
Я бы предложил ещё красавцам и отдельно предложил бы красавицам присылать свои проекты на progelectivecource@gmail.com! Так быстрее проверим и дадим ответ с описанием проблем (если они там будут) :)
ОтветитьУдалитьМне кажется, что классический пример факториала - это одно из самых наглядных объяснений рекурсии. И правда, 3! = 3 * 2! = 3 * 2 * 1! = 3 * 2 * 1 * 0!, а 0! - это базовый случай. Таким образом, эта функция может быть определена через саму себя естественным образом. Вообще, здесь интересно поговорить и о таких фундаментальных вещах, как ряды и производяющие функции... или перебор? но ведь жутко интересно :)
ОтветитьУдалитьМиша, мы это оставим до твоего курса по прикладным алгоритмам. Я согласен, что рекурсивные алгоритмы и все, что вокруг них - очень сладкая тема. Но пока я хотел бы что-то не слишком математическое, чтобы пощупать было проще. Через полгодика раскопаем эту темку поглубже с теми, кто выживет :)
ОтветитьУдалить#include
ОтветитьУдалитьvoid answer(int i);
void question(int i){
if(i==0)
std::cout << "Yes, but...\n";
else
{
std::cout << "What' is PHP? \n";
answer(--i);
}
}
void answer(int i){
if(i==0)
std::cout << "Ok, ok! Hipertext Preprocessor!!! \n";
else
{
std::cout << "Parents Help Parents! \n";
question(i);
}
}
void main()
{
question(10);
}
#include "iostream"
ОтветитьУдалитьvoid main();
void _recursive(int i);
void _recursive(int i)
{
if (i >= 1)
{
std:: cout << "\n" << i << " What is it GNU?";
std:: cout << "\n GNU's Not Unix";
i --;
_recursive(i);
}
else
{
std:: cout << "\n Recursive is complete";
}
}
void _cycle(int i)
{
for (int k = 1; k <= i; k++)
{
std:: cout << "\n" << k << " What is it GNU?";
std:: cout << "\n GNU's Not Unix";
}
}
void main()
{
int i, j;
std:: cout << "Choose the type of recursion: ";
std:: cin >> j;
std:: cout << "Enter the depth of recursion: ";
std:: cin >> i;
switch (j)
{
case 1:
_recursive(i);
break;
case 2:
_cycle(i);
}
}
#include "iostream"
ОтветитьУдалитьvoid talk(int n){
std::cout << "What Abbreviation PHP mean?\n";
if(--n == 0)
std::cout << "Ok, It's means Hypertext Preprocessor\n";
else
{
std::cout << "Parents Help Parents\n";
talk(n);
}
}
void main(){
talk(10);
}
Wow! Все сделали и даже правильно. Коля отличился и сделал сразу 2 варианта! Жаль что остальные не отреагировали, или отреагировали? :)
ОтветитьУдалитьМне понравились реализации Нико и второй вариант от HedG (первый вариант был очень своебразным, и никак не делал программу читаемой). Только вы себе несколько упростили задачу - если вы посмотрите, в моем примере еще идет игра с формулировками в тексте: они разные на первом, последнем и остальных шагах. Сможете это реализовать?
ОтветитьУдалитьВторой вариант от HedG нужно, конечно, исправлять. Во-первых, он зацикливается при параметре n <= 0. Во-вторых, уменьшение параметра в условии проверки - это плохой стиль, мягко говоря. Намного логичнее уменьшать его при рекурсивном вызове - например n--; talk(n) или, если уж сильно хочется, talk(--n)
ОтветитьУдалить// Ребят, Вы меня конечно ж, простите за мои глупые выдумки..
ОтветитьУдалить#include
int rec(int m)
{
int d;
if (m >= 0)
{
printf("%s\n", "My rec function...");
d = rec(--m);
}
return d;
}
int main()
{
int s;
s = rec(10);
scanf("%d", s);
}
//Извиняюсь, сначала не то скопировал )
ОтветитьУдалить#include
int a;
int rec(int m)
{
int d;
if (m >= 0)
{
if (a) {
printf("%s\n", "What is it??");
}
else { printf("%s\n", "It is HARD PROGRAMMING!!!"); }
if (a) { a = 0; } else { a = 1; }
d = rec(--m);
}
return d;
}
int main()
{
a = 1;
int s;
s = rec(10);
scanf("%d", s);
}
Согласен, код ужасен -- появится время, попробую подправить.. я хотел лишь добиться возможности возвращать функцией 0 при успешном прохождении всех стадий рекурсии, и другого значения при противоположном варианте. Это очень удобно, особенно когда нужно знать результат выполнения, не используя глобальных переменных и вывода на экран. Что бы вызвать функцию, и лишь проверить возвращенное значение... Тем не менее -- до конца пока не довел.. как только будет время -- доделаю ;)
ОтветитьУдалитьДорогой Blook, я бы не совмещал рекурсию с использованием глобальных переменных. Вернее, даже не так: я бы не передавал данные из одного вызова функции в другую через глобальную переменную. Это т.н. "плохой стиль", т.к. чревато неожиданными побочными эффектами - в любом месте программы есть доступ к этой переменной на изменение, и если кто-то случайно ее тронет, то код "посыпется". Особенно это важно в больших программах. Поэтому лучше не привыкать так делать. Передавайте параметры как аргументы функции, задумываясь при этом о наболее обоснованном в данном случае способе передачи (по ссылке или по значению), учитывая как соображения производительности, так и защиты переменных от случайной правки.
ОтветитьУдалитьДенис, именно этого я хотел первоначально избежать (глобальных переменных). Т.е. что бы результат всех стадий рекурсии возвращался после вызова рекурсивной функции.. Это черновой вариант.. Придумаю как только найду время...
ОтветитьУдалитьочень удобно было бы:
if (!(rec(x))) //вызов рекурсивной функции
{
printf("%s\n", "YES! rec is complete")
}
else { ... }
Уважаемый Blook. Какова цель в том, чтобы возвращать в качестве результата работы рекурсивной функции факт ее завершения? Сегодня, для того, чтобы указать программе, что успешно вызов не завершился - возбуждается исключение. А, скажем, если нужно иметь функцию суммирования всех чисел до n (например, при n = 5 вернется 1+2+3+4+5=15), то ее естественно написать в виде рекурсивной функции с сигнатурой int sum(int n), где возвращаемое значение int - есть искомая сумма. Если сильно нужно в вашем примере - передавайте а в качестве второго параметра.
ОтветитьУдалитьМихаил, дело привычки (не спорю, возможно вредной) -- в большинстве программ на Си, что я встречал успех выполнения какой-либо задачи проверялся именно таким образом... например в библиотеке WinPcap:
ОтветитьУдалитьif(pcap_setfilter(adhandle, &fcode)<0){
fprintf(stderr,"\nError setting the filter.\n");
Как Вы считайте, считается ли такой стиль "правильным"?
(Он очень часто встречается)
Blook, это не то, чтобы стиль, - в случае Си - это один из немногих способов передачи информации об ошибке, т.к. в Си нет стандартного механизма исключений (хотя можно найти реализации). Важно, что функция должна сообщать об ошибке, когда это спроектировано, но далеко не в каждом случае. Если есть возможность использовать исключения, то стиль возврата кодов ошибок неправильный и может быть оправдан в случае крайних требований к производительности, когда на счету каждый такт, либо в каких-то случаях, связанных с совместимостью. В данном примере я не вижу никакой необходимости сообщать об ошибке, тем более, что это нигде не обрабатывается. И, конечно, все современные программы используют исключения и важно уметь с ними работать.
ОтветитьУдалитьПлюс, это не имеет отношения к рекурсии.
// мой вариант
ОтветитьУдалить#include
void recursion(int count){
if(count >= 10){
std::cout << "What does PHP mean?\n";
}
else
if(count <= 0){
std::cout << "Ok, but...\n";
return;
}
else
{
std::cout << "Ok, but what does PHP mean?\n";
}
std::cout << "PHP: Hypertext Preprocessor\n";
recursion(--count);
}
void main(){
recursion(10);
return;
}
#include
ОтветитьУдалитьvoid Rec(int num){
std::cout << "What is PHP? \n";
std::cout << "PHP: is PHP! \n";
if (num>=1)
Rec(--num);
}
void Cycle(int num){
for (int i = num; i>=1; i--){
std::cout << "What is PHP? \n";
std::cout << "PHP: is PHP! \n";
}
}
void main(){
Rec(10);
std::cout << "\n\t End Rec \n\n";
Cycle(10);
std::cout << "\n\t End Cycle \n\n";
}
\\Мой вариант
ОтветитьУдалить#include
void rec(int recur){
if (recur<10){
std::cout << "What is PHP?\n";
std::cout << "PHP: is Hypertext preprocessor!\n";
}
if (recur=10){
std:: cout << "Yes, but \n";
}
recur++;
return;
}
Я тоже решил написать свой вариант, если не подзно.
ОтветитьУдалить#include "stdafx.h"
#include "iostream"
void whatdoesphpmean(int n)
{
if (n > 0) {
std::cout << "What does PHP mean?\nPHP: Hypertext preprocessor.\n";
whatdoesphpmean(--n);
} else {
std::cout << "Ok, but...";
}
}
int main()
{
whatdoesphpmean(10);
return 0;
}
А, и кстати вот такая реализация с разными первыми и последними фразами.
ОтветитьУдалитьХотелось бы узнать насколько она правильная.
#include "stdafx.h"
#include "iostream"
void whatdoesphpmean(int n)
{
std::cout << "PHP is Hypertext preprocessor.\n";
if (n > 1) {
std::cout << "Yes, but what does PHP mean?\n";
whatdoesphpmean(--n);
} else {
std::cout << "Yes, but...";
}
}
int main()
{
std::cout << "What does PHP mean?\n";
whatdoesphpmean(10);
return 0;
}
Если она работает - значит, она правильная :) Я могу свою показать, правда, она на C# - другого под рукой не было.
ОтветитьУдалитьstatic string CreateText(string FirstLetter, int Count)
{
if (Count > 10)
return "...";
else
return FirstLetter + "то такое PHP?\nPHP: Hypertext Preprocessor\nДа, но " + CreateText("ч", ++Count);
}
static void Main(string[] args)
{
string Text = CreateText("Ч", 1);
Console.WriteLine(Text);
Console.ReadKey();
}
Этот комментарий был удален автором.
ОтветитьУдалитьНу вот как-то так (и рекурсия, и цикл):
ОтветитьУдалить#include "iostream"
void recurs (int cnt)
{
if (cnt<=10)
{
std::cout << "What is PHP?\n";
std::cout << "PHP: Hypertext Preprocessor\n";
cnt++;
recurs(cnt);
}
else
{
std::cout << "Ok! Hypertext Preprocessor!";
}
}
void cikl (int cnt)
{
for (int k=10; k>=cnt; k--)
{
std::cout << "What is PHP?\n";
std::cout << "PHP: Hypertext Preprocessor\n";
}
std::cout << "Ok! Hypertext Preprocessor!";
}
void main()
{
int key;
std::cout << "Viberite tip povtoreniya: [1] - Recursiya, [2]- Cikl: ";
std::cin >> key;
switch (key){
case 1: recurs(1);
break;
case 2: cikl(1);
break;
default: std::cout << "ERROR!" ;
break;
}
}
Кстати у Егора есть такая вот загвоздка, там она как мне кажется вообще не должна была откомпилироваться. Там main - void а он возвращает int - должо было ругнутся. Егор, ты проверял?
ОтветитьУдалитьУ меня там int main. Вроде всё ок :) По-крайней мере, всё отлично работет.
ОтветитьУдалитьСтандарт вовсе запрещает использование конструкции void main (насколько я знаю) - тем не менее, VS без проблем компилирует код на С++, даже встречая ее. Компилятор же gcc всегда ругается и отказывается компилировать такой код.
ОтветитьУдалитьОк, ещё раз пробежался взглядом - да всё ok. Стандарт не запрещает - да, это я знаю, однако мне на глаза вроде бы как попался return в void ф-ции тока вот перечитав я понял что надо проспаться :)
ОтветитьУдалить