Pascal's triangle is a triangular array of the binomial coefficients in a triangle. Read more about Pascal's triangle here.
The gif image below is from Wikipedia that demonstrates the formation of Pascal's triangle clearly.
Here is a recursive algorithm to find out the number at any given position.
Algorithm
function element_at(row, position)
If position = 0 OR position == row
return 1
else
return element_at(row - 1, position - 1) + element_at(row - 1, position)
The C program
The github repo - here
By the way, did you notice the elegance of the recursion? The code is almost same as the algorithm. Recursion makes code readable, concise and brilliant..!
9 comments:
'To iterate is human. To recurse is divine' (Have heard Pramode sir say this many times)
Almost all functions can be written in atmost 3-4 lines using functional programming.
I am learning Haskell here. In the first class, sir showed how to create tree data structure. It took just 1 lines.. And all related operations took 2-3 lines. And they were elegant and graceful. Not any obfuscated code.
This is a very beautiful peace of code!
This is a very beautiful piece of code!
Well, some people find the recursive Fibonacci elegant as well. Such examples are even used to teach the benefits of recursion.
These are real bad examples, as they compute the same intermediate results over and over again. Non-recursive solutions exist which are not only much more efficient, but also easy to write.
In my opinion, recursion is elegant only when it is the proper approach for the problem meant to be solved.
http://www.google.com/search?q=recursion
"Recursion makes code readable, concise and brilliant..!"
And then dynamic programming comes along and makes it fast as well.
Agree with Francois.
@François, It is true recursive Fibonacci is a bad idea as far as the efficiency is concerned. But it is a brilliant way to demonstrate how some algorithms just "fit-in" when using recursion in implementation. the code and the algorithms looks exactly the same.
Or maybe we can use it as the stepping stone to teach memoization :P
@Jithu, congrats on the Hacker News reference.
@alexp0205 Thats cool! I too want to get the hang of Haskell/
Clojure..:)
@ershadk :)
@Francois I agree to the point that there may be/are other non-recursive ways to solve problems(in this case nCr is the rth number in the nth row).
But in the lime light here, is the readability & easy-verifiability(inspired by the inherent essence of functional programming toward synthesizing programs that can be proved)
But given the advancing computing power, I think the recursive solutions could be far more better than the others(may be except for real-time applications requiring maximum efficieny)
@Sreeraj +1. Hacker news reference? Wow. Could you give me the link to that?
Here's the Lisp version:
https://github.com/jithusunny/Lisp/blob/master/pascal.lisp
Post a Comment