(if n === 1) ? then return 1 : else if previously calculated, f[n] > 0 ? then don't call recursive, return f[n] : else build the recursive stack and store every calculation in f so it can be reused when f[n] > 0 condition is checked
There are three return there: 1, f[n] or the recursive call f[n] = factorial(n-1) * n, depending on the value of n and f[n].
Hi myty,
Thanks for the explanation!
The link to the section on memoization was also very interesting.
So, it seems then that memoization is a form of caching that is used to reduce duplication of effort by your program, as previously calculated results don’t need to be recalculated.
Just to help this sink into my brain, I wrote a small script to compare the performance of a memoized function against that of the same non-memoized version.
The results were quite interesting:
var f = [],
timesCalledMemoizedFactorial = 0,
timesCalledrecursiveFactorial = 0;
function memoizedFactorial(n){
timesCalledMemoizedFactorial++;
if(n==1){
return 1;
} else {
if(f[n]>0){
return f[n];
} else{
return f[n] = memoizedFactorial(n-1) * n;
}
}
};
function recursiveFactorial(n){
timesCalledrecursiveFactorial++;
if (n <= 1){
return 1;
} else {
return recursiveFactorial(n-1) * n;
}
}
//Calculate the factorials 1 - 10)
for(var i=1; i<=100; i ++){
memoizedFactorial(i);
recursiveFactorial(i);
}
console.log("memoizedFactorial was called " + timesCalledMemoizedFactorial + " times.");
console.log("recursiveFactorial was called " + timesCalledrecursiveFactorial + " times.");
Output:
memoizedFactorial was called 199 times.
recursiveFactorial was called 5050 times.
Cool!
Anyway, memoized or not, you can still blow the call stack by passing it too large a number:
var f=[];
function factorial (n) {
return n == 1 ? 1 : f[n] > 0 ? f[n] : f[n] = factorial(n-1) * n;
}
console.log(factorial(30000));
Uncaught RangeError: Maximum call stack size exceeded
Whereas in Ruby, as of version 1.9.2 you can handle this with tail recursion:
RubyVM::InstructionSequence.compile_option = {
:tailcall_optimization => true,
:trace_instruction => false
}
eval <<EOF
def factorial(n, result = 1)
if n == 1
result
else
factorial(n - 1, n * result)
end
end
EOF
p factorial(30_000)
Output (in about 1.5 seconds):
27595372462193845993799421664254627839807620445293309855296350368000758688503605 ... 000
Although Ruby 1.9.2 actually ships with native support for tail recursion, it’s disabled by default and you have to either enable it through a compile-flag or by specifying the compile options at runtime (as above).
JavaScript does indeed kick a**e, but saying that, you gotta love Ruby!
In Javascript, normally I would look for an exception in this case:
var i = 0,
f = [];
function factorial (n) {
i = i + 1;
return n == 1 ? 1 : f[n] > 0 ? f[n] : f[n] = factorial(n-1) * n;
}
try {
console.log(factorial(30000));
} catch(e) {
console.log("That's more than I can handle!", i);
};
fact(171) is already Infinity… but you can trampoline your way into TCO in Javascript (http://raganwald.com/2013/03/28/trampolines-in-javascript.html). So Javascript is no slacker with big integer arithmetic… until ES6 brings us Proper Tail Calls.
For different runs there’s slightly different results, but on a side note, for me (Win8 x64) IE10 is the champion: it chokes on around 27000 (26477…27728). Op17 is stagnant: 15667. Surprise, surprise, Ch30 is also stagnant… at 15665. So Op, on the same Blink engine, allocates 2 more.
The worst is FF24 with Firebug: it stays at 6620, but it takes a lot longer to recognize its limit. With normal Firefox Developer Tool is returns undefined and Infinity, but it’s instant to resolve the stack.
I’ve also tested the nightly build of FF24 x64 and it shows a lot of promise: 26711, close to IE.
node.js 0.10.20.0 is performing slightly worse than Ch: 13973.
Also see this performance test and algos for fib: http://jsperf.com/tco-for-fibonacci/6
Syntax that looks like plain English may not be easier to write, especially for newbies. Like I explained, for absolute starters understanding the concepts of programming is more important than learning the syntax. With Rudy’s ‘do something unless otherwise’ the programming flow logic is not clear compared to ‘if…else’ statement. It’s easier to write once you already know what programming is about, but using such flexible and shortcut syntax to teach newbies will only make their lives harder. Good chance they learn how to write such code but don’t know when or why to use it. Just like ternary operator, I love it but refrain from using in my examples when presenting the code to amateur coders since it confuses them.
Thank you. I always thought Python was newer than PHP. I looked it up and it is much older!
For the record, Python isn’t as powerful as PHP.
I’ve been into PHP for a few years but recently got interested in python. It seems to be more powerful than PHP so I am surprised by this statement.
IMO Python would be easier for newbies and also teaches them some good habits like code indentation. But of course PHP skills are more lucrative.
An example of a python desktop app is the bitcoin client electrum. It’s very nice.
Ok, I never did any programing before, other then html and css, can make web sites. But would like to be able to program for my web sites, what should I learn first any particular language or beginners programing to get the concepts of programming, Thx
That depends entirely on what you are hoping to achieve.
Could you give us an example and then we will be able to advise you better.
I would be putting on my web site, contact page, forms with an email responds, login section of site, a page where user after they login can make changes to there team selections ( I guess that would be a database), Thx
C/C++ can be fun but also a complete pig if you have a bug. This is not the first language I started with, prior to learning some C and C++ I meddled in machine languages like Forth, the sort of stuff that made vending machines work before more complex systems came in to being like Java based systems.
JavaScript is to me fun to use, it is very simple language that should have a compilation module to allow quicker run-time in the browser, I am aware of the JScript option but that can break very easily if you need to edit a page for any reason. It really needs to be updated and given more power, in its youth it was abused by people and had its wings clipped but even today you still get people asking how to access files with it!!! So maybe it it should stay neutered.
Python I have no experience of but have installed the console several times with the promise that I would try doing things in it but never get the time to spend on it. If it were native to web browsers like JavaScript and VBScript then I would learn it.
VBScript - frankly, I don’t like it one bit, it reminds me of the QuickBasic that Miscorsoft developed as a tool for basic programmers to render an executable file. I did try QB and my first file that accepted an input and displayed “Hello <name of person>” was 100.7MB, I thought that was a tad excessive in size compared to the 180Kb of the compiled version for Windows.
PHP is really good to use for web development although I have seen comments about using it outside of a web page environment, it really isn’t meant to be used like that, its a bit like trying to turbo charge a robin reliant. I did use a shell script to call a PHP script because doing what I wanted in shell scripting was not easy and I required allot of help getting the shell script together because it is very cryptic. Still, I got the script to do what it was supposed to do and it called a PHP script to do the web server stuff.
Frameworks, not a great fan of these to be honest, if it can be done in PHP, why reinvent the wheel?
JavaScript frameworks, don’t go there, JQuery IS NOT JavaScript and it is one thing that does blow up my kilt a bit and I note that this site lumps JQuery in with JavaScript, IMHO it should have its own forum and leave JavaScript to the purists.
It surprises a lot of people that pick it up after learning another language. In many ways, it’s quite shocking that no one thought to use it to build websites sooner. The same can be said for Ruby. The language itself is a lot older than most think.
Power is relative, based on what you want to do. PHP is in no way a weak language, but as any PHP developer will know it’s very easy to write something that works, but isn’t pretty. To some, that is power. PHP can be used on pretty much any server, just by dropping the files onto the file system. If you’re using Python you’re probably using a framework, which needs setting up. If you’re using Django, you can’t just drop your files in and expect it to work. You need to register your apps, and you’ll want to ensure the correct level of separation. In PHP any sane developer would want to do the same, but if you really wanted you could just throw any old file in there and it’ll (probably) work.
Most modern languages are “nice” in that way. I write C# for a living and I find it to be one of the nicest languages to use day-to-day.
However, PHP is still the most widely used language around, because it’s been used for so long. Nowadays, I doubt there are many companies with a senior lead would choose to write PHP for a brand new project, so over the next 5-10 years I think PHP will become the next “legacy” language.
That being said, I’d say that Python and Ruby are more lucrative than PHP, easily. I’d then say that Java and C# are again much more lucrative. The reason for this is as I’ve said above. People will pay a limited amount of money to get someone to maintain a PHP project, because there are a lot of PHP devs out there. New projects are written in the others, and those with experience in the latter languages will probably find more pay because finding good developers in said languages is trickier.
Well has there a new language that emerges as it were going to take over PHP? I remember the node.js hype before, but it seems that the language still has a long way to go.
For web use, I’d say that most of the main offerings (C#, Ruby, and Python) are all more than mature enough for building websites. I’d even throw Java in there as well.
PHP will be around for another decade, without a shadow of a doubt. However, it’s very unlikely that we’ll see many brand new products built in PHP. If you want to learn a language, PHP will get you employed, but you’ll be likely to spend your time maintaining existing apps or extending existing code bases. A developer that knows one of the languages mentioned above is far more likely to be working on new software, or maintaining newer code bases.
I’m not a fan of Node.js. It fills a niche very nicely, and it’s a nice tool, but there’s something very dirty about using JavaScript, a language many people already hate, to write server-side code. Add the whole mess than is firing up your own Node.js server to serve production code instead of using tried-and-trusted Apache and Nginx and I feel that it’s got a LONG way to go.
If a beginning developer were to ask me what they should learn I’d say ASP.NET/C#, Ruby/Rails, or Python/Django. These three are the future of web development and are mature enough that you’ll always find work. They’re also built on very nice frameworks. PHP is nice to know, but most new work will probably be done in either Ruby or Python, and C# for those on the .NET stack.
If you really want to get crazy, there’s always Clojure and Scala. Both run on the JVM, and both are great fun to use. My experience with both are very limited, but they are growing in popularity and could be worth watching.
Hey ULTiMATE,
I’m not saying I disagree with you, but I’m curious as to why you think Ruby/Python will be increasingly favoured over PHP for new projects? Is this based on a general trend you’ve noticed?
Both languages and their frameworks are now mature enough to handle most web projects, and are vastly preferred by developers. Because of this, we’ll see a lot more technical projects started in Ruby and Python. You only need to look at any large technical community to notice this.
Additionally, if you look at a typical job board, you’ll see a lot of newer companies looking for Ruby and Python developers. Any company building a new web platform or application will immediately look towards Ruby or Python, because both are mature languages with rich libraries/frameworks.
I suppose it’s quite clear to see why. If you’re an experienced web developer, what would you rather choose to write software in? A decade ago, PHP was far better to write code in than Perl. Now, Ruby and Python offers a cleaner architecture, and boasts rapid development as a part of their strongest frameworks. Not only that, but both languages are a lot cleaner than PHP. This is why the trend to move towards Ruby and Python are already in place.
This is a bit of an over reach. This is regional dependent. Here in Columbus OH, you’ll see about 1-2% are Ruby, Python, Perl while aprox 30-40% are LAMP stack postings, and the remainder being .NET
This is also arguable, except for the “cleaner” part.
I strongly disagree with the idea that no new code will be written using PHP. That is ridiculous. PHP is great and there is a lot of code and talent you can build on. This is important because nothing is written from scratch anymore.
Well this… Yes there are still new code written in PHP, actually more than in Python, Ruby, Node.js, C#.net. Nonetheless, most of them are either open source or noncommercial softwares. The situation is quite different if we are talking about enterprise softwares/applications, but one can then argue that PHP was never seriously applied in enterprise application development in the very first place(it was mostly java servlet/JSP, C#.net, and now we see Python too).
That percentage is quite good, considering that Ruby and Python have only been popular for building websites for a few years. Also bearing in mind that both are improving considerably over time, I reckon we’ll see that number grow over the years, with PHP to decline.
How is it arguable? Rails and Django are established frameworks, and given that a lot of PHP developers build straight from WordPress it’s almost solid fact that you’ll get cleaner code from a framework than from hacking on WordPress or writing without a framework.
Your comment offers very little to the discussion. How is PHP great, exactly? Also, how is “having lots of code” a good thing when a lot of that code is quite poor?
You’re right that nothing is built from scratch any more. It’s exactly why Rails and Django have taken off as well as they have, because they enforce the use of a framework.
We’ll lets get something cleared up here. Your comparing Django and rails to Wordpress? Seriously? How about a real framework not some lazy mans pile of crap code (not to bash wordpress for what it is, but it is not a true framework)
Enforcing the use of a framework is not necessarily always a good thing either.