JS - Recursive to iterative

Bardzo proste ćwiczenie. Bierzemy dwie całkiem proste funkcje rekurencyjne z poprzedniej lekcji i zamieniamy na podejście iteracyjne. Do dzieła.

Oto funkcja sprawdzająca palindrom:

function isPalindrome(str){

    if(str.length === 1) return true;

    if(str.length === 2) return str[0] === str[1];

    if(str[0] === str.slice(-1)) return isPalindrome(str.slice(1,-1))

    return false;
}

Oto jej iteracyjny odpowiednik metodą dwóch wskaźników:

function isPalindrome(s) {
    
    let start = 0;
    let end = s.length - 1;

    while(start < end) {
        if (s[start] !== s[end]) {
            return false;    
        } else {
            start++;
            end--;
        }
    }
    
    return true;
}

Jest start i finisz (indeksy). W pętli sprawdzamy czy są równe i jeden inkrementujemy, drugi dekrementujemy.

A teraz pokażę, jak tego nie robić (w języku Python, przykład z sieci):

def isPalindrome(word):
  midPoint = len(word)//2
  palindrome = True
  for i in range(0,midPoint):
    left = word[i]
    right = word[len(word)-i-1]
    if left!=right:
      palindrome=False
      break
  return palindrome

Bawimy się w jakiś mid-pointy jak w binary search, pętla for zupełnie nieczytelna, podobnie jak logika, tworzymy zmienne left i right do których przypisujemy wartości pod indeksem i następnie nazwy tych zmiennych porównujemy, nie wyrywamy się z pętli returnem tylko breakiem, choć wcale nie musimy, bo potem i tak nic dalej nie robimy.

Takich kodów nie lubię. Jest to ewidentne podejście muszę napisać palindrom w wersji iteracyjnej, choć pojęcia nie mam, jak się do tego zabrać. Byle działało. No to akurat działa, trzeba przyznać.

Zobaczmy na nasz przykład i dlaczego „kajak” działa. Zastanówmy się nad jednym – czym będą start i end w każdym obrocie pętli.

Pseudokod:

var word = "kajak"

var start = 0
var end = 5 - 1

warunek =  while(start < end)

po każdej pętli = start++, end--

obrót 1:

word[start] = "k" (0)
word[end] = "k" (4)

obrót 2:

word[start] = "a" (1)
word[end] = "a" (3)

obrót 3:

word[start] = "j" (2)
word[end] = "j" (2)

obrót 4:
nie istnieje, bo start (3) nie jest mniejszy od end (1)...

Dobra, a teraz someRecursive:

function someRecursive(array, callback) {

    if (array.length === 0) return false;

    if (callback(array[0])) return true;

    return someRecursive(array.slice(1),callback);
}

Jak to ugryźć iteracyjnie? Cóż…

function someIterative(arr, callback){

    for(var i = 0; i < arr.length; i++){
        if(callback(arr[i]))
            return true;
    }

    return false;
}

console.log(someIterative([1,2,3], (n) => n > 10));
//false
console.log(someIterative([10,20,30], (n) => n > 10));
//true

Proste, choć wywoływanie funkcji w bloku if zazwyczaj jest bardzo złą praktyką, choć tutaj może nie aż tak.

Ogólnie jest to zła praktyka, gdy wielokrotnie wołamy funkcję zamiast raz ją wywołać, do zmiennej przypisać i potem ifami porównywać w bardziej imperatywnym programowaniu.

JS – Recursive to iterative