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

[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?