Найти минимальный элемент массива рекурсивно

@Sashokk84 · Регистрация: 02.11.2012

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

Всем привет!!!
Нужно найти минимальный элемент массива при помощи рекурсии. Просидел вчера весь день и никак не могу воткнуть как написать этот код, при том, что при помощи итерации написал решение за 20 мин.
Могу решить рекурсивно самые простые задачи такие как поиск факториала и т.п., но когда что-то сложнее, то сразу ступор.
Если можно, то подскажите самый простой способ, т.к. главная моя задача сейчас это понять рекурсию.
Вот собственно код:

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
using std::cout;
using std::cin;
using std::endl;
 
 
 
int main()
{
    setlocale( LC_ALL, "rus" );
    void pechatMassiva( int[], int const );
    int minMassivaIter( int mass[], int const arraySize );
    //int minMassivaRekurs( int mass[], int const arraySize );
 
    int const arraySize = 10;
    int mass[ arraySize ] = { 12, 34, 6, 45, 18, 37, 11, 83, 92, 33 };
   
    cout << "Массив: ";
    pechatMassiva( mass, arraySize );
    cout << endl;
    cout << "Минимальное число массива (итерация): " << minMassivaIter( mass, arraySize ) << "\n\n";
 
    cout << "Массив: ";
    pechatMassiva( mass, arraySize );
    cout << endl;
    cout << "Минимальное число массива (рекурсия): " /*<< minMassivaRekurs( mass[], arraySize )*/ << "\n\n";
 
}
 
 
void pechatMassiva( int mass[], int const arraySize )
{
    for( int i = 0; i < arraySize; i++ )
        cout << mass[ i ] << " ";
    
}
 
 
int minMassivaIter( int mass[], int const arraySize )
{
    int min = mass[ arraySize - 1 ];//min = последний элемент массива
 
    for( int i = 0; i < arraySize; i++ )
    {
        if( mass[ i ] < min )
            min = mass[ i ];
    }
 
    return min;
}
 
//int minMassivaRekurs( int mass[], int const arraySize )
//{
//  Что сюда писать???
 
//}

@OhMyGodSoLong · 03.11.2012, 13:35

Хотите научу читерской штуке «Как превратить цикл в рекурсию за 5 минут»?

Вот у вас есть код

C++
1
2
3
4
5
6
7
8
9
10
int minMassiva( int mass[], int const arraySize )
{
    int min = mass[ arraySize - 1 ];
    for( int i = 0; i < arraySize; i++ )
    {
        if( mass[ i ] < min )
            min = mass[ i ];
    }
    return min;
}

Рекурсия — это повторное выполнение собственного тела. Цикл — это тоже повторное выполнение собственного тела. Цикл зависит от какой-то переменной-счётчика и ещё этого min. Рекурсивная функция зависит от своих параметров. Значит, шаг первый: вынести все локальные переменные в параметры, теперь они инициализируются там:

C++
1
2
3
4
5
6
7
8
9
int minMassiva( int mass[], int const arraySize, int min, int i )
{
    for( i; i < arraySize; i++ )
    {
        if( mass[ i ] < min )
            min = mass[ i ];
    }
    return min;
}

Теперь смотрим, как изменяются эти переменные в одной итерации цикла. i увеличивается на единичку, min становится равной mass[i], если mass[i] < min. Остальные не меняются. Вот то же самое нам надо повторить в теле рекурсивной функции:

C++
1
2
3
4
5
6
7
8
int minMassiva( int mass[], int const arraySize, int min, int i )
{
    if( mass[ i ] < min )
        min = mass[ i ];
    i++;
    minMassiva( mass, arraySize, min, i );
    return min;
}

Вот только с возвратом у нас всё не так круто. Цикл продолжается, пока i < arraySize, значит так должна вести себя и рекурсия. Когда цикл закончился, он возвращает min. Если он не закончился, то он, очевидно, возвращает то, что навычисляет его следующая итерация.

C++
1
2
3
4
5
6
7
8
9
10
11
12
int minMassiva( int mass[], int const arraySize, int min, int i )
{
    if( i < arraySize)
    {
        if( mass[ i ] < min )
            min = mass[ i ];
        i++;
        return minMassiva( mass, arraySize, min, i );
    }
    else
        return min;
}

Осталось только задать начальные значения и запустить цикл:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int minMassiva_rec( int mass[], int const arraySize, int min, int i )
{
    if( i < arraySize)
    {
        if( mass[ i ] < min )
            min = mass[ i ];
        i++;
        return minMassiva( mass, arraySize, min, i );
    }
    else
        return min;
}
 
int minMassivaRec( int mass[], int const arraySize )
{
    return minMassiva_rec( mass, arraySize, mass[ arraySize - 1], 0 );
}

Добавлено через 14 минут
Но это, как видите, тот же итерационный вариант, только записанный по-другому. Можно, конечно, выкинуть пару локальных переменных, заменив их неявным временными. Минимум массива — это наименьшее число среди первого элемента массива и минимума всего остального массива. Вот так и запишем:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// минимум двух чисел
inline
int min(int a, int b)
{
    return (a < b) ? a : b;
}
 
int minArray(int *beginArray, int *endArray)
// минимум массива, ограниченного [beginArray, endArray] это
{
    // если массив состоит из одного элемента, то это этот элемент
    if (beginArray == endArray) {
        return *beginArray;
    }
    // иначе это минимум среди первого элемента и минимума всего остального массива
    else {
        return min(*beginArray, minArray(beginArray + 1, endArray));
    }
}
 
// How to use
int array[5] = { 3, 4, 1, 5, 2 };
std::cout << minArray(&array[0], &array[4]);

По сути, правда, всё равно одно и то же. Переменная min неявно запоминается как аргумент функции min(), а i++ заменился на указатель_на_начало_массива++.

@salam · 03.11.2012, 13:46

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector <int> v;
 
    int fmin(int x)
    {
        if(x > 0)
            return min(v[x], fmin(--x));
        else
            if(x == 0)
                return v[x];
    }
 
int main()
{
    int n;
    cin >> n;
    v.resize(n);
    for(int i=0; i < n; i++)
        cin >> v[i];
    cout << fmin(n) << endl;
    system("pause");
    return 0;
}

@igorrr37 · 03.11.2012, 22:37

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <algorithm>
 
template<typename T>
T MinElement(T const* p, size_t const size)
{
    return (1 == size ? *p : std::min(MinElement(p, size / 2), MinElement(p + size / 2, size - size / 2)));
}
 
int main ()
{
    double arr[] = {1.1, -3.3, -3.31, 0.01};
    std::cout << MinElement(arr, std::end(arr) - std::begin(arr)) << std::endl;
    return 0;
}

@Sashokk84 · 04.11.2012, 12:27 **[ТС]**

Всем спасибо! Буду вникать...

@Sashokk84 · 06.11.2012, 16:34 **[ТС]**

Отдельное спасибо ~OhMyGodSoLong~, очень познавательно, решил уже несколько более сложных задач таким методом...

Новые блоги и статьи Все статьи Все блоги /
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Рецензия / Мнение Это мой обзор планшета X220 с точки зрения школьника. Недавно я решила попытаться уменьшить свой. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .

@Sashokk84 1 / 1 / 0 Регистрация: 02.11.2012 Сообщений: 7
	04.11.2012, 12:27 [ТС]
	Всем спасибо! Буду вникать... 0

@Sashokk84 1 / 1 / 0 Регистрация: 02.11.2012 Сообщений: 7
	06.11.2012, 16:34 [ТС]
	Отдельное спасибо ~OhMyGodSoLong~, очень познавательно, решил уже несколько более сложных задач таким методом... 0

Найти минимальный элемент массива рекурсивно

Решение