Using recursion to create nested folder structure - with example of integers

Question

I am writing my PhD in linguistics and I wish to use a recursive programming method as a parallel to visualise a process. Recursion is important here, because this concept relies on the comparison of the concept recursion in programming and in linguistics. Let us a suppose that we wish to write a method that creates folders and subfolders (and subfolders...) within them. For the sake of simplicity we could handle the folder names as integers and there is no need to create folders themselves. I wish to implement this method with the following rules

Every top folder name should be randomly generated as an integer between 1 and 999 (could be more, but it threw me a Stack Overflow error with larger numbers, but then my solution was flawed)
Every subfolder inherits its name from the top folder, to simplify the process, every top folder has three subfolders and the names of these are generated the following way:first subfolder has the 2x the value of the top folder, second 3x and third 4x
This rules applies to the subfolders' subfolders as well until they reach 999
The program should count how many of these folders / numbers were created in the process

I tried quite many times and mainly every time some steps were missing or not working: Version 1:

numbers here is a static variable of the class (list), but I would be happy if there would be a solution where I wouldn't need this.

public static void countFolders(int max, int currentAmount, int originalAmount, int index) {
    int[] evenMultipliers = new int[]{2, 3, 4};
    if (originalAmount >= max){
        return;
    }
    if (currentAmount < max){
      numbers.add(currentAmount);
    }
    if (index >= evenMultipliers.length) {
      countFolders(max, originalAmount, originalAmount, 0);
    }else if (evenMultipliers[index] * currentAmount > max) {
      countFolders(max, originalAmount + 1, originalAmount + 1, 0);
    }else{
      countFolders(max, currentAmount * evenMultipliers[index], originalAmount, index + 1);
    }
  }

I do think that somewhere along the way I miss some important concepts of recursion. I am not 100% sure how to keep track of the folder names of the previous level, but I tried this so many times with different approach (f.e. recursion within a foreach loop) and still no clue how to finish this properly.

-- EDITED --

The input values are 4 as max and 1-1 as originalAmount and actualAmount

Debug

This sample input produces the following output: [1, 2, 2, 3]

But then it should be [1, 2, 2, 3, 3] (may be not in this order) Because on the top level there could be three folder names / integers 1, 2, 3 and only the top level folder / number '1' can produce subfolders when multiplied by 2x and 3x I try to make it more clear, I will introduce A, B and C to show on which level the current folder is, B is subfolder of A level and C of B level So in case the max is 4

1(A) -> 2(B) and 3(B)

2(A)

3(A)

In case the max is 5 then the output is [1, 2, 2, 4, 3, 4]

But it should be [1, 2, 3, 4, 4, 2, 4, 3, 4]

1(A) -> 2(B), 3(B) 4(B) and within 2(B) there is 4(C)

2(A) -> 4(B)

3(A)

4(A)

UGLY SOLUTION WITH LOOPS I only multiplied the folder values here instead of 2, 3, 4 only with 2 and 3

    public static void countFoldersNew(int max) {
    int actualAmount;
    for (int i = 1; i < max; i++) {
      actualAmount = i;
      numbers.add(actualAmount);
      int temp = actualAmount;

      while (actualAmount * 2 < max) {
        actualAmount = actualAmount * 2;
        numbers.add(actualAmount);
        actualAmount = temp;
        while (actualAmount * 3 < max){
          actualAmount = actualAmount * 3;
          numbers.add(actualAmount);
          if (actualAmount * 2 < max){
            actualAmount = actualAmount * 2;
            numbers.add(actualAmount);
            actualAmount = actualAmount / 2;
            if (actualAmount * 3 < max){
              actualAmount = actualAmount * 3;
              numbers.add(actualAmount);
            }
          }

        }
        actualAmount = temp * 2;
        temp = temp *2;
      }
    }
  }

EDITED: A mind map how the structure should look when the input max is 10

Thank you for your help in advance!

user_1552534 · Answer

This is not recursive but I believe it works based on my understanding of the algorithm.

folders from 1 thru max-1 are iterated
add first folder to list
now process subfolders of that folder
add those to list
repeat

Note that in some cases, the order may be different than expected. I recommend you verify based on additional cases.

for (int max = 3; max < 10; max++) {
    List nums = new ArrayList<>();
    for (int folder = 1; folder < max; folder++) {
        nums.add(folder); // add the first folder
        nums.addAll(add(folder, max)); // add subfolders of first folder
    }
    System.out.printf("max = %2d : %s%n", max, nums);
}

prints

max =  3 : [1, 2, 2]
max =  4 : [1, 2, 3, 2, 3]
max =  5 : [1, 2, 3, 4, 4, 2, 4, 3, 4]
max =  6 : [1, 2, 3, 4, 4, 2, 4, 3, 4, 5]
max =  7 : [1, 2, 3, 4, 4, 6, 2, 4, 6, 3, 6, 4, 5, 6]
max =  8 : [1, 2, 3, 4, 4, 6, 2, 4, 6, 3, 6, 4, 5, 6, 7]
max =  9 : [1, 2, 3, 4, 4, 6, 8, 6, 2, 4, 6, 8, 8, 3, 6, 4, 8, 5, 6, 7, 8]

The method works as follows

keep adding folders to list until folder exceeds size
then process that list starting with next folder in list
eventually the folder will be too large (and so will others) so return the current list.

    
static int[] multipliers = { 2, 3, 4};
public static List add(int currentFolder, int max) {
    List folder = new ArrayList<>();
    int folderIdx = 0;
    while(true) {
        for (int mult : multipliers) {
            int val = currentFolder * mult;
            if (val >= max) {
                // since folders are in order, if 
                // this one is too large, so will subsequent ones
                return folder;
            }
            folder.add(val);
        }
        currentFolder = folder.get(folderIdx++);
    } 
}

Using recursion to create nested folder structure - with example of integers

1 Answers