Too large hierarchy tree using Recursion , makes file searching to crash

Question

I've written a code for searching a specific file , where the user enters a starting path and a filename , and then the program prints its details if the file exists , or prints not found otherwise.

As I suspected , the using of recursion makes the code to crash when the hierarchy tree is too large ,I've tried with 400 directories and it failed ,so I guess that after something like 50 folders one inside to other ,the overhead of the recursion makes the code to crash .

Any suggestions how to fix that ? basically the code is okay for low level tree hierarchy , but I need to design it for healthy trees (500-600 folders one inside the other , and a file that is stored at the last folder) also , thanks

score 3 · Answer 1 · edited May 23 '17 at 12:12

3

The dirtiest way to go is to increase stack size.

The second is to replace char full_name[_POSIX_PATH_MAX + 1] with char *fullname=malloc((_POSIX_PATH_MAX + 1)*sizeof(char)) and don't forget to free() it after recursive call.

And possibly the best one is to scrap that code and use the mighty omnipresent find

edited May 23 '17 at 12:12

Community

1
1

answered Jun 17 '12 at 07:18

qdiesel

401
3
9

I can't use `find` , my task to write a code that simulates `find` :) – JAN Jun 17 '12 at 07:19
I've tried to do this `char *fullname=malloc((_POSIX_PATH_MAX + 1)*sizeof(char))` but it still the same . – JAN Jun 17 '12 at 07:27
Thanks for the suggestions , but I've tried both to increase to `16MB` and and also `char *fullname=malloc((_POSIX_PATH_MAX + 1)*sizeof(char))` , but it still won't work with 100 or 500 folders. – JAN Jun 17 '12 at 07:39
Sorry,but none of these suggestions worked. Nonetheless thank you. – JAN Jun 17 '12 at 08:00
1

Tangentially, the `sizeof(char)` isn't strictly necessary, since the C standard states that `sizeof(char) == 1` always. – huon Jun 17 '12 at 10:28

huon · Accepted Answer · 2012-06-17T09:37:13.403

You can remove the recursion (i.e. convert to an iterative solution) by storing the directories as you see them (instead of processing them immediately) and then coming back around to them on some later iteration. However, you might not get precisely identical output (things may be ordered differently).

The way this method works is by having a list of directories to process, and you go through this list (adding any child directories to it as you go).

In 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

A stack can be implemented as a singly linked list fairly easily. Note that special handling is required if path is not a directory, and that this isn't recursive.

Too large hierarchy tree using Recursion , makes file searching to crash

2 Answers2