4 ms·
Decent enough explanation of recursion. Why not take it further and produce a more general solution? In JavaScript I'd write something like this: functio
by user24 14y ago
Decent enough explanation of recursion.
Why not take it further and produce a more general solution?
In JavaScript I'd write something like this:
function recurseBetween(start, end, callback) {
// Create a recursive function
// which checks the limits and calls the supplied callback
var recursiveCallback = function(i) {
// Call the original callback
callback(i);
// If we're at the end, stop
if(i >= end) {
return;
} else {
// Else increment and recurse
recursiveCallback(++i);
}
};
// Start recursing with the start value
recursiveCallback(start);
}
Now you can use recurseBetween almost exactly as you would a for loop:
recurseBetween(1, 10, function(i) {
console.log(i);
});
You could even abstract the start and max arguments as callbacks, and you could supply a callback to perform the increment too so that you're not limited to integral addition.
- user24 14y agoHere's a completely abstracted version, but I'm certain it's less clear to use ;) function recurseBetween(initial, hasEnded, modify, callback) { // Overwrite the callback with a recursive version: var recursiveCallback = function(i) { // Call the original callback callback(i); // If we're at the end, stop if(hasEnded(i)) { return; } else { // Else increment and recurse recursiveCallback(modify(i)); } }; // Start recursing with the start value recursiveCallback(initial()); } Which transforms our for loop example to: recurseBetween(function() { return 1; }, function(i) { return i<=10; }, function(i) { return i++; }, function(i) { console.log(i); }); Which at first glance is unwieldy, but gives complete control to the calling script, such that we could do things like introduce a step: recurseBetween(function() { return 1; }, function(i) { return i<=100; }, function(i) { return i+=10; }, function(i) { console.log(i); }); Or even more exotic things. In reality, this syntax is too complicated. I would probably introduce some helpers; eg you could pass in a straight integer or a function and it would deal with it. I'd also probably send the arguments as named parameters so the syntax looked like this instead: recurseBetween({ 'start': 1, 'end': 100, 'modify': function(i) { return i+=10; }, 'callback': function(i) { console.log(i); } }); Which is a little clearer. Obviously the example is somewhat contrived because in reality you'd just use a for loop! But an interesting exercise nonetheless.
- jewbacca 14y agoWhat you're inventing here is usually called "unfold". I don't know javascript, but here it is in close relative Scheme: (define (unfold p f g seed) (if (p seed) '() (cons (f seed) (unfold p f g (g seed))))) And how you would call it to print "Hello world!" 100 times: (unfold (lambda (x) (> x 100)) (lambda (x) (display "Hello world")) (lambda (x) (+ x 1)) 1) 'p' is your predicate. It determines when to stop unfolding. It takes the current value ('seed') and returns a boolean that's True when you're done. It's your 'hasEnded'. 'f' is what to do for each 'seed' value. In this case, it ignores the current value and just prints "Hello world". It's your 'callback'. 'g' maps each 'seed' value to the next 'seed' value. It's your 'modify'. 'seed' is the initial state for the unfold. It's your 'initial'. ----- There are a couple other caveats to do with this being an expression rather than a statement, but it doesn't really matter right now. There are a million other cool things about unfolds (and folds, and other higher-order functions), but I'm not sure I could conscionably point you in the right direction since they lead to dangerous places. Speaking of which, here is an unfold in Haskell, where it may (may) be clearer: unfold p f g seed | p seed = [] | otherwise = x:xs where x = f seed xs = unfold p f g (g seed) sequence_ $ unfold (>100) (const $ print "Hello world!") (+1) 1 I say 'an' unfold, because there are a whole bunch of cool ways to do it (and some of them look nothing like this).
- user24 14y agoYeah I've done a bit of haskell at uni, it only struck me later how similar it is(/can be) to JS.
- f055 14y agoOr go back to C and learn that recursion is not really used like that. If you know the limits beforehand, use "for". If you don't know how deep the processing will go, use recursion. If you must code a loop without using "for" it means you're doing a homework ;)