Форум программистов, компьютерный форум CyberForum.ru

Объяснить рекурсию (на примере ханойской башни) - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Работа с массивами http://www.cyberforum.ru/cpp-beginners/thread207399.html
Определить значения и адреса элементов массива, вычисляемых по формуле X(катое)=a(катое)/k(факториал).
C++ Матрицы Помогите с программой: Дана квадратная матрица А порядка n. Найти А в четвертой степени http://www.cyberforum.ru/cpp-beginners/thread207390.html
C++ выводит неверный ответ
#include <iostream.h> #include <stdio.h> const int n = 100; int main (int argc, char * const argv) { int x; cout << "введите размер массива "; cin >> x; int mas;
Создать класс C++
Для соответствующего класса, перегрузить арифметические операции(+,-,*,/). При перезгузке арифметические действия должны выполняться относительно только числовых полей!!! Создать несколько объектов класса и проинициализировать их с помощью конструктора с параметрами. Создать несколько дополнительных объектов таким образом, чтобы: - первый объект являлся суммой двух других объектов; - второй...
C++ Абстрактные методы или указатели на функции? http://www.cyberforum.ru/cpp-beginners/thread207345.html
Сабж для класса систем дифференциальных уравнений вида y'=f(x,y) Что лучше: класс с полем указателя на вектор функцию и передача указателя в конструктор, или внутри класса абстрактный метод, а в программе его перекрывать? Оба метода работают. Но какой логичнее и/или лучше?
C++ Как поменять местами элементы вектора ? собственно вопрос совпадает с темой, как поменять местами 2 элемента вектора ? в C++ Добавлено через 25 минут все, не надо, сам разобрался. подробнее

Показать сообщение отдельно
Kastaneda
Форумчанин
Эксперт С++
4652 / 2860 / 228
Регистрация: 12.12.2009
Сообщений: 7,270
Записей в блоге: 2
Завершенные тесты: 1
16.12.2010, 15:09
Итак, для начала разберем несколько моментов, которые необходимо знать, чтобы понять рекурсию.
Во первых – стек.
Само понятие стека рассматривать не будем, т.к. подразумевается, что это знает каждый, если нет – в гугл. Следует отметить, что в каждой программе есть стек (на этапе компиляции под него выделяется память определенного размера, размер стека влияет на размер программы), который программа использует для своих целей. Цели разные, нас же интересует передача параметров для функции, и передача управления в вызываемую ф-цию (читай «возврат из ф-ции»).
Во вторых – собственно передача параметров и возврат из ф-ции.
Есть различные соглашения для вызовов ф-ций, в языке C используется соглашение cdecl (от «c-declaration»), однако для работы с WinAPI используется stdcall, но нас это сейчас не интересует. Соглашение cdecl звучит примерно так: «Аргументы передаются через стек, справа налево. За очистку стека отвечает вызывающая ф-ция.» Очистка стека нас не интересует, а вот передачу параметров, а так же вызов ф-ции и возврат из ф-ции разберем более подробно на примере такой программы.
C++
1
2
3
4
5
6
7
8
9
10
11
int func (int a, int b, int c);
int main(){
int x=5, y=6, z=7;
int summa;
summa = func(x,y,z);
return 0;
}
int func (int a, int b, int c){
int tmp = a+b+c;
return tmp;
}
И так – в ходе выполнения программа дошла до строки summa = func(x,y,z), естественно первым делом будет вызвана ф-ция, потом уже переменной summa будет присвоено значение, которое возвратит ф-ция. Помним, что по соглашению cdecl данные передаются справа налево, поэтому в стек будут «втолкнуты» (от англ. push) сначала переменная z, потом y, потом x. (еще нужно сказать, чего не пишут в сишной лит-ре (по крайней мере я не встречал) в стек так же кладется адрес строки (а каждая строка в коде имеет свой адрес), следующей после строки, где вызывается ф-ция, это делается для того, что бы по команде return вернутся туда, куда нужно, а не куда попало, но нас сей факт не интересует, поэтому опустим этот вопрос.)
Объяснить рекурсию (на примере ханойской башни)
Когда управление будет передано в функцию, то данные будут извлечены «сверху вниз» если смотреть по рисунку.
Вроде здесь все понятно, более подробно объяснять думаю нет смысла. Теперь можно перейти непосредственно к самой рекурсии.
Объяснение на словах, что такое рекурсия и с чем ее едят писалось на форуме выше, да в любой книге можно это найти, поэтому я не буду повторяться, сразу перейдем к примеру.
C++
1
2
3
4
5
6
7
8
9
int func(int n);
int main(){
int a=3;
int summa=func(a);
}
int func(int n){
   if(n==1)return n;
   return n+func(--n);
}
Этот код был рассмотрен выше, сейчас разберем его более подробно.
Итак программа доходит до строки int summa=func(a), первым делом будет вызвана ф-ция. Аргумент у нас один, поэтому он и будет положен в стек.
Объяснить рекурсию (на примере ханойской башни)
Ф-ция принимает аргумент n, поэтому локальной переменной n будет присвоено значение, которое ф-ция вытащит из стека, т.е. число 3. Нужно уточнить, что «локальная» значит не только область видимости, но и то, что переменная создана в стеке (т.е. временная переменная, когда управление перейдет в вызывающую подпрограмму (т.е. в ф-цию main) эта переменная окажется в области стека «МУСОР») Итак мы находимся в программе, вот как выглядет стек:
Объяснить рекурсию (на примере ханойской башни)
Далее выполняется строка if(n==1)return n, поскольку n сейчас не равно 1, то будет выполнена строка return n+ func (--n) (т.е. return 3+ func (2)) Значение переменной n у нас известно, а вот, что вернет func(2) пока нет, поэтому n будет запомнена, а для вызова ф-ции будет выделено дополнительное место в стеке. Вот стек после второго вызова ф-ции:
Объяснить рекурсию (на примере ханойской башни)
Ф-ция начинает свою работу, if(n==1)return n, n опять не равно 1, поэтому вызываем дальше return n+ func (--n); (т.е. 2+ func(1)) И опять значение n запоминается, выделяется новое место в стеке для ф-ции, вот так:
Объяснить рекурсию (на примере ханойской башни)
Ну вот, n=1, поэтому выполнется строка if(n==1)return n. Куда же вернется значение n? Туда, откуда была вызвана ф-ция, т.е. в предыдущую копию ф-ции, в которой n равно 2.
Объяснить рекурсию (на примере ханойской башни)
В этой копии ф-ции мы остановились на строке return n+ func (--n), значение n у нас было известно ( n=2), вот теперь мы получили значение, которое вернула ф-ция (т.е. 1). Только теперь может выполниться эта строка return 2+1; Это значение опять возвращается в предыдущую копию ф-ции:
Объяснить рекурсию (на примере ханойской башни)
Ну и наконец-то в первой копии ф-ции будет выполнена строка return n+ func (--n) (т.е. return 3+3). Таким образом в функцию main будет возвращено число 6, которое и присвоится переменной summa.

Уфф, вроде все)

P.S. когда сам понимаешь материал, кажется, что рассказал все понятно), если что-то не понятно - спрашивайте.
P.P.S. давно я в paint'е не рисовал)))
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru