Skip to content

Instantly share code, notes, and snippets.

@zgover
Last active August 15, 2021 05:55
Show Gist options
  • Save zgover/145a1fcc14b7efbc49d94c2a10df8d23 to your computer and use it in GitHub Desktop.
Save zgover/145a1fcc14b7efbc49d94c2a10df8d23 to your computer and use it in GitHub Desktop.
[Common Design Patterns] Simple, common and quick algorithms #algorithm #typescript #javascript #dart #sequence #patterns #effecient #math #facorial

lang: TypeScript

/**
 * Recursion simple
 */
const fibonacciRecursion = (n: number, fibRecusor?: typeof fibonacciRecursion): number => {
  const recurse = fibRecusor ?? fibonacciRecursion
  return (n < 2) ? n : (recurse.call(null, n - 1) + recurse.call(null, n - 2))
}
console.log('fibonacciRecursion', `${fibonacciRecursion(20)}`) // [LOG]: "fibonacciRecursion",  "6765" 

/**
 * Recursion with Tail End Optimizing Memoization
 */
const fibonacciRecursionMemoized = (function() { 
  const memo: number[] = []
  return function memoizedFn(n: number): number {
    if (Object.prototype.hasOwnProperty.call(memo, n)) {
      return memo[n]
    }
    return memo[n] = fibonacciRecursion(n, memoizedFn)
  }
})()
console.log('fibonacciRecursionMemoized', `${fibonacciRecursionMemoized(20)}`) // [LOG]: "fibonacciRecursionMemoized",  "6765"  

/**
 * Simple looping with no recursion
 */
function fibonacciPerformant(n: number): number {
  let step1 = 1, step2 = 0
  let tmp = null
  while (n > 0) {
    tmp = step1;
    step1 = step1 + step2;
    step2 = tmp;
    n--
  }
  return step2
}
console.log('fibonacciPerformant', `${fibonacciPerformant(20)}`) // [LOG]: "fibonacciPerformant",  "6765" 


/**
 * Iterable Iterator example
 */
class Fib implements IterableIterator<number> {
  protected fn1 = 0;
  protected fn2 = 1;
  constructor(protected maxValue?: number) {}
  public next(): IteratorResult<number> {
    var current = this.fn1;
    this.fn1 = this.fn2;
    this.fn2 = current + this.fn1;
    if (this.maxValue != null && current >= this.maxValue) {
      return {
        done: true,
        value: null
      } 
    } 
    return {
      done: false,
      value: current
    }
  }
  [Symbol.iterator](): IterableIterator<number> {
    return this;
  }
}
let fib = new Fib();
fib.next() //{ done: false, value: 0 }
fib.next() //{ done: false, value: 1 }
fib.next() //{ done: false, value: 1 }
fib.next() //{ done: false, value: 2 }
fib.next() //{ done: false, value: 3 }
fib.next() //{ done: false, value: 5 }
let fibMax50 = new Fib(50);
console.log(Array.from(fibMax50)); // [ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ]
let fibMax21 = new Fib(21);
for(let num of fibMax21) {
  console.log(num); //Prints fibonacci sequence 0 to 21
}

lang: JavaScript

/**

  • Fibonacci Generator Example */
function* fibonacci() {
  let current = 0;
  let next = 1;
  while (true) {
    let reset = yield current;
    [current, next] = [next, next + current];
    if (reset) {
        current = 0;
        next = 1;
    }
  }
}

const sequence = fibonacci();
console.log(sequence.next().value);     // 0
console.log(sequence.next().value);     // 1
console.log(sequence.next().value);     // 1
console.log(sequence.next().value);     // 2
console.log(sequence.next().value);     // 3
console.log(sequence.next().value);     // 5
console.log(sequence.next().value);     // 8
console.log(sequence.next(true).value); // 0
console.log(sequence.next().value);     // 1
console.log(sequence.next().value);     // 1
console.log(sequence.next().value);     // 2

lang: Dart

void main() {
  var i = 20;
  print('fibonacci($i) = ${fibonacci(i)}');
}

int fibonacciRecursion(int n) {
  return n < 2 ? n : (fibonacci(n - 1) + fibonacci(n - 2));
}

lang: TypeScript

/**
 * Get a factorial of a number using Recursion (UNOPTIMIZED)
 * @param {number} n 
 */
const factorialRecursion = (n: number): number => {
  return n <= 1 ? 1 : (n * factorialRecursion(n-1))
}

/**
 * Get a factorial of a number using Recursion (OPIMIZED: TAIL CALL)
 * @param {number} n 
 * @param {?number} accum the result value accumulator
 */
const factorialRecursionMemoized = (n: number, accum = 1): number => {
  return n <= 1 ? accum : factorialRecursion(n-1, n * accum)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment