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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 31, средняя оценка - 4.94
KOPC1886
27 / 6 / 0
Регистрация: 28.10.2010
Сообщений: 352
09.12.2010, 20:59     Объяснить рекурсию (на примере ханойской башни) #1
Кто может объяснить рекурсию? Можно на примере ханойской башне.Заранее спасибо.
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.12.2010, 20:59     Объяснить рекурсию (на примере ханойской башни)
Посмотрите здесь:

C++ Ханойские башни
C++ Написать рекурсивную и нерекурсивную версию задачи о ханойской башне
C++ Отладить программу в VS 2012 (объяснить ошибку в примере из книжки)
Объяснить что такое "раздельная компиляция", что такое "интерфейс класса" и "реализация класса" на примере C++
C++ Не могу понять алгоритм Ханойской башни
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
lemegeton
 Аватар для lemegeton
2909 / 1338 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
09.12.2010, 21:10     Объяснить рекурсию (на примере ханойской башни) #2
Чтобы понять рекурсию, нужно понять рекурсию.
GNU расшифровывается как "GNU is Not Unix".
KOPC1886
27 / 6 / 0
Регистрация: 28.10.2010
Сообщений: 352
09.12.2010, 22:18  [ТС]     Объяснить рекурсию (на примере ханойской башни) #3
Так как её понять, если никто ее не объясняет?!
Crudelis
Шаровик затейник
 Аватар для Crudelis
667 / 409 / 13
Регистрация: 06.05.2010
Сообщений: 1,109
10.12.2010, 02:14     Объяснить рекурсию (на примере ханойской башни) #4
рекурсия это когда функция вызывает саму себя внутри своего тела функции, взять к примеру функцию вычисляющую факториал:

C++
1
2
3
4
5
int factorial(n){
if(n==0)
return 1;
return n*factorial(n-1);    //----рекурсия
}
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
10.12.2010, 12:34     Объяснить рекурсию (на примере ханойской башни) #5
Цитата Сообщение от Crudelis Посмотреть сообщение
рекурсия это когда функция вызывает саму себя внутри своего тела функции,
Так же можно добавить, что ф-ция считается рекурсивной если она вызыватся из ф-ции, вызов которой происходит в теле ф-ции.
Пример:
C++
1
2
3
4
5
6
7
8
9
10
int f1(){
if(some value)
   return value;
//some code
f2();
}
int f2()
//some code
f1();
}
st_dent
64 / 64 / 3
Регистрация: 05.07.2010
Сообщений: 219
10.12.2010, 13:14     Объяснить рекурсию (на примере ханойской башни) #6
Рекурсивная функция-функция ,вызывающая сама себя. Каждое выполнение тела функции имеет свою область стека для параметров и локальных переменных.
Достоинство:создание компактного кода.
Недостатки:затраты времени на вызов функции и передачу ей копий параметров, затраты памяти для организации каждого вложенного вызова.
При этом следует избегать(по возможности) использования локальных переменных в рекурсивной функции.
Например, факториал:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int f(int n)
{
  if(n<=1) return 1;
  else
    {
       int x=f(n-1);
       return n*x;
     }
}
int main()
{
  int n=3;
  int res= f(n);
}
стек при n=3
||стековый кадр для n=3
||адрес возврата 1
||3

стек при n=2
||стековый кадр для n=2
||адрес возврата 2
||2
||стековый кадр для n=3
||адрес возврата 1
||3

стек при n=1
||стековый кадр для n=1
||адрес возврата 3
||1
||стековый кадр для n=2
||адрес возврата 2
||2
||стековый кадр для n=3
||адрес возврата 1
||3

Здесь каждый раз под х приходиться отводить память. В данном случае можно обойтись без локальной переменной. Пример в посте Crudelis
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9372 / 5422 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
10.12.2010, 13:28     Объяснить рекурсию (на примере ханойской башни) #7
Цитата Сообщение от st_dent Посмотреть сообщение
При этом следует избегать(по возможности) использования локальных переменных в рекурсивной функции.
Например, факториал:
C++
1
int f(int n){ return ( n < 2 ) ? 1 : n * f(n-1); }
KOPC1886
27 / 6 / 0
Регистрация: 28.10.2010
Сообщений: 352
10.12.2010, 21:41  [ТС]     Объяснить рекурсию (на примере ханойской башни) #8
Спасибо! Можно вот на примере кода ханойской башни

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void Towers (int number, int from, int to, int free)
{
  if (number != 0)
  {
    Towers (number-1, from, free, to);
    cout << "Передвигаем " << number << "-й диск с "
         << from << "-его стержня на " << to << "-ий \n";
    Towers (number-1, free, to, from);
  }
}
 
    
int _tmain(int argc, _TCHAR* argv[])
{  setlocale(LC_ALL,"rus");
    int n,s1,s2,s3;
    cin >>n;
    cin >>s1;
    cin >>s2;
    cin >>s3;
    
    Towers ( n,  s1,  s2,  s3);
Вот особенно строки:
Towers (number-1, from, free, to);
cout << "Передвигаем " << number << "-й диск с "<< from << "-его стержня на " << to << "-ий \n";
Towers (number-1, free, to, from);
Как здесь происходит обмен значений между переменными?

 Комментарий модератора 
Используйте теги форматирования кода.
asics
Freelance
Эксперт C++
 Аватар для asics
2838 / 1775 / 144
Регистрация: 09.09.2010
Сообщений: 3,842
10.12.2010, 21:53     Объяснить рекурсию (на примере ханойской башни) #9
KOPC1886, Тут чувак обясняет.
KOPC1886
27 / 6 / 0
Регистрация: 28.10.2010
Сообщений: 352
11.12.2010, 23:14  [ТС]     Объяснить рекурсию (на примере ханойской башни) #10
asics, прослушал спасибо, но там не объясняется!
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
12.12.2010, 08:40     Объяснить рекурсию (на примере ханойской башни) #11
KOPC1886, а что может быть еще не понятного? Функция вызывает саму себя. Если на словах не понятно, то практика!!! Написали простеньку рекурсивную ф-цию (или возьмите одну из тех, что здесь предложили) и под отладчиком трассируем, при этом нужно следить за значением переменных. Особый инерес представляет когда ф-ция "скручивается", т.е. возвращается и в каждой ее копии будут разные значения переменных. Должно помочь ))
KOPC1886
27 / 6 / 0
Регистрация: 28.10.2010
Сообщений: 352
15.12.2010, 20:46  [ТС]     Объяснить рекурсию (на примере ханойской башни) #12
Kastaneda, Я всё равно не понимаю, как происходит обмен значениями между переменными в коде ханойской башни.
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
16.12.2010, 09:38     Объяснить рекурсию (на примере ханойской башни) #13
Цитата Сообщение от st_dent Посмотреть сообщение
стек при n=3
||стековый кадр для n=3
||адрес возврата 1
||3
стек при n=2
||стековый кадр для n=2
||адрес возврата 2
||2
||стековый кадр для n=3
||адрес возврата 1
||3
стек при n=1
||стековый кадр для n=1
||адрес возврата 3
||1
||стековый кадр для n=2
||адрес возврата 2
||2
||стековый кадр для n=3
||адрес возврата 1
||3
может не совсем понятно, суть в том, что в стеке создается несоклько копий одной ф-ции и в каждой копии содержатся разные значения переменных. Например:
C++
1
2
3
4
5
6
int f(int n){
   if(n==1)return n;
   return n+f(--n);//рекурсия
}
//вызываем ф-цию так
f(3);
ф-ция посчитает 3+2+1
Вот как это все выгдядет:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int f(n=3){
   if(n==1)return n;
   return n+f(--n);//n не равно 1, поэтому вызываем дальше
}
int f(n=2){
   if(n==1)return n;
   return n+f(--n);//n не равно 1, поэтому вызываем дальше
}
int f(n=1){
   if(n==1)return n;//возвращаем 1
   return n+f(--n);
}
int f(n=2){//значение вернется в копию ф-ции, где n=2
   if(n==1)return n;
   return n+f(--n);//и будет возвращено 2+то, что вернула ф-ция, т.е. 2+1
}
int f(n=3){//в копию, где n=3 возвращено 2+1, т.е. 3
   if(n==1)return n;
   return n+f(--n); будет возвращено 3+3, т.е. 6
}
если после этого не понятно, тогда - практика до посинения )))

Добавлено через 12 часов 39 минут
Есть мысль написать что-то типа FAQ про рекурсию, с очень подробным разъяснением (на низком уровне) и картинками. Если кто-нибудь напишет, что это нужно, вечером напишу.
DialeR7
 Аватар для DialeR7
1 / 1 / 0
Регистрация: 13.08.2010
Сообщений: 88
16.12.2010, 10:37     Объяснить рекурсию (на примере ханойской башни) #14
Цитата Сообщение от Kastaneda Посмотреть сообщение
Есть мысль написать что-то типа FAQ про рекурсию, с очень подробным разъяснением (на низком уровне) и картинками. Если кто-нибудь напишет, что это нужно, вечером напишу.
было бы замечательно, если напишете =)
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
16.12.2010, 12:08     Объяснить рекурсию (на примере ханойской башни) #15
KOPC1886, мне кажется, вы не понимаете не рекурсию (хотя, возможно, и её вы тоже не понимаете), а именно рекурсивную реализацию Ханойских башен.
На самом деле в примере ханойских башен ничего никуда не передвигается (да и вообще, как там может что-то передвигаться, мы же в функцию всего лишь числа передаём), а создаётся видимость этого передвижения за счёт вывода на экран тех абстрактных передвижений, которые делает функция.
Так что вы не понимаете Башни не за счёт того, что не понимаете рекурсию, а за счёт того, что вы не понимаете саму логику задачи о Башнях, которая к рекурсии никакого отношения не имеет.
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
16.12.2010, 15:09     Объяснить рекурсию (на примере ханойской башни) #16
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Итак, для начала разберем несколько моментов, которые необходимо знать, чтобы понять рекурсию.
Во первых – стек.
Само понятие стека рассматривать не будем, т.к. подразумевается, что это знает каждый, если нет – в гугл. Следует отметить, что в каждой программе есть стек (на этапе компиляции под него выделяется память определенного размера, размер стека влияет на размер программы), который программа использует для своих целей. Цели разные, нас же интересует передача параметров для функции, и передача управления в вызываемую ф-цию (читай «возврат из ф-ции»).
Во вторых – собственно передача параметров и возврат из ф-ции.
Есть различные соглашения для вызовов ф-ций, в языке 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'е не рисовал)))
dihlofos
16.12.2010, 15:17
  #17

Не по теме:

Kastaneda, вам прямо учебники нужно писать

KOPC1886
27 / 6 / 0
Регистрация: 28.10.2010
Сообщений: 352
16.12.2010, 20:49  [ТС]     Объяснить рекурсию (на примере ханойской башни) #18
Kastaneda, спасибо большое, я понял в принципе как работает рекурсия. Но в ханойской башне там то функция ничего не возвращает.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void opel (int n,int s1,int s2,int s3)
    
{if (n==1)
    {cout <<s1<<"-->"<<s3<<endl;}
else
    {   
        opel ( n-1, s1, s3, s2);
        cout <<s1<<"-->"<<s3<<endl;
        opel( n-1, s2, s1, s3);
    
    }       
}
int _tmain(int argc, _TCHAR* argv[])
{  setlocale(LC_ALL,"Russian");
    
    int n=4,s1=1,s2=2,s3=3;
 
    opel ( n, s1, s2, s3);
Когда я смотрел как вызывается функция в режиме отладки, я заметил что в строке
opel ( n-1, s1, s3, s2); происходит обмен значениями между переменными s2 и s3(s1 остается неизменной). А в строке opel( n-1, s2, s1, s3); происходит обмен значениями между переменными s1 и s2. Почему происходит обмен значениями между переменными?
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
16.12.2010, 21:11     Объяснить рекурсию (на примере ханойской башни) #19
Итак, объясняю, какова логика решения задачи про ханойские башни.
Суть в том, что у нас имеется пирамида из n дисков, которая надета на один из штырей, и ещё два штыря - временный и целевой. Суть решения заключается в том, чтобы разбить нашу задачу на подзадачи, а именно - делим нашу пирамиду на две части - на пирамиду из n - 1 дисков (верхний набор) и на один единственный диск. Так вот, мы (абстрактно) берём нашу пирамиду из n - 1 дисков, переносим её на временный штырь, затем переносим наш единственный диск на целевой штырь, а затем переносим всю пирамиду на целевой штырь поверх уже перенесённого последнего диска.
Поскольку мы не можем перенести всю пирамиду целиком, то мы меньшую пирамиду снова делим на две - пирамиду из уже n - 2 дисков и на отдельный диск и к полученной задаче применяем тот же алгоритм. В итоге мы добираемся до элементарной пирамиды из единственного диска, которую просто переносим на целевой штырь. Тут мы начинаем разворачивать рекурсию - вспоминать, что помимо перенесённой части изначальной пирамиды у нас есть ещё один диск - основание пирамиды. Теперь мы переносим это основание на целевой штырь, и всю нашу пирамиду (которая сейчас находится на временном штыре) переносим поверх её основания - диска, теперь находящегося на целевом штыре. Для этого снова применяем тот же алгоритм разбивания пирамиды на части. Перенеся часть пирамиды на основание, вспоминаем, что у полученной пирамиды так же отдельно есть основание, и переносим её на это основание. Так происходит до тех пор, пока вся изначальная пирамида из n дисков не окажется на целевом штыре.
Вся фишка нашей рекурсивной функции не в том, что она физически что-то куда-то переносит, а в том, что она просто-напросто меняет функции штырей, ведь для каждой нашей подзадачи как целевой, как временный, так и исходный штыри могут меняться местами, т.е. перенесли мы пирамиду из, скажем, 4 дисков на временный (для неё) штырь, перенесли последний, пятый диск на целевой штырь, а для перенесённой части пирамиды из 4 дисков изначально временный штырь становится исходным, а в качестве временного будет служить изначально исходный. При этом глобальные функции штырей сохраняются (ведь для нас-то важны не функции штырей в пределах какой-либо из подзадач, а их функции для нашей изначальной задачи - для пирамиды из n дисков, вот эти глобальные назначения штырей функция и выводит на экран). Так вот функция всё то, что я описал, и делает. Сначала проверяется, больше ли n нуля (есть ли ещё диски для переноса), затем вызывает сама себя для n - 1 штыря, и меняет функции штырей (в качестве временного теперь выступает целевой, а в качестве целевого - временный). Затем, внутри этой вызванной функции снова проверяется количество дисков и вызывается ещё одна копия функции уже для ещё меньшей пирамиды из (n - 1) - 1, и снова меняется функция штырей. Так происходит, пока функция не вызовется для пирамиды из одного диска. Тогда будет напечатан мнимый перенос диска с одного штыря на другой и вызвана функция уже для переноса части пирамиды поверх этого перенесённого последнего штыря. Затем снова будет напечатан перенос, и снова какая-то часть пирамиды будет перенесена поверх перенесённого диска. Таким образом наши разрозненные пирамидки будут собираться в одну - изначальную, состоящую из n дисков.
Вообще, главное здесь - понять, что функция и понятия не имеет о том, что нам нельзя класть больший диск поверх меньшего, это заложено в алгоритме, а функция лишь следует ему. Она на каждом шаге всего лишь печатает номера штырей - исходного и целевого, но если мы вспомним, что для каждого экземпляра функции назначения штырей меняются (целевой может стать временным, временный - исходным и т.д.), то становится очевидно, как происходит это мнимый обмен дисков.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.12.2010, 20:28     Объяснить рекурсию (на примере ханойской башни)
Еще ссылки по теме:

Объяснить на примере работу оператора ветвления if else C++
Объяснить как работает рекурсивная функция и стек вызовов на моем примере C++
C++ Написать программу Ханойские башни, используя рекурсию

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
KOPC1886
27 / 6 / 0
Регистрация: 28.10.2010
Сообщений: 352
17.12.2010, 20:28  [ТС]     Объяснить рекурсию (на примере ханойской башни) #20
silent_1991, эм.... а можно не много по подробней о считывании значений в памяти, как все же это происходит?
Yandex
Объявления
17.12.2010, 20:28     Объяснить рекурсию (на примере ханойской башни)
Ответ Создать тему
Опции темы

Текущее время: 19:52. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru