Question: I have an app that creates custom files that are shown in a gallery. They are not images or other standard media files. Because the files are large, I ask users for access to a folder in which the files will be stored.

So far so good.

Reading those files or file info via DocumentFile is so much slower than via File. Operations like

```
DocumentsContract.findDocumentPath()
documentFile.isFile()
documentFile.getName()

```

take up to 15ms each, which accumulates to a large time when reading a large number of files.

What's the best way to handle this? Is there another way to do this? I don't want the files to be in internal app memory or users might lose their work when they uninstall the app.

Thanks in advance! This is stressing me out a lot.

Answer: 
If you want to keep using recursion you have to use [memoization](https://en.wikipedia.org/wiki/Memoization), or caching. The idea is, when calculating a result, store it for later.

I suggest having an array of sufficient size, say 100 entries (seeing that the numbers grow just a bit slower than 2n, this should be enough to represent any 64-bit number). Initialize it to 0:

```
int test(int n)
{
    static int cache[100] = {0};
    ...
}

```

After calculating a result, store it in the correct index:

```
int test(int n)
{
    ...
    result = ...
    cache[n] = result;
    return result;
}

```

But before applying the formula, check if the cache contains the result:

```
int test(int n)
{
    ...
    if (cache[n] != 0)
        result = cache[n];
    ...
}

```
As you probably figured out, the reason your recursive solution is slow is because you recompute answers that had already been computed before.

This is why memoization works, and it allows you to maintain your top down algorithmic translation of the sequence as mathematically defined.

The disadvantage of complete memoization is that the table can be arbitrarily large. If O(1) time (at the cost of O(n) space) is not required, and O(n) time is sufficient, it is possible to perform the computation with O(1) space, and this has been illustrated in other answers as well.

All that is really required is that for any recursive calculation of `test(n-1)`, the values for `test(n-2)` and `test(n-3)` should also be available. If you do not like creating a helper recursive function to track this information, then the below is an alternative that uses a single recursive function.

```
int test(int n) {

    typedef struct { int x[2]; } state;
    static const state init = { 0, 1 };
    static state last;

    if (n > 0) {
        last = init;
        return test(-n);
    }

    n = -n;
    if (n < 3) return n;

    // After the below call, last has test(n-2) and test(n-3)
    int x = test(-(n-1));
    int result = x + last.x[0] + last.x[1];
    last.x[0] = last.x[1];
    last.x[1] = x;
    return result;
}

```

[Try it online!](https://tio.run/##dVHLboMwELzzFSOqSlgBAsmhByeR@h1RDtSYYomayF5UqohvT21MHj3UF693ZmfWuyL7FOL6orTohlpiZ6lWfd4eoqvSBJKWEh9ohksUwR36OctaNrBkBkG4wMPjcXPimFyyIslnng@VgOi1pZB3TEXYu5IiRYnpDy8wusoSDz6qQaJxQOGdsRyPOwUvxO9JI2kwOvSaaRaAKahox840f1LcYctuJXrxWq/x3pA0oFbiQ3b9N0TVdWnwaysbxHW2Yah0fXttWdD1A3A@oQGXL9nShEeMtEPnmx6xmvXy8VicHnF5CtwHtP8HKj00htTygSDOo2ne1lelNJLbvJreYN6dcmUFd9cObxyrlXqe6Nk4SpPE@Wsdp8u@2X2GM2Mgm8Qx8y6/ "C (gcc) – Try It Online")