Блог

Здравствуйте, я изучаю рекурсию, и в настоящее время мне нужно решить пару сложных задач — вот одна из рекурсивных функций

 int rec(int niz[], int start, int end){

if (start == end)
{

    return niz[start]; // vraca zadnji
}

int temp = rec(niz, start 1, end);


// control output
cout << "n-----n";
cout << "start "  << start << endl;
cout << "niz[start] "  << niz[start] << endl;
cout << "end "  << end << endl;
cout << "temp "  << temp << endl;
cout << "n-----------------------------------------n";
//contrl output end

return ((niz[start] < temp) ? niz[start] : temp);
}
  

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

     int niz[] = {1,2,3,4,5,6,7}; 
    cout << rec(niz, 0, 3);
  

и вот мой вывод:

 -----
start 2
niz[start] 3
end 3
temp 4
------------------

----- 
start 1
niz[start] 2
end 3
temp 3
------------------

-----
start 0
niz[start] 1
end 3
temp 2
------------------

1
  

кто-нибудь может объяснить мне, как вычисляется и возвращается значение temp и как я получаю 1 в качестве возврата этой функции?

Заранее благодарю вас!

Рекурсивная функция — это функция, которая вызывает саму себя.

 int temp = rec(niz, start 1, end);
  

Здесь вы вызываете функцию «rec» внутри one, но с измененным параметром (start 1). Вы вызываете эти функции внутри друг друга до тех пор, пока «начало» не будет равно «концу» (затем оно возвращается)

 if (start == end)
{

    return niz[start]; // vraca zadnji
}
  

После возврата самого глубокого массива второй самый глубокий массив продолжает свой поток, печатая некоторую информацию.

 cout << "n-----n";
cout << "start "  << start << endl;
cout << "niz[start] "  << niz[start] << endl;
cout << "end "  << end << endl;
cout << "temp "  << temp << endl;
cout << "n-----------------------------------------n";
  

Затем он возвращает наименьшее значение между niz [start] и temp (локальные значения).

 return ((niz[start] < temp) ? niz[start] : temp);
  

Затем третий по глубине массив продолжает свой поток и так далее. Пока не дойдет до первой функции.

В вашей основной части вы устанавливаете end равным 3, поэтому он выполняет операцию над первыми 3 элементами (он переходит к четвертому элементу, но ничего не делает, кроме возврата его значения). Вы получаете 1, сравнивая значение niz[0], которое вы передали как start, и temp, возвращаемое рекурсивной функцией (которая оказывается одинаковой). Оно равно, поэтому возвращаемое значение равно niz[0], то есть 1;

При использовании рекурсивных функций у вас должна быть какая-то «точка выхода», которая предотвращает бесконечность рекурсии, т. е.

 if (start == end)
{   
    return niz[start];
}
  

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

 f()
{
    //return condition
    //some work
    f();
    //some work
    //return
}
  

И вы можете посмотреть на них следующим образом

 f()
{
    //some code
    f()
    {
        //some code
        f()
        {
            //some code
            f()
            {
                ...
                //eventually the return condition is met
            }
            //some code
            //return
        }
        //some code
        //return
    }
    //some code
    //return
}
  

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

 f()
{
    f();
}
  

Это приведет к переполнению стека из-за созданных системных данных;

Возможно, вы захотите посмотреть «Начало», чтобы лучше понять его 🙂

  rec(niz, 0, 3)                          (D)
  |
  ---->rec(niz, 1, 3)                    (C)
        |
        ----> rec(niz, 2, 3)             (B)
               |
               ----> rec(niz, 3, 3)      (A)
  

Вы вызываете (D), который вызывает (C) для вычисления temp и так далее вплоть до (A). В (A) start==end и это возвращает niz[3] = 4 .

В (B):

temp = 4 (результат выполнения (A))

start = 2

As 4 больше, чем niz[start] = 3 (B) возвращает 3

В (C):

temp = 3 (результат выполнения (B))

start = 1

As 3 больше, чем niz[start] = 2 (B) возвращает 2

В (D):

temp = 2 (результат (C))

start = 0

As 2 больше, чем niz[start] = 1 (B) возвращает 1

Ваша рекурсивная строка находится перед блоком инструкции print. По природе рекурсии она вызывает функцию в этой рекурсивной строке и останавливает выполнение вызывающей функции до тех пор, пока вызываемый объект не завершит работу. Поэтому вы вызываете следующий элемент, который должен быть обработан, прежде чем печатать текущий элемент.

В вашем примере происходит следующее:

 Layer 1:
    Is start equal to end? No.
    What is the result of the next element? Don't know yet, recurse.
Layer 2:
    Is start equal to end? No.
    What is the result of the next element? Don't know yet, recurse.
Layer 3:
    Is start equal to end? No.
    What is the result of the next element? Don't know yet, recurse.
Layer 4:
    Is start equal to end? Yes!
    Return the current element, 4.
    End layer 4.
Layer 3:
    Now know next element, start printing for the 3rd element.
    Return 3.
    End layer 3.
Layer 2:
    Now know the next element, start printing for the 2nd element.
    Return 2.
    End layer 2.
Layer 1:
    Now know the next element, start printing for the 1st element.
    Return 1.
    End layer 1.
End program.
  

Как вы можете видеть, элементы массива печатаются в обратном порядке, потому что инструкции print выполняются после рекурсивного вызова. Я бы хотел, чтобы они печатались по порядку, распечатайте их перед рекурсивным вызовом или создайте буфер и добавьте каждый раздел печати в начало буфера.