Ребята, объясните пожалуйста эту рекурсию!

@andy2050 · Регистрация: 18.09.2009

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

Ребята, ну хоть убейся не могу понять эту рекурсивную фунцию для задачи с Ханойской башней!
Всё работает отлично, но вот как! Кто может, объясните пошагово, буду очень признателен!

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<iostream>
using namespace std;
 
int num;
 
void hanoy(int num,char a,char b,char c)
{
if(num>0)
{
hanoy(num-1,a,c,b);
cout<<a<<" -> "<<c<<endl;
hanoy(num-1,b,a,c);
}
 
}
 
int main(){
char a='A',b='B',c='C';
int num;  
  
cout<<"number of rings=";
cin>>num;
 
hanoy(num,a,b,c);
 
system("PAUSE");
return 0;
}

@Somebody · 19.09.2009, 18:02

Ханойская башня - тут и алгоритм, и ещё рисунок в тему.

@andy2050 · 19.09.2009, 18:51 **[ТС]**

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

Ханойская башня - тут и алгоритм, и ещё рисунок в тему.

алгоритм ясен, вот только рекурсивная функция и её работа в моём коде вообще не понятна!

@odip · 20.09.2009, 18:43

Чтобы понять рекурсию нужно сначала понять рекурсию.

@just_a_cat · 20.09.2009, 23:30

ты не понимаешь рекурсию вообщем ? или только рекурсию в данной задаче ?
если вообщем, то лучше изучать её на примере вычисления факториала :

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int fact(int N) 
{
           int Res;
    if (N > 1) {
        Res= fact(N-1)*N;
    }
    else {
        Res = 1;
    }
 
    return Res;
}
int main()
{
           cout << factorial(3);
 
           system("pause > nul");
           return 0;
}

для начала попробуем разбить нашу задачу вычисления факториала, на простые подзадачи

C
1
2
//N! = N*(N-1)*(N-2)*...*2*1 = (N-1)!*N
    //(N-1)! = (N-1)*(N-2)*...*2*1

тоесть нам нужно умножить н-1, потом н-1-1, потом н-1-1-1... и так пока н-1 не будет равно 1.
это мы и делаем вот в этой строке,

C
1
Res= fact(N-1)*N;

тоесть мы умножаем результат нашеё функции, на N, чему равен результат функции ? верно, мы не знаем, но мы можем пойти дальше, а потом вернуться.

C
1
Res= fact(N-1)*N;

компилятор смотрит на эту строку и что он делает ? он обращается к функции, только N делает на еденицу меньше, чему бы не было равно N, мы когда нибудь дойдём и оно будет равно еденице. И только когда оно будет равно еденице мы начнём возвращататься на те места с которых мы ушли, то есть мы начнём возвращать наш результат res, и куда же он вернётся ?
ну конечно же туда где мы его последний раз вызывали тоесть в нашу формулу
[C]Res= fact(N-1)*N;[/С]
потом мы снова отрезультируем (вернём результат) и снова вернёмся к формуле, то есть код будет считываться примерно вот так вот

C
1
2
3
4
5
 int fact(int N) 
{
           int Res;
    if (N > 1) {
        Res= fact(N-1)*N;

// fact (N-1) снова вызывает функцию, тоесть

C
1
2
3
4
5
int fact(int N) 
{
           int Res;
    if (N > 1) {
        Res= fact(N-1)*N;

// и так пока N будет больше 1
...................

C
1
2
3
4
5
6
7
8
9
10
11
int fact(int N) 
{
           int Res;
    if (N > 1) { // когда же мы наконец-то сравняем N с 1, то 
        Res= fact(N-1)*N; 
           }    
            else {
        Res = 1;     // мы наконец-то прийдём в эту точку, тоесть присвоем переменной res eдиницу
    }
 
    return Res; //   и вернём её

// а возвращать будем, туда откуда вызывали, тоесть вот сюда:

C
1
2
3
4
5
6
7
    Res= fact(N-1)*N; // только место  fact(N-1) будет наш Res
           }    
            else {                 
        Res = 1;   // сюда мы даже заходить не будем
    }
 
    return Res;  // а сразу пойдём сюда

// и так далее :

C
1
2
3
4
5
6
7
     Res= fact(N-1)*N; 
           }    
            else {                 
        Res = 1;   
    }
 
    return Res;

// пока не вернёмся в самое самое начало, к самому первому вызову.

C
1
2
3
4
5
6
7
 Res= fact(N-1)*N; 
           }    
            else {                 
        Res = 1;   
    }
 
    return Res;

// теперь мы уже будем возвращать рес не в функцию факт, а в инт меин () ...

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

@novi4ok · 21.09.2009, 00:49

что конкретно непонятно с рекурсией?

@andy2050 · 21.09.2009, 13:29 **[ТС]**

just_a_cat -> Спасибо огромное за такое тщательное и последовательное объяснение! Ещё раз уложил всё по полочкам. В принципе я знал что нужна базовая задача и задача которая сводится к базовой.
Что мне действительно не понятно в "моём ханойском коде", так это двойная рекурсия, где функция вызывает ещё ту же самую функцию 2 раза... Не могу вьехать в последовательность выполнения этой рекурсии!

@just_a_cat · 26.09.2009, 15:04

хм... последовательно ....
ну сначала много раз делаем этот кусок кода (нум=3) :

C
1
2
3
4
5
void hanoy(int num,char a,char b,char c)
{
if(num>0)
{
hanoy(num-1,a,c,b);

запоминаем, передаём, запоминаем, передаём ... нум=0. Мы не проходим на чек поинте вот тут:

C
1
if(num>0)

поэтому возвращаем (возвращаем и нум который равен 1, потому что последний раз когда мы его запоминали он был равен 1) и начинаем делать вот этот кусок:

C
1
2
3
4
cout<<a<<" -> "<<c<<endl;
hanoy(num-1,b,a,c);
}
}

нум будет равно 0, поэтому мы опять обходим чек поинт первый и просто вернём вот суда же:

C
1
2
3
4
cout<<a<<" -> "<<c<<endl;
hanoy(num-1,b,a,c);
}
}

но вернём уже нум=2. То есть, нам таки уже дадут пройти чек поинт

смотрим что будет:

C
1
2
3
4
5
void hanoy(int num,char a,char b,char c)
{
if(num>0)
{
hanoy(num-1,a,c,b);

оп и мы снова входим и вызовем функцию как в первый раз, только в этот раз мы будем в ней крутиться не так долго )
и так далее .....
запоминаем, передаём, запоминаем, передаём .... возвращаем, передаём, запоминаем, выводим, передаём, запоминаем, возвращаем ....

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

Новые блоги и статьи Все статьи Все блоги /
Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом	http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .

@Somebody 2838 / 1647 / 254 Регистрация: 03.12.2007 Сообщений: 4,222
	19.09.2009, 18:02
	Ханойская башня - тут и алгоритм, и ещё рисунок в тему. 0

@odip 7176 / 3234 / 82 Регистрация: 17.06.2009 Сообщений: 14,164
	20.09.2009, 18:43
	Чтобы понять рекурсию нужно сначала понять рекурсию. 0

@novi4ok 556 / 510 / 25 Регистрация: 23.07.2009 Сообщений: 2,359 Записей в блоге: 1
	21.09.2009, 00:49
	что конкретно непонятно с рекурсией? 0

@andy2050 0 / 0 / 0 Регистрация: 18.09.2009 Сообщений: 3
	21.09.2009, 13:29 [ТС]
	just_a_cat -> Спасибо огромное за такое тщательное и последовательное объяснение! Ещё раз уложил всё по полочкам. В принципе я знал что нужна базовая задача и задача которая сводится к базовой. Что мне действительно не понятно в "моём ханойском коде", так это двойная рекурсия, где функция вызывает ещё ту же самую функцию 2 раза... Не могу вьехать в последовательность выполнения этой рекурсии! 0

Ребята, объясните пожалуйста эту рекурсию!

Решение