Слишком большое дерево иерархии, использующее Recursion, приводит к сбою файла

Question

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

Как я и предполагал, использование рекурсии приводит к сбою кода, когда иерархическое дерево слишком велико, я пробовал 400 каталогов, и это не удалось, поэтому я думаю, что после чего-то вродепапок один внутри другого, накладные расходы рекурсии приводят к сбою кода.

Любые предложения, как исправить это? в основном код подходит для иерархии дерева низкого уровня, но мне нужно создать его для здоровых деревьев (500-600 папок один внутри другого и файл, который хранится в последней папке), также, спасибо

Answer 1

Вы можете удалить рекурсию (то есть преобразовать в итерационном решении) путем сохранения каталогов, как вы видите их (вместо их обработки сразу же), а затем возвращаться к ним на более поздней итерации. Однако вы не можете получить точно идентичный результат (вещи могут быть заказаны по-разному).

Способ, которым работает этот метод - это иметь список каталогов для обработки, и вы просматриваете этот список (добавляя к нему все дочерние каталоги, когда вы идете).

В psuedocode/Python:

def print_dirs(path, recursive, filename): 
    dir_stack = empty stack 
    dir_stack.push(path) 

    while dir_stack is not empty: 
     dir = dir_stack.pop() # returns the head element (and removes it) 

     for file in children(dir): 

     # ...do stuff with names... 

     if recursive and file is a directory: 
      dir_stack.push(file) # process the directory later 

Стек может быть реализован в виде односвязный список довольно легко. Обратите внимание, что специальная обработка необходима, если path не является каталогом и что этот не является рекурсивным.

Answer 2

Самый грязный путь - increase stack size.

Второе должно заменить char full_name[_POSIX_PATH_MAX + 1]char *fullname=malloc((_POSIX_PATH_MAX + 1)*sizeof(char)) и не забудьте указать free() после рекурсивного вызова.

И, возможно, лучшим вариантом является ломом этот код и использовать могучий вездесущий find