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

@KOPC1886 · Регистрация: 28.10.2010

Студворк — интернет-сервис помощи студентам

Кто может объяснить рекурсию? Можно на примере ханойской башне.Заранее спасибо.

@lemegeton · 09.12.2010, 21:10

Чтобы понять рекурсию, нужно понять рекурсию.
GNU расшифровывается как "GNU is Not Unix".

@KOPC1886 · 09.12.2010, 22:18 **[ТС]**

Так как её понять, если никто ее не объясняет?!

@Crudelis · 10.12.2010, 02:14

рекурсия это когда функция вызывает саму себя внутри своего тела функции, взять к примеру функцию вычисляющую факториал:

C++
1
2
3
4
5
int factorial(n){
if(n==0)
return 1;
return n*factorial(n-1);    //----рекурсия
}

@Kastaneda · 10.12.2010, 12:34

Сообщение от 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 · 10.12.2010, 13:14

Рекурсивная функция-функция ,вызывающая сама себя. Каждое выполнение тела функции имеет свою область стека для параметров и локальных переменных.
Достоинство:создание компактного кода.
Недостатки:затраты времени на вызов функции и передачу ей копий параметров, затраты памяти для организации каждого вложенного вызова.
При этом следует избегать(по возможности) использования локальных переменных в рекурсивной функции.
Например, факториал:

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 · 10.12.2010, 13:28

Сообщение от st_dent

При этом следует избегать(по возможности) использования локальных переменных в рекурсивной функции.
Например, факториал:

C++
1
int f(int n){ return ( n < 2 ) ? 1 : n * f(n-1); }

@KOPC1886 · 10.12.2010, 21:41 **[ТС]**

Спасибо! Можно вот на примере кода ханойской башни

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 · 10.12.2010, 21:53

KOPC1886, Тут чувак обясняет.

@KOPC1886 · 11.12.2010, 23:14 **[ТС]**

asics, прослушал спасибо, но там не объясняется!

@Kastaneda · 12.12.2010, 08:40

KOPC1886, а что может быть еще не понятного? Функция вызывает саму себя. Если на словах не понятно, то практика!!! Написали простеньку рекурсивную ф-цию (или возьмите одну из тех, что здесь предложили) и под отладчиком трассируем, при этом нужно следить за значением переменных. Особый инерес представляет когда ф-ция "скручивается", т.е. возвращается и в каждой ее копии будут разные значения переменных. Должно помочь ))

@KOPC1886 · 15.12.2010, 20:46 **[ТС]**

Kastaneda, Я всё равно не понимаю, как происходит обмен значениями между переменными в коде ханойской башни.

@Kastaneda · 16.12.2010, 09:38

Сообщение от 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 · 16.12.2010, 10:37

Сообщение от Kastaneda

Есть мысль написать что-то типа FAQ про рекурсию, с очень подробным разъяснением (на низком уровне) и картинками. Если кто-нибудь напишет, что это нужно, вечером напишу.

было бы замечательно, если напишете =)

silent_1991 · 16.12.2010, 12:08

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

@Kastaneda · 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'е не рисовал)))

@dihlofos · 16.12.2010, 15:17

Не по теме:

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

@KOPC1886 · 16.12.2010, 20:49 **[ТС]**

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 · 16.12.2010, 21:11

Итак, объясняю, какова логика решения задачи про ханойские башни.
Суть в том, что у нас имеется пирамида из n дисков, которая надета на один из штырей, и ещё два штыря - временный и целевой. Суть решения заключается в том, чтобы разбить нашу задачу на подзадачи, а именно - делим нашу пирамиду на две части - на пирамиду из n - 1 дисков (верхний набор) и на один единственный диск. Так вот, мы (абстрактно) берём нашу пирамиду из n - 1 дисков, переносим её на временный штырь, затем переносим наш единственный диск на целевой штырь, а затем переносим всю пирамиду на целевой штырь поверх уже перенесённого последнего диска.
Поскольку мы не можем перенести всю пирамиду целиком, то мы меньшую пирамиду снова делим на две - пирамиду из уже n - 2 дисков и на отдельный диск и к полученной задаче применяем тот же алгоритм. В итоге мы добираемся до элементарной пирамиды из единственного диска, которую просто переносим на целевой штырь. Тут мы начинаем разворачивать рекурсию - вспоминать, что помимо перенесённой части изначальной пирамиды у нас есть ещё один диск - основание пирамиды. Теперь мы переносим это основание на целевой штырь, и всю нашу пирамиду (которая сейчас находится на временном штыре) переносим поверх её основания - диска, теперь находящегося на целевом штыре. Для этого снова применяем тот же алгоритм разбивания пирамиды на части. Перенеся часть пирамиды на основание, вспоминаем, что у полученной пирамиды так же отдельно есть основание, и переносим её на это основание. Так происходит до тех пор, пока вся изначальная пирамида из n дисков не окажется на целевом штыре.
Вся фишка нашей рекурсивной функции не в том, что она физически что-то куда-то переносит, а в том, что она просто-напросто меняет функции штырей, ведь для каждой нашей подзадачи как целевой, как временный, так и исходный штыри могут меняться местами, т.е. перенесли мы пирамиду из, скажем, 4 дисков на временный (для неё) штырь, перенесли последний, пятый диск на целевой штырь, а для перенесённой части пирамиды из 4 дисков изначально временный штырь становится исходным, а в качестве временного будет служить изначально исходный. При этом глобальные функции штырей сохраняются (ведь для нас-то важны не функции штырей в пределах какой-либо из подзадач, а их функции для нашей изначальной задачи - для пирамиды из n дисков, вот эти глобальные назначения штырей функция и выводит на экран). Так вот функция всё то, что я описал, и делает. Сначала проверяется, больше ли n нуля (есть ли ещё диски для переноса), затем вызывает сама себя для n - 1 штыря, и меняет функции штырей (в качестве временного теперь выступает целевой, а в качестве целевого - временный). Затем, внутри этой вызванной функции снова проверяется количество дисков и вызывается ещё одна копия функции уже для ещё меньшей пирамиды из (n - 1) - 1, и снова меняется функция штырей. Так происходит, пока функция не вызовется для пирамиды из одного диска. Тогда будет напечатан мнимый перенос диска с одного штыря на другой и вызвана функция уже для переноса части пирамиды поверх этого перенесённого последнего штыря. Затем снова будет напечатан перенос, и снова какая-то часть пирамиды будет перенесена поверх перенесённого диска. Таким образом наши разрозненные пирамидки будут собираться в одну - изначальную, состоящую из n дисков.
Вообще, главное здесь - понять, что функция и понятия не имеет о том, что нам нельзя класть больший диск поверх меньшего, это заложено в алгоритме, а функция лишь следует ему. Она на каждом шаге всего лишь печатает номера штырей - исходного и целевого, но если мы вспомним, что для каждого экземпляра функции назначения штырей меняются (целевой может стать временным, временный - исходным и т.д.), то становится очевидно, как происходит это мнимый обмен дисков.

@KOPC1886 · 17.12.2010, 20:28 **[ТС]**

silent_1991, эм.... а можно не много по подробней о считывании значений в памяти, как все же это происходит?

Новые блоги и статьи Все статьи Все блоги /
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .
Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .

@KOPC1886 27 / 6 / 0 Регистрация: 28.10.2010 Сообщений: 352

	Объяснить рекурсию (на примере ханойской башни) 09.12.2010, 20:59. Показов 15854. Ответов 27 Метки нет (Все метки) Кто может объяснить рекурсию? Можно на примере ханойской башне.Заранее спасибо. 0

@lemegeton 4903 / 2696 / 921 Регистрация: 29.11.2010 Сообщений: 5,783
	09.12.2010, 21:10
	Чтобы понять рекурсию, нужно понять рекурсию. GNU расшифровывается как "GNU is Not Unix". 1

@KOPC1886 27 / 6 / 0 Регистрация: 28.10.2010 Сообщений: 352
	09.12.2010, 22:18 [ТС]
	Так как её понять, если никто ее не объясняет?! 0

@asics Freelance 2891 / 1826 / 356 Регистрация: 09.09.2010 Сообщений: 3,841
	10.12.2010, 21:53
	KOPC1886, Тут чувак обясняет. 1

@KOPC1886 27 / 6 / 0 Регистрация: 28.10.2010 Сообщений: 352
	11.12.2010, 23:14 [ТС]
	asics, прослушал спасибо, но там не объясняется! 0

@Kastaneda 5232 / 3205 / 362 Регистрация: 12.12.2009 Сообщений: 8,143 Записей в блоге: 2
	12.12.2010, 08:40
	KOPC1886, а что может быть еще не понятного? Функция вызывает саму себя. Если на словах не понятно, то практика!!! Написали простеньку рекурсивную ф-цию (или возьмите одну из тех, что здесь предложили) и под отладчиком трассируем, при этом нужно следить за значением переменных. Особый инерес представляет когда ф-ция "скручивается", т.е. возвращается и в каждой ее копии будут разные значения переменных. Должно помочь )) 1

@KOPC1886 27 / 6 / 0 Регистрация: 28.10.2010 Сообщений: 352
	15.12.2010, 20:46 [ТС]
	Kastaneda, Я всё равно не понимаю, как происходит обмен значениями между переменными в коде ханойской башни. 0

silent_1991 5058 / 3118 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	16.12.2010, 12:08
	KOPC1886, мне кажется, вы не понимаете не рекурсию (хотя, возможно, и её вы тоже не понимаете), а именно рекурсивную реализацию Ханойских башен. На самом деле в примере ханойских башен ничего никуда не передвигается (да и вообще, как там может что-то передвигаться, мы же в функцию всего лишь числа передаём), а создаётся видимость этого передвижения за счёт вывода на экран тех абстрактных передвижений, которые делает функция. Так что вы не понимаете Башни не за счёт того, что не понимаете рекурсию, а за счёт того, что вы не понимаете саму логику задачи о Башнях, которая к рекурсии никакого отношения не имеет. 1

@dihlofos
	16.12.2010, 15:17
	Не по теме: Kastaneda, вам прямо учебники нужно писать :) 1

silent_1991 5058 / 3118 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	16.12.2010, 21:11
	Итак, объясняю, какова логика решения задачи про ханойские башни. Суть в том, что у нас имеется пирамида из n дисков, которая надета на один из штырей, и ещё два штыря - временный и целевой. Суть решения заключается в том, чтобы разбить нашу задачу на подзадачи, а именно - делим нашу пирамиду на две части - на пирамиду из n - 1 дисков (верхний набор) и на один единственный диск. Так вот, мы (абстрактно) берём нашу пирамиду из n - 1 дисков, переносим её на временный штырь, затем переносим наш единственный диск на целевой штырь, а затем переносим всю пирамиду на целевой штырь поверх уже перенесённого последнего диска. Поскольку мы не можем перенести всю пирамиду целиком, то мы меньшую пирамиду снова делим на две - пирамиду из уже n - 2 дисков и на отдельный диск и к полученной задаче применяем тот же алгоритм. В итоге мы добираемся до элементарной пирамиды из единственного диска, которую просто переносим на целевой штырь. Тут мы начинаем разворачивать рекурсию - вспоминать, что помимо перенесённой части изначальной пирамиды у нас есть ещё один диск - основание пирамиды. Теперь мы переносим это основание на целевой штырь, и всю нашу пирамиду (которая сейчас находится на временном штыре) переносим поверх её основания - диска, теперь находящегося на целевом штыре. Для этого снова применяем тот же алгоритм разбивания пирамиды на части. Перенеся часть пирамиды на основание, вспоминаем, что у полученной пирамиды так же отдельно есть основание, и переносим её на это основание. Так происходит до тех пор, пока вся изначальная пирамида из n дисков не окажется на целевом штыре. Вся фишка нашей рекурсивной функции не в том, что она физически что-то куда-то переносит, а в том, что она просто-напросто меняет функции штырей, ведь для каждой нашей подзадачи как целевой, как временный, так и исходный штыри могут меняться местами, т.е. перенесли мы пирамиду из, скажем, 4 дисков на временный (для неё) штырь, перенесли последний, пятый диск на целевой штырь, а для перенесённой части пирамиды из 4 дисков изначально временный штырь становится исходным, а в качестве временного будет служить изначально исходный. При этом глобальные функции штырей сохраняются (ведь для нас-то важны не функции штырей в пределах какой-либо из подзадач, а их функции для нашей изначальной задачи - для пирамиды из n дисков, вот эти глобальные назначения штырей функция и выводит на экран). Так вот функция всё то, что я описал, и делает. Сначала проверяется, больше ли n нуля (есть ли ещё диски для переноса), затем вызывает сама себя для n - 1 штыря, и меняет функции штырей (в качестве временного теперь выступает целевой, а в качестве целевого - временный). Затем, внутри этой вызванной функции снова проверяется количество дисков и вызывается ещё одна копия функции уже для ещё меньшей пирамиды из (n - 1) - 1, и снова меняется функция штырей. Так происходит, пока функция не вызовется для пирамиды из одного диска. Тогда будет напечатан мнимый перенос диска с одного штыря на другой и вызвана функция уже для переноса части пирамиды поверх этого перенесённого последнего штыря. Затем снова будет напечатан перенос, и снова какая-то часть пирамиды будет перенесена поверх перенесённого диска. Таким образом наши разрозненные пирамидки будут собираться в одну - изначальную, состоящую из n дисков. Вообще, главное здесь - понять, что функция и понятия не имеет о том, что нам нельзя класть больший диск поверх меньшего, это заложено в алгоритме, а функция лишь следует ему. Она на каждом шаге всего лишь печатает номера штырей - исходного и целевого, но если мы вспомним, что для каждого экземпляра функции назначения штырей меняются (целевой может стать временным, временный - исходным и т.д.), то становится очевидно, как происходит это мнимый обмен дисков. 3

@KOPC1886 27 / 6 / 0 Регистрация: 28.10.2010 Сообщений: 352
	17.12.2010, 20:28 [ТС]
	silent_1991, эм.... а можно не много по подробней о считывании значений в памяти, как все же это происходит? 1

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

Решение