Consider a simple function that adds the first N natural numbers. (e.g. sum(5) = 0 + 1 + 2 + 3 + 4 + 5 = 15
).
Here is a simple JavaScript implementation that uses recursion:
function recsum(x) {
if (x === 0) {
return 0;
} else {
return x + recsum(x - 1);
}
}
If you called recsum(5)
, this is what the JavaScript interpreter would evaluate:
recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + (1 + recsum(0)))))
5 + (4 + (3 + (2 + (1 + 0))))
5 + (4 + (3 + (2 + 1)))
5 + (4 + (3 + 3))
5 + (4 + 6)
5 + 10
15
Note how every recursive call has to complete before the JavaScript interpreter begins to actually do the work of calculating the sum.
Here's a tail-recursive version of the same function:
function tailrecsum(x, running_total = 0) {
if (x === 0) {
return running_total;
} else {
return tailrecsum(x - 1, running_total + x);
}
}
Here's the sequence of events that would occur if you called tailrecsum(5)
, (which would effectively be tailrecsum(5, 0)
, because of the default second argument).
tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15
In the tail-recursive case, with each evaluation of the recursive call, the running_total
is updated.
Note: The original answer used examples from Python. These have been changed to JavaScript, since Python interpreters don't support tail call optimization. However, while tail call optimization is part of the ECMAScript 2015 spec, most JavaScript interpreters don't support it.
Modern browsers have Array#includes
, which does exactly that and is widely supported by everyone except IE:
console.log(['joe', 'jane', 'mary'].includes('jane')); //true
You can also use Array#indexOf
, which is less direct, but doesn't require polyfills for outdated browsers.
console.log(['joe', 'jane', 'mary'].indexOf('jane') >= 0); //true
Many frameworks also offer similar methods:
- jQuery:
$.inArray(value, array, [fromIndex])
- Underscore.js:
_.contains(array, value)
(also aliased as _.include
and _.includes
)
- Dojo Toolkit:
dojo.indexOf(array, value, [fromIndex, findLast])
- Prototype:
array.indexOf(value)
- MooTools:
array.indexOf(value)
- MochiKit:
findValue(array, value)
- MS Ajax:
array.indexOf(value)
- Ext:
Ext.Array.contains(array, value)
- Lodash:
_.includes(array, value, [from])
(is _.contains
prior 4.0.0)
- Ramda:
R.includes(value, array)
Notice that some frameworks implement this as a function, while others add the function to the array prototype.
Best Answer
Hashing is a function that applies to an arbitrary data and produces the data of a fixed size (mostly a very small size). There are many different types of hashes, but if we are talking about image hashing, it is used either to:
Images that look identical to us, can be very different if you will just compare the raw bytes. This can be due to:
Even if you will find an image that will be different just in one byte, if you will apply a hash function to it, the result can be very different (for hashes like MD5, SHA it most probably will be completely different).
So you need a hash function which will create a similar (or even identical) hash for similar images. One of the generic ones is locality sensitive hashing. But we know what kind of problems can be with images, so we can come up with a more specialized kind of hash.
The most well known algorithms are:
By the way, if you use python, all these hashes are already implemented in this library.