Pentabonacci function

We are going to use Memoization to implement a solution. This will require creating a structure to store the pre-calculated data and thus optimize the response time.

RECURSION: "to understand recursion you must first understand recursion" .

One of the characteristics of recursion (or recursion) is that it allows you to write clean code and also allows you to execute complex tasks that would otherwise become quite tedious.

However, recursion can become very costly in resources if the problem grows in complexity and steps are not taken to optimize the process.

JavaScript (ECMAScript 6) supports queue optimization for recursion, however not all (almost any) JS engines in different browsers (including NodeJS) support this feature.

Therefore, we should leave the use of optimized recursion to languages ​​that do support it. (At least for now 22-10-2019).

You can read a bit more about ES6 and queue optimization for recursion, in this post.

MEMOIZATION, or was it memorization... I don't remember

The memoization technique (not to be confused with memorization ) is an optimization technique used to speed up processes when you have heavy function calls . There are several areas in which it is used, not only in recursion.

To solve the problem we will use this technique since it seems to be the right one, although there could be another even more efficient one.

What we will do is create a cache of results stored in a list. This way we don't need to use recursion, and the process becomes very intuitive.

The problem definition asks to calculate a series called Penta-Fibonacci, that is, applying the Fibonacci series but up to n-5.

Recall that the value of each element of the Fibonacci series is calculated as follows:

n = (n -1) + (n - 2);

therefore our Penta-Fibonacci series is defined as:

n =  (n-1) + (n -2) + ... + (n -5);

The fibonacci series starts with the values ​​0 and 1 and the rest is calculated from these two numbers. Being:

f(0) = 0;
f(1) = 1;
f(2) = 1;
f(3) = 2;
f(4) = 4;
...

With this we already have the values ​​that will serve as the basis for calculating the rest of our Penta-Fibonacci series.

We need to work with a row or queue , to always store the last 5 elements of the series to calculate the next one. Javascript does not have an object of type row, but instead has an object of type Array, which has two methods that will help us work as if it were a row. These are push(), which allows us to add elements to the end of the array, and shift()which allows us to remove the first element from the array and reduces the size of the array.

the code please

We are going to implement this solution without using recursion, we will simply use a loop for.

const pentaFiboOdd = function(n) {
  // Función que retorna los elementos impares de la serie Penta Fibonacci

  // Creamos el caché inicial de valores
  let cachedValues = [0, 1, 1, 2, 4];

  // Casos base:
  if(n < 0) return 0;
  if(n < 5) return cachedValues[n];

  // Creamos el array de resultados (sólo elementos impares)
  let result = cachedValues.filter(value => value % 2 !== 0);

  // función reductora para calcular la suma de los elementos en caché.
  const reducer = (acc, curr) => acc + curr;

  // iteramos desde i = 5 hasta n y calculamos los valores de cada elemento
  // que tiene la serie, basados en la suma de los 5 anteriores
  for(let i = 5; i <= n; i++){
    let elemento = cachedValues.reduce(reducer);
    // sólo si el elemento es impar lo añadimos al resultado
    if(elemento % 2 !== 0) {
      result.push(elemento);
    }
    // aunque el elemento no sea parte del resultado, debemos actualizar la caché
    cachedValues.push(elemento);
    cachedValues.shift();
  }
  return result;
}

let serie = pentaFiboOdd(50);
console.log('El resultado de pentaFiboOdd(50) es:');
console.log(serie);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Let's take a good look at what's going on here.

1. The base case is already covered and explained.
2. We have created a list called cachedValues, it contains the first five elements of our series.
3. Each new element in the series is calculated by adding the values ​​of the 5 elements stored in our cache.
4. If the result is odd, it is stored in the arrayresult.
5. The first element in the cache is purged and the new calculated element is added to the cache. In this way we guarantee that we will always have the last 5 elements with which the next one is calculated.

With this you have applied Memoization, in a non-recursive algorithm.

EDITION

Since the CodeWars exercise (kata) that this question comes from asks for the number of odds that exist in the string, then other logic could be used to find the result.

Thanks to the contribution of @gbianchi , the idea proposed by him is to use a deterministic method to know if given a value nthe result of f(n)will be even or odd.

If we analyze the first 17 elements of the series we have the following.

f(0) = 0     // par
f(1) = 1     // impar
f(2) = 1     // impar
f(3) = 2     // par
f(4) = 4     // par
f(5) = 8     // par
f(6) = 16    // par
f(7) = 31    // impar
f(8) = 61    // impar
f(9) = 120   // par
f(10) = 236  // par
f(11) = 464  // par
f(12) = 912  // par
f(13) = 1793 // impar
f(14) = 3525 // impar
f(16) = 6930 // par
...

We see a pattern that repeats every 6 elements starting with n=1. Therefore, the way to count these odd elements is given by calculating the times that 6 fits in nand the rest of dividing n / 6.

For every time 6 fits entirely in n, 2 odds must be added to the count.

And if the division of n/6 is inexact, an odd must be added to the count according to the following:

if n%6 > 22 odds are added, otherwise exactly odds are added n%6.

Finally, we must take into account that the value 1 is repeated and therefore we must eliminate it from the account.

Let's see the solution:

const countPentaFiboOdd = function(n) {
  
  let count = Math.floor(n/6) * 2;
  const rest = n%6;
  if(rest < 3) {
    count += rest;
  } else {
    count += 2;
  }
  // dado que el 1 se repite cuando n  > 1, lo sacamos de la ecuación
  if (n > 1) count--;
  return count;
}

console.log(countPentaFiboOdd(1000));

I hope this helps you solve the problem.

To calculate the value for n = 7 you have to calculate the value of the previous 5, so you make 5 recursive calls, but each of these calls will make another 5, so for the value of n=30 you will have an incredible amount of recursive calls that will kill the stack. Many of these calls will have been made before, so the ideal would be to reuse them.

A simple solution is to use a structure that saves the previous results to prevent the recursion from getting out of hand:

Once you calculate PentaFib of N, you save it. As you will have had to calculate PentaFb(N-1), PentaFb(N-2), ... PentaFb(N-5), you will have all those values ​​already saved, so calculating PentaFib(N+1) is accessing the 5 previously saved values ​​and add them. This is what is called memorization

Since we only need to know how many odd elements there are, we can further simplify the calculation:

We will save 0 if the number is even and 1 if it is odd. Thus we have the initial values:

[0, 1, 1, 2, 4]

become

[0, 1, 1, 0, 0]

And every time we calculate the next value we will have the following:

[0, 1, 1, 2, 4] -> f(5) = 8

And with our new f prime function :

[0, 1, 1, 0, 0] -> f'(5) = (0 + 1 + 1 + 0 + 0) mod 2 = 0

So in the end we will only have to count the number of 1 in the array:

const pentafib = {
  results: [0, 1, 1, 0, 0], //resultados para n < 5
  calcPentaFib : function calcPentaFib(n) {
    
    if (this.results.length > n) { // está ya calculado
      return this.results[n];
      
    } else {
      const value = (this.calcPentaFib(n - 1) +
          this.calcPentaFib(n - 2) +
          this.calcPentaFib(n - 3) +
          this.calcPentaFib(n - 4) +
          this.calcPentaFib(n - 5)) % 2;
          
      //se guarda el resultado para posteriores peticiones
      this.results[n] = value;
      return value;
    }
  }
}

function countOddPentaFib(n) {
    let arr = []
    for (let i = 0; i <= n; i++) {
        arr.push(pentafib.calcPentaFib(i))
    }
    arr = arr.filter(n => n === 1); //nos quedamos con los 1
    //devolvemos el número de 1 encontrados
    return arr.length - 1; // restamos uno porque f(1) y f(2) son 1, con lo que tenemos un valor repetido
}

console.log(countOddPentaFib(30));
console.log(countOddPentaFib(100));

Mauricio's solution is totally correct.

Based on the data determination and the recurring pattern, the following can be done:

The code is in c#, but it is translatable to which language...

Mauricio used a mathematical function, even more beautiful. However, using only "trivial" code can be solved as well.

public static long CountOddPentaFib(long n) {
    int valor = 1;
    int inferior = 8;
    int suma = 1;
    if (n < inferior)
    {
        return valor;
    }
    while (inferior <= n+1)
    {
        valor++;
        inferior += suma;
        if (suma == 1)
        {
            suma = 5;
        }
        else
        {
            suma = 1;
        }
    }
    return valor;
}

There is an issue if the input value is even or odd, and that is why the while takes one more value than there is to count. I couldn't find where the problem is in those edges, but I think Mauricio's solution applies.