Рекурсивный ввод-вывод последовательности без использования массивов и списоков?

Question

[limberg]

Задача: организовать ввод-вывод последовательности n целых чисел, с применением рекурсии. Числа должны выводится с порядковыми номерами и в том же порядке, в каком производился их ввод. Использование массивов и списков не разрешается. Вывод должен происходить после окончания ввода.

Буду благодарен за подсказку, как можно подкорректировать эту функцию так, чтобы вывод был в прямом порядке, а не в обратном:

void RecursiveInput( int n, int index = 1 )
{
    if ( index <= n )
    {
        int value;
        cin >> value;

        RecursiveInput( n, index + 1 );

        cout << "Номер " << index << ": " << value << endl;
    }
}

Comments

[Dmitrii]

А в чем мотивация не использовать массивы?
Вы же по сути и так будете использовать память на стеке

[Adamos]

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

[limberg]

Dmitrii, мотивации никакой. Это просто учебные задачки, не я условие придумывал)

[limberg]

Adamos, понял, спасибо за идею со строками!

[Сергей Соловьев]

Adamos, но по идее - это тот же самый список и есть

[Adamos]

limberg, идея так себе, честно говоря. Массив тратит меньше памяти, например.

[Alexandroppolus]

может, здесь нужен грязный хак с адресной арифметикой? Уже на втором вызове функции можно будет узнать разницу адресов на стеке для value, и потом, с самого глубокого вызова, обращаться к предыдущим. Такое может прокатить в современных плюсах?

[Adamos]

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

std::string res = "Номер " + std::to_string(index) + ": " + std::endl + RecursiveInput( n, index + 1 );

[Alexandroppolus]

ещё вариант: понятное дело, что мы здесь используем O(N) памяти на стеке. То есть так или иначе неявно будет какой-то массив/список, как верно заметил Dmitrii

что если на каждом вызове создавать на стеке свою переменную, которая будет узлом списка? прокидывать по рекурсии указатели на первый и последний узел. К последнему подвешивать очередной узел, а как ввод закончится (на самом глубоком уровне), запустить рекурсию с выводом значений с первого узла. Да, вроде как список, но формальности соблюдены

[mayton2019]

Ох и душный преподаватель. Ну тут как-бы вводить массив понятно как.
Но если допустим числа были 1,2,3,4,5 то при обратном ходе рекурсии из стека
мы их будем печатать так

5,4,3,2,1

Если бы в системе было 2 стека тогда можно былоб както перехитрить порядок вывода.

Да без какого-то грязного трюка с адресами - даже неясно что делать. Хачить стекфрейм?

[Rsa97]

Массивы и списки говорите нельзя? А как насчёт очередей?
Дек - deque - double-ended queue - очередь с двумя концами.
Полученное число пишем в конец дека, перед возвращением выводим число из головы дека.
https://metanit.com/cpp/tutorial/7.8.php

[mayton2019]

Rsa97, не прокатит я думаю. Любая сложная коллекция не проходит через условия задачи.

Можно было-бы передавать строку через стек. Типа std::string и переворачивать ее на ходу.
Но это с друой стороны тоже коллекция символов.

[Odissey Nemo]

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

Answer 1

[Alexandroppolus]

в общем, закину свой вариант, который изложил в комментах. Просто оставлю это здесь.

Вышло даже немного проще, достаточно передавать только одну ссылку.
Нет массивов, и нет списков, аллоцированных в куче. Только одиночные стековые переменные.

кодъ на плюсахъ

#include <iostream>

struct Node {
    int value;
    Node *next;
};

void RecursiveOutput( Node* item )
{
    if ( item != 0 )
    {
        RecursiveOutput(item->next);
        std::cout << item->value << std::endl;
    }
}

void RecursiveInput( int n, int index = 1, Node* item = 0 )
{
    if ( index <= n )
    {
        Node data;
        std::cin >> data.value;
        data.next = item;

        RecursiveInput( n, index + 1, &data );
    } else {
        std::cout << "RecursiveOutput" << std::endl;
        RecursiveOutput(item);
    }
}

int DEPTH = 3;

int main()
{
    std::cout << "input values: "  << std::endl;
    
    RecursiveInput(DEPTH);
    
    std::cout << "end"  << std::endl;

    return 0;
}