Задача на рекурсию - почему вроде бы ошибочный код внутри работает правильно?

@Thor · Регистрация: 12.12.2014

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

Изучаю учебник C++, решаю задачки в конце глав.

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

Я с наскоку написал вот такой код:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
//#include <iomanip>
//#include <string>
using namespace std;
 
template < class T >
T recursiveMin(T a[], int size) {
    if (size == 1)
        return a[0];
 
    int i = size - 1;
    if (a[i] < recursiveMin(a, i))
        return a[i];
}
 
int main() {
    int const n = 5;
    int a[n] = { 2, 1, 3, 4, 5 };
    cout << "min:  " << recursiveMin(a, n) << endl;
    return 0;
}

Этот код работает правильно для самых разных массивов, однако более детально на него поглядев, мне показалось, что работать он, как мне кажется, не должен!

В функции recursiveMin есть два оператора if, и оператор return выполняется только тогда, когда хотя бы одно из проверяемых условий верно. Однако самый первый вызов функции recursiveMin (непосредственно из main) приводит к тому, что оба условия в if ложны, и return, который должен вернуть в main значение, в нём просто отсутствует.

Получается, что если вызов функции на верхнем уровне рекурсии не доходит до return, то в main возвращается значение из вызова на какой-то глубине рекурсии (очевидно, самый последний return, который был встречен).

Такое поведение, как мне кажется, неожиданно и нелогично. Почему так происходит? И как средствами компилятора (Visual Studio 2015) посмотреть что куда возвращается?

@igorrr37 · 31.12.2016, 06:40

http://stackoverflow.com/quest... rn-a-value
UB, походу. Когда return недостижим то просто возвращается содержимое регистра EAX (?). А хранится там последнее возвращённое значение функции recursiveMin что равно последнему найденному минимуму. Регистры можно посмотреть в VS2015 так: ставишь брейкпоинт и когда он сработает открываешь Debug->Windows->Registers.

С такой ф-цией результат будет неправильный

C++
1
2
3
4
5
6
7
8
9
10
template < class T >
T recursiveMin(T a[], int size) {
    if (size == 1)
        return a[0];
 
    int i = size - 1;
    int ret = recursiveMin(a, i);
    if (a[i] < ret)
        return a[i];
}

@TheCalligrapher · 31.12.2016, 10:02

Эксперимент с return

@Catstail · 31.12.2016, 19:12

Что же... Сомнения вполне обоснованны. Тем более, что код работает неверно.

Вот такой вызов выдает min=5 (а должен -2).

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
#include <iostream>
 
using namespace std;
 
template < class T >
T recursiveMin(T a[], int size)
 {
    if (size == 1)
        return a[0];
 
    int i = size - 1;
    if (a[i] < recursiveMin(a, i))
        return a[i];
 
 
}
 
int main() {
    int const n = 5;
    int a[n] = { -2, 1, 3, 4, 5 };
    int j;
    cout << "min:  " << recursiveMin(a, n) << endl;
    cin >> j;
    return 0;
}

Правильный, на мой взгляд, код может выглядеть так:

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
#include <iostream>
 
using namespace std;
 
template < class T >
T recursiveMin(T a[], int size)
 {
    if (size == 1)
        return a[0];
 
    int i = size - 1;
    int m = recursiveMin(a+1, i);
    if (a[0] < m)
        return a[0];
    else
        return m;    
 
}
 
int main() {
    int const n = 5;
    int a[n] = { -2, 1, 3, 4, 5 };
    int j;
    cout << "min:  " << recursiveMin(a, n) << endl;
    cin >> j;
    return 0;
}

@Fixer_84 · 31.12.2016, 21:24

Thor, держите код. Надеюсь, это то, что нужно:

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 ArrayMin(int A[], int N)
{
if (N == 1) return A[0];
else return min(A[N-1], ArrayMin(A, N-1));
}
 
int main()
{
int N, min;
cout << "Введите размерность массива:" << endl;
cout << "N = ";
cin >> N; 
int *A = new int[N]; 
cout << "Введите сам массив:" << endl;
for (int i = 0; i < N; i++)
{
cin >> A[i]; 
}
min = ArrayMin(A, N);
cout << "Минимальный элемент: " << min << endl;
delete [] A;
system("pause"); 
return 0;
}

@Thor · 31.12.2016, 21:58 **[ТС]**

igorrr37, спасибо за инфу!

TheCalligrapher, почитал тред, помог немного разобраться.

Catstail, у меня ваш код (первый который) даёт правильный ответ (-2), т.е. работает верно (компилятор VS2015).

Fixer_84, спасибо. Вообще, свой код-то я исправил. У меня был чисто методологический вопрос по тому как работает C++ в условиях, когда возвращающая значение функция не достигает return.

@Catstail · 01.01.2017, 18:41

Thor, это не мой, а ваш код. Вот как он работает с отладочной печатью:

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
#include <iostream>
using namespace std;
template < class T >
T recursiveMin(T a[], int size)
 {
    cout << "Enter size=" << size << endl;             
    if (size == 1)
    {   cout << "Return " << a[0] << endl; 
        return a[0];
    }    
 
    int i = size - 1;
    if (a[i] < recursiveMin(a, i))
    {
        cout << "Return " << a[i] << endl;     
        return a[i];
    }    
    cout << "Return ???" << endl;
 
}
 
int main() {
    int const n = 5;
    int a[n] = { 2, 1, 3, -4, 5 };
    int j;
    cout << "min:  " << recursiveMin(a, n) << endl;
    cin >> j;
    return 0;
}

Вывод:

Code
1
2
3
4
5
6
7
8
9
10
11
Enter size=5
Enter size=4
Enter size=3
Enter size=2
Enter size=1
Return 2
Return 1
Return ???
Return -4
Return ???
min:  6618808

Что есть полная чушь...

А вот - правильный код тоже с отладочной печатью:

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
#include <iostream>
using namespace std;
template < class T >
T recursiveMin(T a[], int size)
 {
    cout << "Enter size=" << size << endl;             
 
    if (size == 1)
    {   cout << "Return " << a[0] << endl; 
        return a[0];
    }    
 
    int i = size - 1;
 
    int m = recursiveMin(a+1, i);
 
    if (a[0] < m)
    {
        cout << "Return " << a[0] << endl;
        return a[0];
    }    
    else
    {
        cout << "Return " << m << endl;
        return m;    
    }
 
}
 
int main() {
    int const n = 5;
    int a[n] = { 2, 1, 3, -4, 5 };
    int j;
    cout << "min:  " << recursiveMin(a, n) << endl;
    cin >> j;
    return 0;
}

Вывод:

Code
1
2
3
4
5
6
7
8
9
10
11
Enter size=5
Enter size=4
Enter size=3
Enter size=2
Enter size=1
Return 5
Return -4
Return -4
Return -4
Return -4
min:  -4

@Thor · 01.01.2017, 21:33 **[ТС]**

Catstail, если в первом коде из вашего сообщения закомментить строку 18, то код у меня (на моём компе, с использованием моего компилятора) работает "правильно":

Code
1
2
3
4
5
6
7
8
9
Enter size=5
Enter size=4
Enter size=3
Enter size=2
Enter size=1
Return 2
Return 1
Return -4
min:  -4

Если всё оставить как есть, то работает примерно как у вас.

В данной маленькой программе всё просто, легко увидеть ошибку и исправить её. Но в более сложных программах, если логические операторы написаны с ошибкой и функция не достигает return'а, то ни во время компиляции, ни во время выполнения не возникает ошибок, код работает, и функция что-то возвращает. Я создал эту тему, потому что такое поведение С++ меня озадачило, и хотел в этом разобраться.

@_Ivana · 01.01.2017, 21:44

А варнинг-чекер в ИДЕ молчит по этому поводу? Меня вот в ИДЕЕ заколебало, что даже в целях отладки я не могу вначале длинной функции вставить ретурн тру потому что дескать все что после становится недостижимо и кот даже не компилируется. В плюсовых ИДЕ типа Студии нет такого уродства? Или его надо искать в продуктах от Джет Брайнс типа Клиона? Или вы пишете кот в блокноте?

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

@GbaLog- · 01.01.2017, 22:03

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

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

Тут скорее не от ИДЕ зависит, а от компилятора, вы вот какой пользуете?
А вообще, в том же gcc такой проблемы не имеется.
Вот в приведенном ниже примере компилятор поначалу выдаёт варнинг на неиспользуемую переменную, но флагом -Wno-unused-variable мы его выключаем.

http://rextester.com/VJKF88743

@_Ivana · 01.01.2017, 22:09

Сообщение от GbaLog-

вы вот какой пользуете

Для баловства тот же рекстестер с ГСС, для локального баловства - Вижуал Студию 2010. Но на варнинги я забиваю (потому что в большинстве случаев в Студии они Майкрософт-специфичные), но с другой стороны я и функции без ретурна в одном из достижимых кейсов не пишу. Я же знаю, что нахожусь в языке для отстрела ног, поэтому вынужден тратить внимание еще и на это

ЗЫ а в джаве по-моему все-таки ИДЕЯ палки в колеса вставляет, а не компилятор. Хотя не исключаю возможности, что где-то среди ее 100500 настроек есть незаметный флажок "не вставлять палки в колеса", но по дефолту он отключен.

@GbaLog- · 01.01.2017, 22:21

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

ЗЫ а в джаве по-моему все-таки ИДЕЯ палки в колеса вставляет, а не компилятор.

Ну джава не компилируемый язык(не совсем так, но идея, думаю, понятна), поэтому в самой ИДЕЕ можно сделать какой-нибудь статический анализатор и, соответственно, начать вставлять палки в колёса.

@Catstail · 02.01.2017, 10:00

Thor, да, проверил работу в VC6.0. Действительно если закомментировать отладочную печать, то выдает верный минимум. Надо читать, как реализован выход из функции, которая должна возвращать некий тип, а оператор return отсутствует...

Проделал небольшой эксперимент с VC6.0. Пишем вот такой код:

C++
1
2
3
4
5
6
7
8
9
10
11
#include <iostream.h>
int f(int x)
{
    int y=x*x;
}
int main() {
    int j;
    cout << f(2) << endl;
    cin >> j;
    return 0;
}

И, естественно, налетаем на ошибку: "Функция f должна возвращать значение". Теперь меняем код:

C++
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream.h>
int f(int x)
{
    int y=x*x;
        if (y > 100) return y;
}
int main() {
    int j;
    cout << f(2) << endl;
    cin >> j;
    return 0;
}

Ошибка исчезает. Вывод = 4. Но, позвольте! При x=2, y=4 и return не должен выполниться! Смотрим, во что транслируется f(x). И что же видим? Ха-ха!

Assembler
1
2
3
4
00401072 cmp dword ptr [ebp-4],64h 
00401076 jle f+2B (0040107b)
00401078 mov eax,dword ptr [ebp-4] ;; занесение верного значения
0040107b pop edi                           ;; начало возврата

Получается, что в данном случае при возврате в регистре eax остается "старое значение" (т.е. код этот НЕВЕРЕН, а уровень контроля в C++ его, увы, пропускает).

@Catstail · 02.01.2017, 10:32

Кстати, теперь понятно, почему, закомментировав

C++
1
cout << "Return ???" << endl;

, мы получаем "верный" ответ. Просто eax не портится.

Новые блоги и статьи Все статьи Все блоги /
Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Символьное дифференцирование igorrr37 13.02.2026 / * Программа принимает математическое выражение в виде строки и выдаёт его производную в виде строки и вычисляет значение производной при заданном х Логарифм записывается как: (x-2)log(x^2+2) -. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@TheCalligrapher Вездепух 12937 / 6804 / 1821 Регистрация: 18.10.2014 Сообщений: 17,220
	31.12.2016, 10:02
	Эксперимент с return 2

@Thor 2 / 2 / 0 Регистрация: 12.12.2014 Сообщений: 87
	31.12.2016, 21:58 [ТС]
	igorrr37, спасибо за инфу! TheCalligrapher, почитал тред, помог немного разобраться. Catstail, у меня ваш код (первый который) даёт правильный ответ (-2), т.е. работает верно (компилятор VS2015). Fixer_84, спасибо. Вообще, свой код-то я исправил. У меня был чисто методологический вопрос по тому как работает C++ в условиях, когда возвращающая значение функция не достигает return. 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	01.01.2017, 21:44
	А варнинг-чекер в ИДЕ молчит по этому поводу? Меня вот в ИДЕЕ заколебало, что даже в целях отладки я не могу вначале длинной функции вставить ретурн тру потому что дескать все что после становится недостижимо и кот даже не компилируется. В плюсовых ИДЕ типа Студии нет такого уродства? Или его надо искать в продуктах от Джет Брайнс типа Клиона? Или вы пишете кот в блокноте? В любом случае, вам может помочь либо жесткий стайлгайд, либо статический котоанализатор, либо другой язык 0

Задача на рекурсию - почему вроде бы ошибочный код внутри работает правильно?

Решение