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

Что значит КАК? Ну функция из самой себя вызывает саму себя с новым аргументом  Удобно использовать для математических вычислений, в конце концов для вычисления факториала  Единственное, нужно следить, чтобы проверялось условие и этот цикл завершился когда-нибудь, а не стал бесконечным 
Вот нахождение факториала простым способом

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

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

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

Так все спрашивают, когда начинаю  . Это не нужно, и вообще задумыватся над этим не надо, поверь  . Логика проста, как два мегабайта скачать  
А думать о схеме не надо, вот как это происходит





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

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

XenonSk, 0! = 1.


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

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

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


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

 

Pete, Ну и?  

Поправил) 

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

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

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

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

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

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

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

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

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

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

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

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

Pete, ничего экзотического, перепиши обычную быструю сортировку (Хоара), не создавая собственного стека.
И сравни быстродействие эмуляции стека с явной рекурсией. Такой вариант, возможно, окажется быстрее, но ненамного. И даже в этом я не уверен. 

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

Хм.. Согласен. Пока не встречал ее итерационной реализации без стека. Сравнение этих алгоритмов в скорости, наверное, уже больше зависит от системы. Конечно, отсутствие объявления новых переменных на каждом уровне рекурсии придаст определенное ускорение, хотя, кто знает...
(ЗЫ: мы пока от темы не ушли далеко?  )  

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

Ну мне кажется тут такой же "большой" прирост в скорости, что и при использовании

Вместо
 

XenonSk, 
конечно, прирост производительности явно не будет большим. Может твой компилятор и сгенерирует эквивалентный код, как в верхней инструкции. Что может быть более показательным сейчас, как использование интерпретируемых языков.... 

kirjanov, То, что кинул я считается не одним и тем же ... Вообще говорят, что часто побитовый сдвиг дает хороший прирост  

Я не знаю компилятора, настолько тупого, чтобы умножение или деление на константу он не превратил в битовый сдвиг.
И, кстати, в случае знакововых чисел можно сильно огрести, использовав сдвиг вправо вместо деления:



И еще:


Это Intel C++ 9.0 в режиме максимальной оптимизации.
Не оптимизируйте, и не оптимизируемы будете  

Void, просто говорю, что в справочнике написано, а об "вылезании" там тоже писали  

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

В стек заносится лишь адрес возврата и параметры вызываемой функции.
Да, вызываемая функция выделяет место на стеке для своих локальных переменных, но это — одна инструкция изменения регистра стека.

Кажется, уже обсуждалось, что статические переменные не могут дать никакого преимущества в скорости перед локальными. 

я это и имел в виду, не так выразился

под статическим массивом я подразумевал массив на стеке (размер известен в compile-time)
как пример можно взять рекурсивную функцию

и эквивалентную ее итеративную с эмуляцией стека

и вызов

тут итеративная выигрывает в используемой памяти (261 против 512 байт) и по количеству команд процессора
(326 против 575 (вывод считаем оной командой; командную реализацию while и if не рассматриваем))
так как любая рекурсивная программа сводится к итеративной, то, как показывает пример, при правильной ее организации она оказывается более эффективной  

Это сообщение отредактировал(а) MAKCim - 12.6.2006, 09:42

Эх, люблю я бенчмарки проводить  Вот и в этот раз не выдержал и написал тест. Все ту же быструю сортировку в двух вариантах: явная рекурсия и эмуляция через стек.

Результаты:
GCC 3.4.5 (MinGW)

VC 8.0:

Вот такая забавная картина, не находите? 
Так стоит ли заморачиваться с ручной эмуляцией стека ради пары процентов производительности, которые в зависимости от компилятора могут оказаться и на той, и на другой стороне? ИМХО, нет.
В данном случае можно было оценить верхний предел глубины рекурсии, однако выделяя под стек массив постоянного размера мы в любом случае рискуем молчаливо вылететь за его пределы. Используя же динамический массив мы рискуем свести на нет все призрачные преимущества эмуляции рекурсии.