Простецкая загвоздка с рекурсией.

[Taurus727]

В общем в справочнике такой пример рекурсии - вычисление факториала числа :

Код:

int factr (int n) {
int answer;
if (n==1) return (1);
answer = factr(n-1)*n;
return (answer);
}

Все понятно вроде логически. Но я не вижу явного изменения числа n. Разве вызов factr(n-1) изменяет переменную? Как я вижу эта функция будет бесконечно вызывать сама себя если ее не вызвать с параметром 1? Или переменная каким-то образом меняется? Или опечатка в книге? Только не бейте чайником по голове за дурацкий вопрос. Спасибо

[Алексей++]

 factr(n-1)
передаёт в функцию уменьшенное на 1 текущее значение n )

[Taurus727]

Ну а при следующем вызове? Вызываем с параметром 3. В функцию идет 2 (n-1). Дальше условие иф не проходит. Новый вызов. А переменная n все также 3. И мы опять имеем вызов с 2. Или вызов factr(n-1) уменьшает значение переменной? Непонятно тогда каким образом хм... Это ведь не присваивание.

[Алексей++]

Taurus727, не, это же не статическая переменная.

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

сначала n==5.
после нового вызова n=5-1==4
после нового вызова n=4-1==3
...

[Антон (LogRus)]

а зачем тебе изменённое n?
возвращает же функция answer

n функция получает через параметр
значит что ?
что если в первом вызове n=3, то во второй вызов n придёт равным n-1 т.е. 2
и внутри второго вызова функции она будет n=2

что бы понять рекурсию надо понать рекурсию
понятно? вот и хорошо
а теперь реализуй рекурсию на шаблонах

[Taurus727]

То есть когда передаем параметр factr(n-1) то новый вызов функции захватывает момент, когда эта переменная как бы уменьшается, копия происходит уменьшенного числа n и получается что копия переменной неявно, но уменьшилась, а на выходе из рекурсии полной по идее тогда n возвращется на первое значение? Ну и естественно разрушается при return так как она локальная...

[Taurus727]

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

[Sla]

по буквам

объявляешь функцию
int factr (int n) {
int answer;

проверяешь конец рекурсии
if (n==1) return (1);

а вот тут-то и самое интересное:
вот этот ансвер вернется самым последним
answer =
а это тоже ансвер, только не от n, а от n-1, но это таже самая функция
factr(n-1)
*n;

вот здесь возращем
return (answer);
}

и где здесь
новый вызов функции захватывает момент?

[Алексей++]

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

да всё гораздо проще )

представь, что 3 итерации рекурсии выглядят так -

Код:

factr_3(3);

//--------

int factr_3(int n)
{
  //n==3
  return factr_2(n-1);
}

int factr_2(int n)
{
  //n==2
  return factr_1(n-1);
}

int factr_1(int n)
{
  //n==1
  return factr_0(n-1);
}

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

[Taurus727]

Жесть... Вкуриваю...

[RXL]

Taurus727, здесь n - параметр ф-ии. параметры передаются по значению. Т.е. передается просто число. Т.ч. с перекуром повремени

[Taurus727]

Пардон?

[Антон (LogRus)]

Taurus727, значится так
запись
int factr(int n) говорить о том, что паремер n будет передан по значению,
что собственно это означает?
Это значит, что если ты вызовешь функцию вот таким макаром
factr(n+z+y*1024-f)
то
перед вызовом будет вычислено значение n+z+y*1024-f
затем это значение будет засуното в стек, после чего вызовится функция
функция в свою очередь(очередной) сохранённое значени в стеке(стек конкретного вызова, а не какой-то разделямый между вызовами стек) вытащит из стека и засунет в переменную n
т.е. функции пополам каким образом было вычислено переданное значение главное, что оно было засунуто в стек

теперь пример как это работает в твоей функции

первый вызов

int res = factr(3);
что тут происходит(в общем случае, без оптимизации, inline и прочей фигни)?
1. число 3 заносится в стек
2. проиходит вызов функции
3. функция вытаскивает 3 из стека и заносит в переменную n
4. функция, что-то делает
5. результат вычислений опять засовыет в стек
6. выходим из функции
7. значение из стека вытаскивается и засовывается в res

Код:

int factr (int n) {
// тут у нас n==3
int answer;
// проверяем, что n==1, если это, так, то 1 засовываем в стек и возвращаем управление
if (n==1) return (1);
/*вычисляется значение n-1==2, засовывается в стек, вызывается фунция,
она вытягивает из стека 2 засовывает в n, вычисляет результат, засовывает
в стек, возвращает управление, результат из стека вытаскивается,
умножается на n==3 и результат помещается в answer,
что происходит внутри factr(n-1) уже обяснять думаю не надо :) 
*/
answer = factr(n-1)*n;
//answer копируется в стек, и возвращается управление(выход из функции)
return (answer);
}

кстати если написать
вместо
answer = factr(n-1)*n;
return (answer);
вот это
return factr(n-1)*n;
то из бавишься от одного копирования лишнего копирования
вообще можно функцию сократить до такой

Код:

int factr (int n) {return n==1 ? 1 : factr(n-1)*n;}

[Алексей++]

>>вообще можно функцию сократить до такой

но не нужно ) Читабельность падает

[Антон (LogRus)]

Алексей1153++, для кого, как для меня она прекрастно читаема и намного проще в восприятии что то что было раньше
особенно вот в таком виде
int factr (int n)
{
    return n==1 ? 1 : factr(n-1)*n;
}
если 1, то 1, иначе посчитаем еще что-то, и всё
полностью отражает смысл без лишних переменных сравнений и прочего

[Алексей++]

LogRus, нечитабельный стиль кода - дело хозяйское, конечно, но протрассируй в дебаге вот это чудо

Код:

int factr (int n){return n==1 ? 1 : factr(n-1)*n;}

и это

Код:

int factr (int n)
{
   if(n==1)return 1;
   
   return factr(n-1)*n;
}

и ты прочувствуешь разницу )

а где там лишние сравнения, кстати ?

[Taurus727]

Запустил в debug код (в самой длинной записи ) и на каждую строку поставил точку прерывания. И проследил изменение переменных. Действительно. Все так и есть. Но боюсь  буду рекурсию использовать редко   итерация ближе моему мозгу видимо хотя посмотрим всем спасибо

[Sla]

но здесь и с кодом надо поиграться
1. уже было замечено - что будет если n достаточно большое?
   надо что-то делать
2. что будет если
   n=0?
   надо что-то делать
3. что будет если n<0 (почти п.2)
   надо что-то делать

Т.е. для правильной работы данной функции нужно вводить еще и флаг ошибки

Что будет?

int n;
res=factr(n);

n -не определена, возможно что угодно, диагностика ошибки обязательна

[Taurus727]

Ну все ошибки тут никто не ловил. Кстати даже когда вызываешь функцию с параметром 120 уже ответ выходит за границы int потом его кидает в минус. А потом возвращает 0 в итоге. Так что функция эта чисто для примера что есть рекурсия

[Антон (LogRus)]

Алексей1153++, не волнуйся я отлажусь в одной строчке
я отлажывался даже в макросе который разваричавался в фигительного размера функцию

Sla, это же функция очень похожа на C и следовательно её поведение должно быть похоже на поведение atoi

Код:

unsigned int factr (unsigned int n)
{
   return n>1 ? factr(n-1)*n : n;
}

маленькая и красивая

[Taurus727]

За вами надо в тетрадку записывать чем я и займусь.

[Алексей++]

LogRus, красиво, когда

n ? 10 : 20

а у тебя - ребячество

[Антон (LogRus)]

За вами надо в тетрадку записывать чем я и займусь.

Валяй. Тебе полезно, нам приятно.

[Джон]

Но боюсь  буду рекурсию использовать редко   итерация ближе моему мозгу видимо

"Итерация свойственна человеку, рекурсия божественна."
Л. Питер Дойч

Подожди, вот до "древесной" структуры доберёшься, там без рекурсии никуда.

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

Это дух клуба!

[nikedeforest]

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

Код:

void Paint(int x, int y, RGB col_background, RGB col_border)
{
  if(getpixel(x,y)!=col_border)
  {
     putpixel(x,y,col_background);
     Paint(x+1,y,col_background,col_borde);
     Paint(x-1,y,col_background,col_borde);
     Paint(x,y+1,col_background,col_borde);
     Paint(x,y-1,col_background,col_borde);
     Paint(x+1,y+1,col_background,col_borde);
     Paint(x+1,y-1,col_background,col_borde);
     Paint(x-1,y+1,col_background,col_borde);
     Paint(x-1,y-1,col_background,col_borde);
  }
return;
}

А также с помощью данной функции видно каким критическим ресурсом явялется стэк. Такая функция закрашивает только маленькие области . Экран с разрашением 600х800 она не зальет при всем ее желании .

[Алексей++]

>>Экран с разрашением 600х800 она не зальет при всем ее желании

а кроме того, даже если стека хватит, будет делать это медленно )

[nikedeforest]

Кстати неправда. Или точнее спросить - медленнее чем что? Алгоритм полинейной закраски не был быстрее.

[Алексей++]

nikedeforest, со стеком много работы

[Taurus727]

Простите, а getpixel() и putpixel() в какой библиотеке есть в Visual Studio 2005? Я бы ваш примерчик обкатал...

[nikedeforest]

Вы перешли на Visual Studio? Дело хозяйское, просто я начинал с Борланда 3.1. под ДОС который. Ну да ладно. А собираетесь консольное приложение делать или с GUI?

[nikedeforest]

GUI было бы лучше наверное

[Taurus727]

Пока делаю консольные без GUI чтоб не закопаться

[Алексей++]

Taurus727, заливать можно всё теми же символами )

Код:

@@@@@@
@.....@@
@@@....@@
  @@@@@

[Taurus727]

Ну да можно символами. Но нужно управление позицией курсора то с чего я свою тему до этой начинал стандартные С++ библиотеки не предоставляют средств позиционирования курсора в консоли. Есть дополнительные функции свои в каждом компиляторе. Пока не отыскал их в вс2005

[Taurus727]

А телетайпом можно и в цикле залить

[Алексей++]

Taurus727, вычисления делай в памяти, а на экран выводи результат за один раз

[Taurus727]

Массив консоли х на х символов. Вычисления заливки внутри. Вывод массива на экран в цикле? Значения в массиве грубо говоря 0 и 1 для закрашен/нет. Можно...

[Алексей++]

0...255 значение )
хотя непечатные есть )))

[Taurus727]

Ну это уже извращение цвет видом символа передавать в эпоху видеокарт с радиаторами размером с батарею. Вспоминается старая добрая Elite с каркасной 3d графикой. Хватит мне и 1/0 то есть ' ' или '#'

[RXL]

Taurus727, почитай "Заметки о рекурсии": https://club.shelek.ru/view.php?id=25

[Алексей++]

Taurus727,вспоминается вот чего ))

88888888888888888888
88888888888888888888
88888888888888888888
88888888888888888888
88888888888888888888
88888888888888888888
88888888888888888888
88888888888888888888
88888888888888888888
88888888888888888888

[Taurus727]

Кстати там в статье есть опечатка. Надо вам ее исправить. Цитата:
Но не будем спешить с выводами. На самом деле  есть очень много примеров, подобных вышеприведенному, в которых применение рекурсии просто расточительно и е выдерживает никакой конкуренции с рекурсией.

[Taurus727]

Сие есть "игра" Жизнь насколько я помню

[Алексей++]

Taurus727, о, кстати, вот те и задачки интересная ) Напиши жизню )

[nikedeforest]

Ладно, поржали и хватит
ЕХЕшник в папке release прикрепленнеого архива. В файле pouring.cpp увидишь функцию Paint - само рисование. Там некоторые изменения. Во-первых передается параметр HDC hdc - это контекст устройства, типа указателя на устройство, на которое хочешь вывести пиксель и т.п. Это может быть монитор, принтер и т.п.
Еще вместо цвета коемки я в нее решил передавать старый цвет пикселя (в нашем случае белый). Как ты думаешь почему?
Теперь смотри на  функцию LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam).
Я вносил изменения в

Код:

case WM_LBUTTONDOWN:
		isLButtonDown=TRUE;		
		break;
	case WM_LBUTTONUP:
		isLButtonDown=FALSE;
		break;
	case WM_MOUSEMOVE:
		
		if(isLButtonDown)
		{
			
			COLORREF color_border=RGB(0,255,0);			
			POINTS pt=MAKEPOINTS(lParam);
			int x = pt.x;
			int y = pt.y;
			hdc=GetDC(hWnd);
			   SetPixel(hdc,x,y,color_border );
			   SetPixel(hdc,x+1,y,color_border );
			   SetPixel(hdc,x-1,y,color_border );
			   SetPixel(hdc,x,y+1,color_border );
			   SetPixel(hdc,x,y-1,color_border );
			   SetPixel(hdc,x+1,y+1,color_border );
			   SetPixel(hdc,x+1,y-1,color_border );
			   SetPixel(hdc,x-1,y+1,color_border );
			   SetPixel(hdc,x-1,y-1,color_border );
			   ReleaseDC(hWnd,hdc);
		}
		break;

	case WM_RBUTTONUP:
		{
		POINTS pt=MAKEPOINTS(lParam);
		hdc=GetDC(hWnd);
			int x = pt.x;
			int y = pt.y;
			COLORREF old_col=GetPixel(hdc,x,y);
		Paint(hdc,x,y,RGB(0,255,255),old_col);
		ReleaseDC(hWnd,hdc);
		}
		break;

Посмотри на case WM_RBUTTONUP. Этот case выпадает когда возникает сообщение, что отпущена правая кнопка мыши. В принципе, раз кнопка отпущена, значит она была и нажат, поэтому будем считать, что клик мыши был (не рассматриваем изврат, что нажатин было вне нашего окна, а отпущено над нашим окном). Как только ты отпустил правую конпку мыши, вычисляются координаты Х, У над которыми была отпущена кнопка и вызывается наша функция зарисовки. Дальше вроде не очень надо, но если что-то станет непонятно, то спрашивай.
WM_MOUSEMOVE - это сообщение о том, что мышь движется.
Для того, чтобы поиграться. Запускаешь ЕХЕшник жмешь левую кнопку и водишь по окну, только быстро не води, а то пробелы будут (надо было точки линией соединять ). Чтобы залить область нажми правую кнопку мыши.

[nikedeforest]

Здесь ЕХЕшник

[Taurus727]

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

[nikedeforest]

Там не так много на смамом деле. Забыл лишнее выкинуть. СALLBACK функции служат как бы для обработки сообщений. Функция WNDPROC вызывается как только твоя программа получилав сообщение (а она их получает кучу). Как только сообщение получено, мы сморим в тело сообщения, чтобы выделить какие нас интересет. А вот внутри switch как раз написано, что делать в случае, если возникло интересующее нас сообщение. Мы описываем действия на интересующие нас сообщения, другие же просто игнорируются программой. В итоге что сделал я. Взвожу флаг в случае нажатия левой кнопки мыши. В случае отжатия этой кнопки, флаг становится равным false. ПРи движении мыши я смотрю взведен ли флаг, если взведен, значит по сути пользователь нажал левую кнопку мыши и водит мышью по окну (по логике программы он хочет рисовать). Делаю вывод, что надо рисовать, что и происходит в обработчике события WM_MOUSEMOVE. Ну и заливаем при нажатии правой кнопки мыши.