9 / 9 / 7
Регистрация: 23.11.2012
Сообщений: 94
1

Рекурсия

19.10.2013, 14:49. Показов 1041. Ответов 5
Метки нет (Все метки)

Есть такой код. В нем рисуется что то вроде линейки. Данный код предназначен для иллюстрации работы рекурсии. Может мне кто нибудь объяснить. Вот при первом вызове subdivide палочка ставится посередине, значение середины 32. Далее палочки ставятся на 32, 16 и 48, ок. Но что происходит потом я не могу понять. Происходит вызов subdivide с level 3, она ставит палочку на 32 и вызывает subdivide с level 2, которая, в свою очередь ставит палочку на 16 и вызывает subdivide с level 1, которая ставит палочку на значении 8. Но как в этом рекурсивном цикле палочка оказывается на значении 24 я не понимаю. Откуда она его берёт!?!? Объясните пожалуйста, всю голову сломал уже....

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
29
30
31
32
33
34
35
36
37
38
39
// ruler.cpp -- using recursion to subdivide a ruler
#include <iostream>
const int Len = 66;
const int Divs = 6;
void subdivide(char ar[], int low, int high, int level);
int main()
{
    char ruler[Len];
    int i;
    for (i = 1; i < Len - 2; i++)
        ruler[i] = ' ';
    ruler[Len - 1] = '\0';
    int max = Len - 2;
    int min = 0;
    ruler[min] = ruler[max] = '|';
    std::cout << ruler << std::endl;
    for (i = 1; i <= Divs; i++)
    {
        subdivide(ruler,min,max, i);
        std::cout << ruler << std::endl;
        for (int j = 1; j < Len - 2; j++)
            ruler[j] = ' ';  // reset to blank ruler
    }
    // std::cin.get();
    std::system("PAUSE");
    return 0;
}
 
void subdivide(char ar[], int low, int high, int level)
{
    if (level == 0)
        return;
    int mid = (high + low) / 2;
    ar[mid] = '|';
    std::cout << "Recursion at level: " << level << std::endl
    << "Mid = " << mid << std::endl;
    subdivide(ar, low, mid, level - 1);
    subdivide(ar, mid, high, level - 1);
}
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
19.10.2013, 14:49
Ответы с готовыми решениями:

Рекурсия
Помогите написать функцию которая будет считать эту рекуррентную формулу с помощью рекурсии

рекурсия B c++
пожалуйста помогите,почему не работает? дело в рекурсии,функция func1 вызывается много раз.. ...

Рекурсия, почему есть ограничение на входные данные
Сегодня баловался с рекурсией. получилось типа цикла, только из функции #include &lt;iostream&gt;...

Рекурсия
#include&lt;stdio.h&gt; void gg(int a,int b) { int i=0; if(a==20) return; printf(&quot;%d\n&quot;,a);...

5
zzzZZZ...
526 / 357 / 94
Регистрация: 11.09.2013
Сообщений: 2,040
19.10.2013, 16:50 2
знакомая програмка из Стивена Прата))

C++
1
2
3
 
subdivide(ar, low, mid, level - 1);
subdivide(ar, mid, high, level - 1)
обрати внимание функция 1ый раз вызывается для low mid, 2ой, для mid high

low=0, high = LEN-2=64,
1) mid = 0 + 64 / 2 = 32
2) mid+high=32+64=96
mid=96/2=48
0
9 / 9 / 7
Регистрация: 23.11.2012
Сообщений: 94
19.10.2013, 18:53  [ТС] 3
Да, из него родимого. Нет, это я понял. Меня интересует именно то, каким образом функция получает значение 24 в переменную mid. Потому что это значение должно получаться именно при вызове первой функции с mid в качестве high.
Ну вот например: level = 3, значит при вызове первой функции level-1 = 2. Получаем что mid = 16 так? то бишь 32/2. Потом вызывается эта же функция с level -1, level = 1. Получается mid = 16/2 = 8, так?. Далее функция опять вызовет сама себя но натолкнется на проверку условия level == 0 и выполнит оператор return. Что происходит дальше? откуда программа берет значение 24 в переменную mid?

Добавлено через 1 час 35 минут
в общем я вставлял в код принтф и заметил такую штуку. В определенный момент, при вызове функции, значение low в ней становится 16 а high = 32, они складываются, делятся на 2 и получается 24. НО КАК!?!? Ведь при вызове функции один параметр high или low всегда константый.... либо low = 0 и high переменная, либо high = 64 а low переменная. Как они обе поменяли значение!?!?!
0
zzzZZZ...
526 / 357 / 94
Регистрация: 11.09.2013
Сообщений: 2,040
19.10.2013, 20:39 4
Цитата Сообщение от fuzzytoozy Посмотреть сообщение
Да, из него родимого. Нет, это я понял. Меня интересует именно то, каким образом функция получает значение 24 в переменную mid. Потому что это значение должно получаться именно при вызове первой функции с mid в качестве high.
Ну вот например: level = 3, значит при вызове первой функции level-1 = 2. Получаем что mid = 16 так? то бишь 32/2. Потом вызывается эта же функция с level -1, level = 1. Получается mid = 16/2 = 8, так?. Далее функция опять вызовет сама себя но натолкнется на проверку условия level == 0 и выполнит оператор return. Что происходит дальше? откуда программа берет значение 24 в переменную mid?

Добавлено через 1 час 35 минут
в общем я вставлял в код принтф и заметил такую штуку. В определенный момент, при вызове функции, значение low в ней становится 16 а high = 32, они складываются, делятся на 2 и получается 24. НО КАК!?!? Ведь при вызове функции один параметр high или low всегда константый.... либо low = 0 и high переменная, либо high = 64 а low переменная. Как они обе поменяли значение!?!?!
долго пытался понять то, что тебе не понять...

low и high не меняются, меняется только mid. Мы при вызове функции, просто от середины меняем границы функции, в одном случае вместо low ставим mid, в другом вместо high. Ты функцию вызываешь первый раз, subdivide(ar, low(0), high(64), level - 1);
потом она вызывает сама себя с разными значениями:
subdivide(ar, low(0), mid(32), level - 1);
subdivide(ar, mid(32), high(64), level - 1);
дальше mid снова меняется, и для каждой функции из этих 2ух он будет свой, т.е. в 1ом случае (0+32)/2=16, в другом (32+64)/2=48, потом каждая из функций вызывает другие две себя, дргумими значениями mid

я не понимаю что непонятно...)
0
Модератор
Эксперт С++
11348 / 9312 / 5594
Регистрация: 18.12.2011
Сообщений: 24,850
19.10.2013, 21:04 5
Легче будет понять в отладчике.
Поставьте останов на строку 32.
И далее выполняйте код построчно с заходом в функции
(в VS - клавиша F11). При этом следите за переменной mid.
0
9 / 9 / 7
Регистрация: 23.11.2012
Сообщений: 94
19.10.2013, 21:32  [ТС] 6
Цитата Сообщение от dzrkot Посмотреть сообщение
долго пытался понять то, что тебе не понять...

low и high не меняются, меняется только mid. Мы при вызове функции, просто от середины меняем границы функции, в одном случае вместо low ставим mid, в другом вместо high. Ты функцию вызываешь первый раз, subdivide(ar, low(0), high(64), level - 1);
потом она вызывает сама себя с разными значениями:
subdivide(ar, low(0), mid(32), level - 1);
subdivide(ar, mid(32), high(64), level - 1);
дальше mid снова меняется, и для каждой функции из этих 2ух он будет свой, т.е. в 1ом случае (0+32)/2=16, в другом (32+64)/2=48, потом каждая из функций вызывает другие две себя, дргумими значениями mid

я не понимаю что непонятно...)
Ты просто не понимаешь что я спрашиваю. Я понимаю что меняется значение только mid и оно передается как high или low. Суть вопроса не в том КАК это происходит. А каким образом получается число 24 в mid. Ты проследи цикл и попробуй мне объясни это. там получается так что в функции которой ПЕРЕДАЛИ MID в качестве параметра low = 16, а high = 32. Я и спрашиваю каким образом получаются такие значения, если у первого вызова функции low всегда = 0 и в качества параметра high передается mid, а у второго high всегда = 64 и в качестве параметра low. Тогда получается что одновременно могут изменяться только либо high либо low в одной функции, другое значение всегда остается постоянным 0 или 64, тогда каким образом они приняли вид 16 и 32....я не понимаю

Добавлено через 11 минут
Цитата Сообщение от zss Посмотреть сообщение
Легче будет понять в отладчике.
Поставьте останов на строку 32.
И далее выполняйте код построчно с заходом в функции
(в VS - клавиша F11). При этом следите за переменной mid.
я знаю в каком месте она меняется таким образом, я просто не понимаю почему и как именно таким образом. Откуда берется значение 24
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
19.10.2013, 21:32

Рекурсия: убрать ограничение, требующее, чтобы аргумент был неотрицательным
Доброго времени суток. Уважаемые ГУРУ, есть одна проблема. Ниже представлен код, в котором параметр...

Рекурсия: вычисление функции по формуле
Помогите пожалуйста сделать рекурсию Даны n и m, найти X и Y, при X1=Y=1 X=X+Y/i^2 Y=Y=X/i^2

Рекурсия: возведение числа в целую степень
Сделайте одну програмку используя рекурсию. Очень нужно... Срочно. 1. Реализовать поиск НОД; ...

Рекурсия: возведение числа в степень
Приветствую. Прошу помощи. Нужно посчитать Xn по формуле: С рекурсией плохо дружу. Заранее...


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

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.