VPF::Помогите пожалуйста полностью "исследовать" рекурс

Killer_13

Дата 17.6.2009, 19:16 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 740
Регистрация: 12.1.2008
Где: Germany

Репутация: 1
Всего: 1

Здравствуйте, давно я не задавал глупых вопросов, решил опять начать. smile

Значит, - началась моя подготовка к экзамену по программированию "С", готовлюсь тщательно, так как хочу сдать на хорошую оценку, разбираю все что необходимо. Решил полностью разобраться с рекурсией, вот уже пол дня прошел, пока кажеться чуток протоптал, но если в общем, то почти на месте топчусь, перечитал множество примеров и литературы, решил еще и здесь спросить, может че кто подскажет.
Значит, возьмем самый простой пример рекурсии, - возведение в степень.

Уже раз 20 с помощью дебаггера исследовал принцип работы задачи не могу до конца понять.

Код


#include <stdio.h>
#include <math.h>

int power(int,int);

int main()
{
    int base,exp;
    //char symb;
    printf("Geben base->");
    scanf("%d",&base);
    printf("Geben- exponent>");
    scanf("%d",&exp);
    printf("\n\n\n%d",power(base,exp));

   return 0;
}

int power(int base,int exp)
{
   int p;
   
   if(exp) {
       p=base*power(base,exp-1);
       printf("p=%d\n",p);
       return p;
   }
   else
   return 1;
}

Значит.. попробую обьяснить, что именно мне не понятно.
1.Передали мы в ф-цию два значения,(к примеру 3 и3), иф проработал пока ехр не стала нуль вышол на ретурн 1 и аж потом начал переменной р присваивать9, и 27. так вот, почему ретурн 1 повернул это все таким образом?

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

2. вот например как мы можем умножать значение base*power(base,exp-1) если в ф-ции значение base не меняется, а значение ехр меняется, как именно происходит умножение числа на ф-цию с двумя параметрами.

думаю если кто в 2ух словах напишет, картина станет четче.
Пасибо!

zim22

Дата 17.6.2009, 19:24 (ссылка)

(нет голосов)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 29
Всего: 69

Цитата(Killer_13 @ 17.6.2009, 19:16

)

думаю если кто в 2ух словах напишет, картина станет четче.

так понятней?

Код


int power(int base,int exp)
{
  printf("base: %d; ", base);
  printf("exp: %d\n", exp);
   int p;

   if(exp) {
       p=base*power(base,exp-1);
       printf("return p: %d\n", p);
       return p;
   }
   else {
     printf("return 1\n");
     return 1;
   }
}

Это сообщение отредактировал(а) zim22 - 17.6.2009, 19:37

--------------------

C++ FAQ Lite

Killer_13

Дата 17.6.2009, 19:44 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 740
Регистрация: 12.1.2008
Где: Germany

Репутация: 1
Всего: 1

Чуток яснее стало

Я чуток попробовал подправить

Код


int power(int base,int exp)
{
    int p;
  printf("base: %d; ", base);
  printf("exp: %d;", exp);
  printf("p: %d\n", p);

   if(exp) {
       p=base*power(base,exp-1);
       printf("return p: %d\n", p);
       return p;
   }
   else {
     printf("return 1\n");
     return 1;
   }
}

почему р постоянно выдает -1.

Но вот еще понять не могу, как ретурн1 заставляет прыгнуть
вот сюда

Код


 printf("return p: %d\n", p);
       return p;

и напечатать три раза р? :(

zim22

Дата 17.6.2009, 19:57 (ссылка)

(нет голосов)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 29
Всего: 69

Цитата(Killer_13 @ 17.6.2009, 19:44

)

еще понять не могу, как ретурн1 заставляет прыгнуть

есть функция допустим

Код


void fcn(int i) {
  if (i == 0) return;
  fcn(--i);
  cout << "hello";
}

когда рекурсивно последний вызов функции завершится (i = 0), то мы возвратимся к строчке fcn(--i); и программа начнёт выполняться со следующей строки.
ещё понятней стало? smile

--------------------

C++ FAQ Lite

Killer_13

Дата 17.6.2009, 20:18 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 740
Регистрация: 12.1.2008
Где: Germany

Репутация: 1
Всего: 1

Понятней, а сколько раз р печатать? Она печатает пока не освободится стек или...?
вот - из вашего рисунка понятно, что умножаться начинает с последнего элемента, тоисть с 2*(2,0) - откуда там взялась 1?
И все так не понял как ретурн 1 прыгает в принтф и заставляет р печататься, а откуда тогда р берет значения, если мы работаем со строкой которая ниже строки которая определяет значение р?

А почему именно умножается второе значение функции? тоисть 2*(2,0) 0 заменяется на 1 откуда?

zim22

Дата 17.6.2009, 21:36 (ссылка)

(нет голосов)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 29
Всего: 69

Killer_13, слишком много вопросов smile

возьмите пример попроще на рекурсию.
например факториал. или число Фибоначчи.
http://ru.wikipedia.org/wiki/Рекурсия

Цитата(Killer_13 @ 17.6.2009, 20:18

)

откуда там взялась 1?

Код


int power(2, 0) {
  if (exp) // не зашли сюда
  else
  return 1; // вот отсюда взялась
}

Это сообщение отредактировал(а) zim22 - 17.6.2009, 21:41

--------------------

C++ FAQ Lite

Killer_13

Дата 17.6.2009, 21:42 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 740
Регистрация: 12.1.2008
Где: Germany

Репутация: 1
Всего: 1

разбирал я все єти примеры, че т результат один.. :(
да вот сюда и обратился с надеждой услышать ответы на свои вопросы, хочется четко понять как работает. smile

mes

Дата 17.6.2009, 22:11 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 79
Всего: 250

Цитата(Killer_13 @ 17.6.2009, 20:42

)

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

Код


void repeat (int n)
{

  if (n==0) return; // 1.
  repeat (n-1); 
  return; // 2.
}
repeat (5);

В раазвернутом коде выглядит так :

Код



 repeat (5)
    repeat (4)
       repeat (3)
           repeat (2)
              repeat (1)
                 repeat (0) 
                 return;  //1.
              return; //2.
          return; //2.
       return; //2.
    return; //2.
 return; //2.

или в текстовом виде

Код


если условие сработало, то возвращаемся// не сработало
   иначе  идем на шаг вглубь рекурсии, // идем в глубь
   если условие сработало, то возвращаемся // не сработало
        иначе  идем на шаг вглубь рекурсии, // идем в глубь
        если условие сработало, то возвращаемся // не сработало
              иначе  идем на шаг вглубь рекурсии, // идем в глубь
              если условие сработало, то возвращаемся // не сработало
                   ....       
                       ....  
                          .... // тут сработало условие ;)
                       ....
                    ....
               возвращаемся
        возвращаемся
    возвращаемся
возвращаемся

Это сообщение отредактировал(а) mes - 18.6.2009, 11:54

--------------------

http://opendots.net

Killer_13

Дата 18.6.2009, 11:48 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 740
Регистрация: 12.1.2008
Где: Germany

Репутация: 1
Всего: 1

Почти все понятно, но хочу задать еще несколько вопросов. :_

например если вот например, в предыдущем примере.

Код


void repeat (int n)
{
  if (n==0) return; // 1.
  repeat (n-1); 
  return; // 2.
repeat (5);
}

если эту ф-цию вызывать в мейн програм, то нужно задать какое то стартовое значение. Например repeat(3);

Код


#include <stdio.h>

void repeat(int);

int main()
{
  repeat(3);

   return 0;
}

void repeat (int n)
{
  int o=23;
  if (n==0) return; // 1.
  repeat (n-1);
  return printf ("burum\n%d\n",o); // 2.
repeat (5);
}

1.а зачем последняя строчка repeat(5) - что она делает, если я задал уже значение?

а вот почему в дебаггере, переменная о обьявляется и ей присваивается какое то произвольное число, а после прохождения строчки она становиться значением 23, а потом снова наново...

2.Я хочу спросить, почему в начале переменной о присваивается какое нибудь значение?

mes

Дата 18.6.2009, 11:56 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 79
Всего: 250

Цитата(Killer_13 @ 18.6.2009, 10:48

)

1.а зачем последняя строчка repeat(5) - что она делает, если я задал уже значение?

это опечатка произошла (исправил), сорри.
repeat (5) не относится к телу функции - это условный вызов функции из мейн , с параметром 5.

--------------------

http://opendots.net

mes

Дата 18.6.2009, 12:28 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 79
Всего: 250

Цитата(Killer_13 @ 18.6.2009, 10:48

)

2.Я хочу спросить, почему в начале переменной о присваивается какое нибудь значение?

переменная о локальная, и для каждого вызова функции создается новый экземпляр. Итого при при repeat (5) в Вашем случае создается 6 экземпляров о (при n=5,4,3,2,1,0) smile

вот попробуйте поэксперементировать с этим примером :

Код


struct create_counter //тип переменной, которая будет при созданнии изменять счетчик ее экземпляров и выводить сообщение
{
    create_counter (int& counter, const std::string& name) { std::cout <<name <<++counter<<std::endl; }
};
int aa;
int bb;
int cc;

void set_cout_margin (int value) // устанавливает отступ для вывода
{
     std::cout.width(value*4);std::cout << " ";
}
void repeat (int max, int n=0)  // max, значение которого  должно достигнуть n для окончания рекурсии
{
   set_cout_margin  (n);
   std::cout << "{ n=" <<n <<std::endl;

   set_cout_margin  (n);
   create_counter(aa, "  AA_");

  if (n==max) return; // 1.
    set_cout_margin  (n);
    create_counter(bb, "  BB_");
  repeat (max, n+1);
    set_cout_margin  (n);
    create_counter(cc, "  CC_");

   set_cout_margin  (n);
   std::cout << "} "<<n<<std::endl;;
  return; // 2.
}

using namespace std;
int main () { cout << endl;

repeat(4,0);
}

он на консоль будет выводить, что происходит внутри.
надеюсь что такое структура и с передачей по ссылке Вы знакомы.
smile

--------------------

http://opendots.net

Killer_13

Дата 18.6.2009, 12:54 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 740
Регистрация: 12.1.2008
Где: Germany

Репутация: 1
Всего: 1

Пасибо, за последний пример, но он на С++ - вижу, что легко можно переделать на С, но кажеццо я врубился как работает алгоритм рекурсии. smile

Спасибо всем ответившим. smile

Двигаюсь дальше. smile

mes

Дата 18.6.2009, 13:09 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 79
Всего: 250

Цитата(Killer_13 @ 18.6.2009, 11:54

)

Пасибо, за последний пример, но он на С++

ага.. привык что большинство вопросов по С++ и даже не посмотрел, что у Вас чистый Си.
В общем рекурсия в развернутом виде выглядит так :

Код


{
 {
  { 
   {
    ...
   }
  }
 }
}

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

Это сообщение отредактировал(а) mes - 18.6.2009, 13:10

--------------------

http://opendots.net

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »