246071-Либерти-Освой-самостоятельно-С-за-21-день (852741), страница 21
Текст из файла (страница 21)
Поскольку вызов функции fib(2) возвращает значение 1 и вызовфункцииfib(1)возвращаетзначение1,тофункцияfib(3)возвратитзначение2.Если вызвать функцию fib(4), она возвратит сумму значений, возвращаемых функциямиfib(3) и fib(2). Мы уже установили, что функция fib(3) возвращает значение 2 (путем вызовафункций fib(2) и fib(1)) и что функция fib(2) возвращает значение 1, поэтому функция fib(4)просуммируетэтичислаивозвратитзначение3,котороебудетявлятьсячетвертымчленомрядаФибоначчи.Сделаем еще один шаг.
Если вызвать функцию fib(5), она вернет сумму значений,возвращаемых функциями fib(4) и fib(3). Как мы установили, функция fib(4) возвращаетзначение3,афункцияfib(3)—значение2,поэтомувозвращаемаясуммабудетравначислу5.Описанный метод — не самый эффективный способ решения этой задачи (при вызовефункцииfib(20)функцияfib()вызывается13529раз!),темнеменееонработает.Однакобудьтеосторожны.ЕслизадатьслишкомбольшойномерчленарядаФибоначчи,вамможетнехватитьпамяти. При каждом вызове функции fib() резервируется некоторая область памяти.
Привозвращенииизфункциипамятьосвобождается.Ноприрекурсивныхвызовахрезервируютсявсеновые области памяти, а при таком подходе системная память может исчерпаться довольнобыстро.Реализацияфункцииfib()показанавлистинге5.10.Предупреждение: При запуске программы, представленной в листинге 6.10, задавайтенебольшие номера членов ряда Фибоначчи (меньше 15). Поскольку в этой программеиспользуетсярекурсия,возможныбольшиезатратыпамяти.Листинг 5.10.
Пример использования рекурсии для нахождения члена рядаФибоначчи1:#include<iostream.h>2:3:intfib(intn);4:5:intmain()6:{7:8:intn,answer;9:cout<<"Enternumbertofind:";10:cin>>n;10:11:cout<<"\n\n";12:13:answer=fib(n);14:15:cout<<answer<<"isthe"<<n<<"thFibonaccinumber\n";17:return0,16:}17:18:intfib(intn)19:{20:cout<<"Processingfib("<<n<<")...";23:21:if(n<3)22:{23:cout<<"Return1!\n";24:return(1);25:}26:else27:{28:cout<<"Callfib("<<n-2<<")andfib("<<n-1<<").\n";29:return(fib(n-2)+fib(n-l));30:}31:}Результат:Enternumberlofind:6Processingfib(6)...Callfib(4)andfib{S)Processingfib(4)...Callfit>(2)andfib(3)Processingfib(2)...Return1!Processingfib(3)...Callfib(l)andfiO<2)Processingfib(D...Return1!Processingfib(2)...Return1!Processingfib(5)...Callfib(3)andfib{4)Processingfib(3}...Callfib(1)andfib(2)Processingflb(1)...Return1!Processingfib(2)...Return1!Processingfib(4)...Callfib(2)andfib(3)Processingfib(2)...Return1!Processingfib(3)...Callfib(1)andfib(2)Processingfib(l)...Return1!Processingfib(2)...Return1!8isthe6thFibonaccinumberПримечание:Некоторые компиляторы испытывают затруднения с использованиемоператоров в выражениях с объектом cout.
Если вы получите предупреждение в строке 28,заключитеоперациювычитаниявкруглыескобки,чтобыстрока28приняласледующийвид:28:cout<<"Callfib("<<(n-2)<<")andfib("<<n-1<<").\n";Анализ:Встроке9программапредлагаетввестиномерискомогочленарядаиприсваиваетего переменной n. Затем вызывается функция fib() с аргументом n. Выполнение программыпереходиткфункцииfib(),гдевстроке20этотаргументвыводитсянаэкран.В строке 21 проверяется, не меньше ли аргумент числа 3, и, если это так, функция fib()возвращает значение 1. В противном случае выводится сумма значений, возвращаемых привызове функции fib() с аргументами n-2 и п-1.
Таким образом, эту программу можнопредставить как циклический вызов функции fib(), повторяющийся до тех пор, пока приочередном вызове этой функции не будет возвращено некоторое значение. Единственнымивызовами,которыенемедленновозвращаютзначения,являютсявызовыфункцийfib(1)иfib(2).Рекурсивноеиспользованиефункцииfib()проиллюстрированонарис.5.4и5.5.В примере, изображенном на рисунках, переменная n равна значению 6, поэтому изфункции main() вызывается функция fib(6). Выполнение программы переходит в тело функцииfib(),ивстроке30значениепереданногоаргументасравниваетсясчислом3.Посколькучисло6больше числа 3, функция fib(6) возврашает сумму значений, возвращаемых функциями fib(4) иfib(5):38:return(fib(n-2)+fib(n-1));Этоозначает,чтовыполняетсяобращениекфункциямfib(4)иfib(5)(посколькупеременнаяn равначислу 6, то fib(n-2) — это то же самое, что fib(4), а fib(n-1) — то же самое, что fib(5)).После этого функция fib(6), которой в текущий момент передано управление программой,ожидает, пока сделанные вызовы не возвратят какое-нибудь значение.
Дождавшись возвратазначений,этафункциявозвратитрезультатсуммированияэтихдвухзначений.Рис.5.4.ИспользованиерекурсииРис.5.5.ВозвращениеизрекурсииПоскольку при вызове функции fib(5) передается аргумент, который не меньше числа 3,функцияfib()будетвызыватьсяснова,наэтотразсаргументами4и3.Афункцияflb(4)вызовет,всвоюочередь,функцииfib(3)иfib(2).Результаты и промежуточные этапы работы программы, представленной в листинге 5.10,выводятся на экран. Скомпилируйте, скомпонуйте и выполните эту программу, введя сначалачисло 1, затем 2, 3, и так доберитесь до числа 6, внимательно наблюдая за отображаемойинформацией.Работа с этой программой предоставляет вам прекрасный шанс проверить возможностисвоего отладчика. Разместите точку останова в строке 20, а затем заходите в тело каждойвызываемойфункцииfib(),отслеживаязначениепеременнойnприкаждомрекурсивномвызовефункцииfib().В программировании на языке C++ рекурсия не частый гость, но в определенных случаяхонаявляетсямощнымивесьмаэлегантныминструментом.Примечание:Рекурсия относится к одной из самых сложных тем программирования.Данныйразделполезендляпониманияосновныхидейеереализации,однаконеследуетслишкомрасстраиваться,есливамнедоконцаяснывседеталиработырекурсии.Работафункций-приподнимаемзавесутайныПри вызове функции управление программой передается вызванной функции.
Происходитпередача параметров, после чего начинается выполнение операторов, составляющих телофункции. По завершении выполнения функции возвращается некоторое значение (если неопределено,чтофункциявозвращаеттипvoid)иуправлениепередаетсявызывающейфункции.Как же реализуется эта задача? Откуда программе известно, к какому блоку ей сейчаснужно перейти? Где хранятся переменные при передаче их в качестве аргументов? Чтопроисходит с переменными, которые объявляются в теле функции? Как передается назадвозвращаемое значение? Откуда программе известно, с какого места ей нужно продолжитьработу?Многие авторы даже не делают попыток ответить на все эти вопросы, но без пониманияпринципов работы функций программирование вам покажется сплошным шаманством.Объяснениежепотребуеткраткогоосвещениявопросов,связанныхспамятьюкомпьютера.УровниабстракцииОдно из основных препятствий для начинающих программистов — преодолениенескольких уровней абстрагирования от реальности.
Компьютеры, конечно, всего лишьэлектронныемашины.Ониничегонезнаютобокнахименю,опрограммахиликомандах,онидаже ничего не знают о единицах и нулях. Все, что происходит в действительности, связанолишь с измерением напряжения в различных точках интегральных микросхем. И даже этоявляетсяабстракцией.Самоэлектричествопредставляетсобойлишьумозрительнуюконцепция,обобщающуюповедениеэлементарныхчастиц.Некоторых программистов пугает любой уровень детализации, опускающийся нижепонятий о значениях, хранящихся в ОЗУ.
В конце концов, вам не нужно понимать физикуэлементарныхчастиц,чтобыуправлятьавтомобилем,печьпирогиилибитьпомячу.Точнотакже,чтобыпрограммировать,можнообойтисьбезпониманияэлектроникикомпьютера.Однако вы должны понимать, как в компьютере организована память. Без четкогопредставленияотом,гдерасполагаютсявашипеременныепослеихсозданияикакпередаютсязначениямеждуфункциями,программированиеостанетсядляваснепостижимойтайной.РазбиениепамятиКогда вы начинаете работу со своей программой, операционная система (например, DOSилиMicrosoftWindows)выделяетразличныеобластипамятивответнатребованиякомпилятора.КакпрограммистунаC++,вамчастопридетсяинтересоватьсяпространствомглобальныхимен,свободнойпамятью,регистрами,памятьюсегментовпрограммыистеками.Глобальные переменные хранятся в пространстве глобальных имен.
Подробнее опространстве глобальных имен и свободной памяти речь пойдет на следующих уроках, а покасосредоточимсянарегистрах,оперативнойпамятиистеках.Регистры представляют собой специальную область памяти, встроенную прямо вцентральное процессорное устройство, или центральный процессор (Central Processing Unit —CPU). На их плечи возложена забота о выполнении внутренних вспомогательных функций,описаниебольшейчастикоторыхвыходитзарамкиэтойкниги.Номывсе-такиостановимсянарассмотрениинаборарегистров,ответственныхзауказаниенаследующуюстрокупрограммывлюбой момент времени. Назовем эти регистры (все вместе) указателями команд.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
