Tail Recursion

Tail recursion is special case of recursion where the function calls itself as the last statement in the method.

From wikipedia:

Tail calls can be implemented without adding a new stack frame to the call stack. 

Here's an example of Sum of Ints function that sum Integers between a and b

so when call sumOfInts(1, 4) would equals 1 + 2 + 3 + 4 = 10

First implementation using non-Tail recursion:

def sumOfInt(a: Int, b: Int): Int =

        if (a > b) 0 else a + sumOfInt(a + 1, b) // last stmt is a call to the same function and then add some value to it (non tail recursion)

The second implementation using a Tail recursion function:

def sumOfInt2(a: Int, b: Int): Int =

        sumOfAllInts(a, b, 0)                    

def sumOfAllInts(a: Int, b: Int, t: Int): Int =

        if (a > b) t else sumOfAllInts(a + 1, b, t + a)  // last stem is a call to the same function only (tail recursion)

Test

sumOfInt(1, 100000000)                        //> java.lang.StackOverflowError

sumOfInt2(1, 100000000)                       //> res2: Int = 987459712

Conclusion

The Tail recursion version using the same stack frame on each call (vs the non-tail recursion which  will use a new stack frame for each call for the reclusive method)

See this question and read the answer to understand about Tail Recursion: http://cs.stackexchange.com/questions/6230/what-is-tail-recursion

Increment Base64 numbers

In Short-url service, I need to have unique numbers that consist of 4, 5 or 6 digits at most.

If I use the decimal system (base 10), and If I constraint myself with 5 digits, I'll have maximum of 10^5 (= 100000) unique values, but this is less than enough!

So, I need to us some other number system with higher base. What about base 64?

In base 64, we have 64^5 (=1073741824) unique values... ohh this is good.

In the decimal system, I can start with 0 and use the `+` operator to increment this values.. but in base 64 I have to write the `increment` operation myself.

Here's  the method I wrote (in Java8) and the results shows that, the 1,000,000,000 th value is `6lrnA`.

So, after increment billion times, I can have this `6lrnA` value of 5 digits, so It is perfect for such service.

The code:

import java.util.List;
import java.util.stream.Collectors;

public class Base64Incremental {

    static final String allChars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";

    public static void main(String[] args) {
        String s = "A";
        for (int i = 0; i < 1000000000; i++) {
            s = incr(s);

            if (i % 100000000 == 0) {
                System.out.printf("i = %d => s = %s\n", i, s);
            }
        }
        System.out.println(s);
    }

    static String incr(String in) {
        List<Character> chars = in.chars().mapToObj(i -> (char) i).collect(Collectors.toList());
        add(chars, chars.size() - 1);
        return chars.stream().map(c -> String.valueOf(c)).collect(Collectors.joining());
    }

    static void add(List<Character> chars, int i) {
        int index = allChars.indexOf(chars.get(i));

        // if the char value is not highest value in the number system (not 9 as
        // if it was decimal system)
        if (index < allChars.length() - 1) {
            // increment the value by 1
            chars.set(i, allChars.charAt(index + 1));
        } else {
            // else, (the char value is the highest value in the number system,
            // then should place the least value in the number system here (0 in
            // decimal system)
            chars.set(i, allChars.charAt(0));
            // then check, if this char is not the highest order char (the most
            // left char), if so perform the same func again on the next char
            if (i != 0) {
                add(chars, i - 1);
            } else {
                // otherwise, just insert a number on the left to be the
                // highest order with the low value
                chars.add(0, allChars.charAt(0));
            }
        }
    }
}

The result:

i = 0 => s = B
i = 100000000 => s = E8dDB
i = 200000000 => s = K57HB
i = 300000000 => s = Q3ZLB
i = 400000000 => s = W03PB
i = 500000000 => s = cyVTB
i = 600000000 => s = ivzXB
i = 700000000 => s = otRbB
i = 800000000 => s = uqvfB
i = 900000000 => s = 0oNjB
6lrnA

That's All!

Dynamic Programming VS Dynamic Langugage VS Dynamicly-Typed Language

Three Concepts need to be clear:
Dynamic Programming:
Is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems which are only slightly smaller[1] and optimal substructure (described below). When applicable, the method takes far less time than naïve methods.

Dynamic Programming Language:
Is a term used broadly in computer science to describe a class of high-level programming languages that execute at runtime many common behaviors that other languages might perform during compilation.

Dynamic Type:
A programming language is said to be dynamically typed when the majority of its type checking is performed at run-time as opposed to at compile-time.

simple dictionary using binary search

//strcmp.c

#include <stdio.h>

int my_strcmp(const char[], const char[]);

/*
// testing..
int main(void)
{

    printf("%i\n", strcmp("alpha", "altered"));
    printf("%i\n", strcmp("zioty", "yucca"));

    getchar();
    return 0;
}
*/

int my_strcmp(const char str1[], const char str2[])
{
    int i=0;

    while (str1[i] == str2[i] && str1[i] != '\0' && str2[i] != '\0')
        i++;

    if (str1[i] > str2[i])
        return 1;
    else if (str1[i] < str2[i])
        return -1;
    else
        return 0;
}

// simple dictionary using binary search
// auther mhewedy
// date : 2010-08-13
// compiled under GCC 4.x

#include <stdio.h>
#include <string.h>
#include "strcmp.c"

#define DICT_LENGTH 3

typedef struct _dictionary_s dictionary;
struct _dictionary_s
{
    char word[20];
    char definition[50];
};

int lookup(const char[], const dictionary[], int);
int binary_lookup(const char[], const dictionary[], int, int);

int main(void)
{
    static const dictionary dict[DICT_LENGTH] =
    {
        {"a", "first letter in alphabatic"},
        {"b", "second letter"},
        {"c", "third letter"}
    };
    char word[20];
    int ret=-1;

    do{
        printf("Enter word: \n");
        if (gets(word) == NULL)
            break;
        ret = binary_lookup(word, dict, 0, DICT_LENGTH-1);

        if (ret < 0)
        {
            fprintf(stderr, "word not found!\n");
        }
        else{
            printf("%s : %s\n", word, dict[ret].definition);
        }
        printf("\n");
    }while (1);

    return 0;
}

int binary_lookup(const char word[], const dictionary dict[], int start, int end)
{
    if (start > end)
        return -1;

    int middle = (start+end)/2;
    int cmp = my_strcmp(word, dict[middle].word);

    if (cmp == -1)
    {
        end = middle -1;
        binary_lookup(word, dict, start, end);
    }
    else if (cmp == 1)
    {
        start = middle +1;
        binary_lookup(word, dict, start, end);
    }
    else // 0
    {
        return middle;
    }
}

int lookup(const char word[], const dictionary dict[], int length)
{
    int i;
    for (i=0; i<length; i++)
    {
        if (strcmp(word, dict[i].word) == 0)
            return i;
    }
    return -1;
}

Bubble Sort, Selection Sort and Insertion Sort

Here's sample implementations in C for Bubble, selection and insertion sorts:

#include <stdio.h>

void bubble_sort(int[], int);
void selection_sort(int[], int);
void insertion_sort(int[], int);

void print(int[], int);

int main(void)
{
    int arr[]={15, 10, 3, 8, 1, 58, 2};
    print(arr, sizeof(arr)/sizeof(int));
    //bubble_sort(arr, sizeof(arr)/sizeof(int));
    //selection_sort(arr, sizeof(arr)/sizeof(int));
    insertion_sort(arr, sizeof(arr)/sizeof(int));
    print(arr, sizeof(arr)/sizeof(int));

    return 0;
}

void bubble_sort(int arr[], int length)
{
    int outter, inner;

    for (outter=length-1; outter>=1; outter--)
    {
        for (inner=0; inner<length-1; inner++)
        {
            if (arr[inner] > arr[inner+1])
            {
                int tmp = arr[inner];
                arr[inner] = arr[inner+1];
                arr[inner+1] = tmp;
            }
            //print(arr, length);
        }
    }
}

void selection_sort(int arr[], int length)
{
    int outter, inner;

    for (outter=0; outter<=length-1; outter++)
    {
        int min = outter;
        for (inner=outter+1; inner<=length-1; inner++)
        {
            if (arr[inner] < arr[min])
                min = inner;
        }
        if (min != outter)
        {
            int tmp= arr[min];
            arr[min]= arr[outter];
            arr[outter] = tmp;
        }
        //print(arr, length);
    }
}

void insertion_sort(int arr[], int length)
{    
    int outter, inner, tmp;
    for (outter=1; outter<=length-1; outter++)
    {
        inner = outter;
        while (inner>0 && arr[inner-1]>arr[inner])
        {    
            //print(arr, length);
            tmp = arr[inner];
            arr[inner] = arr[inner-1];
            arr[inner-1] = tmp;
            inner--;
        }
    }
}

void print(int arr[], int length)
{
    int i=0;
    for (;i<length; i++)
    {
        printf("%i ", arr[i]);
    }
    printf("\n");
}