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

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

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

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

@lemegeton · 17.12.2010, 23:47

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

еще нужно сказать, чего не пишут в сишной лит-ре (по крайней мере я не встречал) в стек так же кладется адрес строки

Это в основном пишут в учебниках по ассемблеру. Там, где учат вызывать подпрограммы. Там же написано, что в стеке еще могут лежать состояния флагов процессора, что, правда, уже совсем бессмысленная в данном контексте информация.

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

Помним, что по соглашению cdecl данные передаются справа налево, поэтому в стек будут «втолкнуты» (от англ. push) сначала переменная z, потом y, потом x.

Продемонстрируем:

C++

#include <iostream>
 
using namespace std;
 
// переменные в стеке оказываются в обратном порядке
void f(int a, int b, int c)
{
        int *p = &c;
        cout << *(p+1) << endl;
        cout << *(p+2) << endl;
}
 
int main(int argc, char *argv[])
{
        f(1, 2, 3);
        return 0;
}

silent_1991 · 18.12.2010, 11:02

KOPC1886,
А что по-подробнее-то? Ничего не считывается. Вот вы когда вызываете функцию, например, sqrt, в функции main, вы передаёте ей параметр - число. Оно копируется в собственную переменную функции sqrt, там с этой переменной происходят какие-то манипуляции и функция возвращает результат. Так вот тут то же самое, при вызове функции HanoiTowers ей передаются какие-то аргументы, они копируются в собственные переменные функции, она в свою очередь вызывает саму себя (теоретически), но фактически это уже другая функция с другими локальными параметрами, в которые и копируются значения тех параметров, которые этой новой функции передала вызывающая функция. Т.н. "обмен" происходит только потому, что сама вызывающая функция передаёт вызываемой свои же параметры, но в другом порядке. Т.е., например, у нас есть функция HanoiTowers(int n, int from, int buf, int to), и мы изначально вызвали HanoiTowers(10, 1, 2, 3), а она вызвала рекурсивно HanoiTowers(9, 1, 3, 2), т.е. в первой функции from был равен 1, buf - 2, to - 3, а в новой функции стало from - 1, buf - 3, to - 2, вот вам и весь "обмен". Я говорю "обмен" в кавычках, потому что обмена никакого нет, ведь вызванная функция просто получает в качестве параметров с теми же именами, что и вызывающая, перемешанные значения.

Не по теме:

Тьфу, спасибо случайно жамкнул)))

@KOPC1886 · 18.12.2010, 17:25 **[ТС]**

silent_1991, а вот обратно при втором вызове НanoiTowers(int n, int from, int buf, int to) значения опят встают на свои места (то есть 1, 2, 3). Значения опять возвращаются! Я не совсем понимаю как происходит это "обмен". Как переменные записываются в память и как считываются?

silent_1991 · 18.12.2010, 17:42

Да написал же я, обмена никакого нет! У каждой функции будут свои from, buf, to. И при вызове из первой функции (у неё from1 = 1, buf1 = 2, to1 = 3) второй, у второй будут уже свои from2 = 1, buf2 = 3, to2 = 2. И когда мы выйдем из второй функции (которая вывела свои from2, buf2 и to2), её собственные переменные уничтожатся (мы их уже вывели, они нам больше не нужны), а по возвращении в первую функцию она оперирует снова со своими from1, buf1 и to1.

@KOPC1886 · 18.12.2010, 22:41 **[ТС]**

silent_1991, а почему, кстати, первый вызов функции происходит так НanoiTowers(int n, int from, int buf, int to)-НanoiTowers(int n, int from, int buf, int to)-НanoiTowers(int n, int from, int buf, int to)... до тех пор пока n не стане равным 1? А все остальные вызовы идут последовательно?

Добавлено через 2 часа 24 минуты
А как мне тогда преподаватель объяснять, почему и как здесь происходит якобы "обмен" значений?
Как объяснить работу этого кода?

silent_1991 · 19.12.2010, 03:30

Что значит "последовательно"? Здесь такого не будет. Тут будет достаточно обширное дерево вызовов, попробуйте на бумажке нарисовать хотя бы для n = 5

@KOPC1886 · 19.12.2010, 15:14 **[ТС]**

Я написал вызов функции для n=4 посмотрите так?

silent_1991 · 20.12.2010, 02:29

KOPC1886, да. Так что вы имели ввиду под "последовательно"?

silent_1991 5055 / 3115 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	19.12.2010, 03:30	26
	Что значит "последовательно"? Здесь такого не будет. Тут будет достаточно обширное дерево вызовов, попробуйте на бумажке нарисовать хотя бы для n = 5 1

@KOPC1886 27 / 6 / 0 Регистрация: 28.10.2010 Сообщений: 352
	19.12.2010, 15:14 [ТС]	27
	Я написал вызов функции для n=4 посмотрите так? Миниатюры 0

silent_1991 5055 / 3115 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	18.12.2010, 11:02	22
	KOPC1886, А что по-подробнее-то? Ничего не считывается. Вот вы когда вызываете функцию, например, sqrt, в функции main, вы передаёте ей параметр - число. Оно копируется в собственную переменную функции sqrt, там с этой переменной происходят какие-то манипуляции и функция возвращает результат. Так вот тут то же самое, при вызове функции HanoiTowers ей передаются какие-то аргументы, они копируются в собственные переменные функции, она в свою очередь вызывает саму себя (теоретически), но фактически это уже другая функция с другими локальными параметрами, в которые и копируются значения тех параметров, которые этой новой функции передала вызывающая функция. Т.н. "обмен" происходит только потому, что сама вызывающая функция передаёт вызываемой свои же параметры, но в другом порядке. Т.е., например, у нас есть функция HanoiTowers(int n, int from, int buf, int to), и мы изначально вызвали HanoiTowers(10, 1, 2, 3), а она вызвала рекурсивно HanoiTowers(9, 1, 3, 2), т.е. в первой функции from был равен 1, buf - 2, to - 3, а в новой функции стало from - 1, buf - 3, to - 2, вот вам и весь "обмен". Я говорю "обмен" в кавычках, потому что обмена никакого нет, ведь вызванная функция просто получает в качестве параметров с теми же именами, что и вызывающая, перемешанные значения. Не по теме: Тьфу, спасибо случайно жамкнул))) 2

@KOPC1886 27 / 6 / 0 Регистрация: 28.10.2010 Сообщений: 352
	18.12.2010, 17:25 [ТС]	23
	silent_1991, а вот обратно при втором вызове НanoiTowers(int n, int from, int buf, int to) значения опят встают на свои места (то есть 1, 2, 3). Значения опять возвращаются! Я не совсем понимаю как происходит это "обмен". Как переменные записываются в память и как считываются? 0

silent_1991 5055 / 3115 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	18.12.2010, 17:42	24
	Да написал же я, обмена никакого нет! У каждой функции будут свои from, buf, to. И при вызове из первой функции (у неё from1 = 1, buf1 = 2, to1 = 3) второй, у второй будут уже свои from2 = 1, buf2 = 3, to2 = 2. И когда мы выйдем из второй функции (которая вывела свои from2, buf2 и to2), её собственные переменные уничтожатся (мы их уже вывели, они нам больше не нужны), а по возвращении в первую функцию она оперирует снова со своими from1, buf1 и to1. 2

@KOPC1886 27 / 6 / 0 Регистрация: 28.10.2010 Сообщений: 352
	18.12.2010, 22:41 [ТС]	25
	silent_1991, а почему, кстати, первый вызов функции происходит так НanoiTowers(int n, int from, int buf, int to)-НanoiTowers(int n, int from, int buf, int to)-НanoiTowers(int n, int from, int buf, int to)... до тех пор пока n не стане равным 1? А все остальные вызовы идут последовательно? Добавлено через 2 часа 24 минуты А как мне тогда преподаватель объяснять, почему и как здесь происходит якобы "обмен" значений? Как объяснить работу этого кода? 0

silent_1991 5055 / 3115 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	20.12.2010, 02:29	28
	KOPC1886, да. Так что вы имели ввиду под "последовательно"? 0