Оптимизировать вложенные рекурсии - PullRequest
Новая
       9

Оптимизировать вложенные рекурсии

0 голосов
/ 04 октября 2019

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

Моя реализация выполняется по следующей схеме: 

void compute(Program program) {
    // Evaluate operations by calling specifics function...
    for (int i = 0; i < program.op_nbr; i++)
        eval_operation(&program.operations[i]);
}

void eval_operation(Operation op) {
    // Evaluate the operation
    switch (op->kind) {
        ...
        case Something: return eval_thing(&op->thing);
        ...
    }
}

void eval_thing(Thing thing) {
    for (int i = 0; i < thing.op_nbr; i++)
        eval_operation(&thing.operations[i]);
}

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

  • compute цикл и вызов eval_operation для каждой операции;
  • eval_operation вычисление данной операции, если это операция типа thing, то она вызывает eval_thing;
  • eval_thing вызов eval_operation для каждой операции, содержащейся в «вещи».

Я надеюсь, вы понимаете концепцию и предвидите, что может произойти: eval_thing может вызывать себя несколько раз(в зависимости от ввода), поэтому я получаю переполнение стека, если это происходит слишком много раз;логика, я знаю пределы рекурсии в C, но я знаю, что есть и оптимизации, такие как хвостовая оптимизация, но я не думаю, что она применима к моей проблеме;поэтому мой вопрос заключается в том, как добиться большей рекурсии или даже бесконечности, если это возможно (я могу сделать только 1 КБ в качестве примера).

Может ли быть факт, что эти функции void и что передача по параметру выполненас помощью указателей будет легче решить эту проблему?

PS: Под «вложенными рекурсиями» я подразумеваю тот факт, что рекурсия выполняется не непосредственно внутри самой функции, а посредством вызова в соответствии с циклом for, обычно: 

void foo() {
    return bar();
}

void bar() {
    return foo();
}
...