VPF::Рекурсивная функция - Форум программистов

observateur

Дата 10.6.2006, 12:48 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 176
Регистрация: 10.6.2006

Репутация: нет
Всего: нет

Заранее спасибо тем кто ответить...Самостоятолна изучаю C++. помогите пожалоста понять как работает Рекурсивная функция. Уменя есть книга Х.М.Дейтель "Как программировать на С++". Все равно трудно понять суть рекурсии. smile

Xenon

Дата 10.6.2006, 12:58 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 1529
Регистрация: 12.4.2006

Репутация: 11
Всего: 50

Что значит КАК? Ну функция из самой себя вызывает саму себя с новым аргументом smile

Удобно использовать для математических вычислений, в конце концов для вычисления факториала smile

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

Вот нахождение факториала простым способом

Код


int fact(int n)
{
    int result=1;
    for (int i=1;i<=n;i++) 
    {
        result=result*i;
    }
    return result;
}

Вот пр помощи рекрусси:

Код


int fact(int n)
{
    if (n==1) // факториал единицы равен одному
    {
        return 1;
    }
    else           
    {
        return n*fact(n-1);
    }
}

Это сообщение отредактировал(а) XenonSk - 10.6.2006, 12:58

--------------------

observateur

Дата 10.6.2006, 13:04 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 176
Регистрация: 10.6.2006

Репутация: нет
Всего: нет

Я знаю условия цикла рекурсивный функции. мне надо схема ее рабаты. Точнее схематический как она работает. спасибо за вашу терпению

AlanG

Дата 10.6.2006, 13:27 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 71
Регистрация: 11.5.2006
Где: РашЫн ФидирейшЫн

Репутация: нет
Всего: нет

Цитата

Так все спрашивают, когда начинаю smile

. Это не нужно, и вообще задумыватся над этим не надо, поверь smile

. Логика проста, как два мегабайта скачать smile

А думать о схеме не надо, вот как это происходит

Код


int fact(int n)
{
    if (n==1) // факториал единицы равен одному
    {
        return 1;
    }
    else           
    {
        return n*fact(n-1); //сдесь fact(n-1) - это вызов функции fact(), причем заметь что ему (функции fact) 
//передается агрумент в виде числа равного (n-1) и все, вся рекурсия
 //А то что return (возврат), он сразу не происходит, сначала всеже вызывается 
//функция, а вот когда n cтанет равным 1, последнему вызову возвратится результат, 
//этот результат перемножается с n (n*fact(n-1))
 
    }
}

Вообще все вызовы сохраняются в стеке, и каждому вызову присваивается значение с помощбю return

Это сообщение отредактировал(а) AlanG - 10.6.2006, 13:28

Pete

Дата 10.6.2006, 13:42 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 318
Регистрация: 5.1.2006
Где: Москва

Репутация: нет
Всего: 12

XenonSk, 0! = 1.

Код

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

На примере того же факториала:
Мы знаем рекуррентное соотношение (которое, кстати, лежит в основе каждой рекурсивной функции):
fact (n) = n * fact (n - 1).
Вот мы это и реализуем: в предположении, что наша функция вычисляет факториал, пишем, что "n! = n(n - 1)!".
При этом мы уверены, что (n - 1)! будет вычислен правильно. На основе этого получаем то, что надо.

Это сообщение отредактировал(а) Pete - 10.6.2006, 14:26

--------------------

Совет учиться на ошибках других бесполезен; научиться чему-либо можно только на собственных ошибках. (Бернард Шоу)
Не откладывай на завтра то, что можешь сделать сегодня. (Пословица)
А теперь выпишем точное значение числа пи... (Препод)
Жахни, Пендальф! © Гоблин

AlanG

Дата 10.6.2006, 13:54 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 71
Регистрация: 11.5.2006
Где: РашЫн ФидирейшЫн

Репутация: нет
Всего: нет

Цитата

XenonSk, 0! = 1.

А ноль для интереса прибавил, или чтобы начинающего запутать smile

Цитата

На примере того же факториала:
Мы знаем рекуррентное соотношение (которое, кстати, лежит в основе каждой рекурсивной функции):
fact (n) = n * fact (n - 1).
Вот мы это и реализуем: в предположении, что наша функция вычисляет факториал, пишем, что "n! = n(n - 1)!".
При этом мы уверены, что f (n - 1). На основе этого получаем то, что надо.

Перевод будет? smile

Xenon

Дата 10.6.2006, 14:03 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 1529
Регистрация: 12.4.2006

Репутация: 11
Всего: 50

Pete, Ну и? smile

--------------------

Pete

Дата 10.6.2006, 14:12 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 318
Регистрация: 5.1.2006
Где: Москва

Репутация: нет
Всего: 12

Поправил)

--------------------

Xenon

Дата 10.6.2006, 14:30 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 1529
Регистрация: 12.4.2006

Репутация: 11
Всего: 50

Млин, я 0!=1 прочитал, как : "Нуль не равен единице" ... smile

Тогда уж:

Код


int fact(int n)    
{    
    if (n==0 || n==1)  
    {    
        return 1;    
    }    
    else            
    {    
        return n*fact(n-1);    
    }    
}

Это сообщение отредактировал(а) XenonSk - 10.6.2006, 14:32

--------------------

Pete

Дата 10.6.2006, 14:37 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 318
Регистрация: 5.1.2006
Где: Москва

Репутация: нет
Всего: 12

Это не что иное, как оптимизация. Если говорить бо оптимизации, то вычисление факториала с помощью рекурсии гораздо дороже итеративного варианта и выйгрыша почти никакого.

--------------------

observateur

Дата 10.6.2006, 16:12 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 176
Регистрация: 10.6.2006

Репутация: нет
Всего: нет

Спасибо всем кто отвечал. Постараюс понять.

MAKCim

Дата 10.6.2006, 17:27 (ссылка)

(нет голосов)

Загрузка ...

Воін дZэна

Профиль
Группа: Экс. модератор
Сообщений: 5644
Регистрация: 10.12.2005
Где: Менск, РБ

Репутация: 52
Всего: 207

Цитата

и выйгрыша почти никакого.

я бы сказал вообще никакого smile

--------------------

Void

Дата 10.6.2006, 17:45 (ссылка)

(нет голосов)

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 40
Всего: 173

Цитата(Pete @ 10.6.2006, 16:37

)

сли говорить бо оптимизации, то вычисление факториала с помощью рекурсии гораздо дороже итеративного варианта и выйгрыша почти никакого.

Хвостовая рекурсия эквивалентна итерации (точнее, наоборот). В приведенном коде рекурсия не хвостовая, но легко к ней сводится. Так что разница в способе вычисления тут скорее не алгоритмическая, и все зависит от прозорливости оптимизатора smile

По крайней мере, явную хвостовую рекурсию приличные компиляторы C++ сворачивают уже давно.

--------------------

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

Pete

Дата 10.6.2006, 18:07 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 318
Регистрация: 5.1.2006
Где: Москва

Репутация: нет
Всего: 12

Цитата(MAKCim @ 10.6.2006, 17:27

)

я бы сказал вообще никакого

Небольшой есть.

Цитата(Void @ 10.6.2006, 17:45

)

Хвостовая рекурсия эквивалентна итерации (точнее, наоборот).

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

Это сообщение отредактировал(а) Pete - 10.6.2006, 18:07

--------------------

Void

Дата 10.6.2006, 18:11 (ссылка)

(нет голосов)

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 40
Всего: 173

Цитата(Pete @ 10.6.2006, 20:07

)

Есть алгоритмы, которые рекурсивны по своей природе, и для их итеративной реализации придется организовывать собственный стек. Сомнительный выигрыш.

Цитата(Pete @ 10.6.2006, 20:07

)

На такие вещи, по-моему, нельзя надеяться.

В С++ — нельзя, согласен.

--------------------

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »