i hav forgotten wot sleep is.. my room has mountain dew nd energry drink cans evrywer.. evrything is like dumpd on the floor everywer... but imstillalive .. tobehonest im in a daze right now.. nt sure wot i am writing and why i am doing this...whoami???... in the past 48 hours.. i hav redesigned processor microcode, given the most anticlimatic 123 exam ever.. rote a hilarious business plan fr techcomm (expected revenue: 100 mil in 5 yrs w00t), ritten sum huuge ass 212 concurrency ml program wich did nt evn compile, riten a 'Mini Unix Shell' ..lol. ritten my last japanese essay and painfulli learnt the stack handling conventions for ps18240...
problem is that beyond 3am .. my body shifts to allnighter mode.. nd because of the large number of starbucks doubleshots wich abhinav askd me to buy fr him wich mysteriousli dissapeared frm my fridge...i reeli cant sleep.. so im going to blog!!! ...... lucky u! :P
ok wen i made this thing.. i had all these grand plans nd ambitions abt riting a post everyweek.. nd getting millions of readers on rss nd making a gazellion dollars through google ads nd changing the world. bigtime.. but i guess thts nt the case......uptill now
one of the things i wantd to do with this blog is try nd explain stuff i find kinda kool..nd see how ppl react. .......u see..... im reeli reeli bad at explaining stuff... but i wanna change tht.. also i find a bunch of reeli kool computer stuff reeli kool.. because of wich a bunch of very weird ppl consider me to be very weird.. so lemme change tht stuff nd kill two stones with one bird nd try to rite a geeky post.. heregoes..
RECURSION
Recursion is a reeli kool idea in computer science.. its pretty simple to understand but the implications of it.. are reeli kool and deep..
Recursion is essentially the art of solving problems by just rephrasing the problem in terms of itself..
It might seem like a very lazy way to go about doing things... but it can often be the best
First off we start of with a stupid math example
Suppose u wanna find the factorial of a number.. wich basically means u want the product of all the numbers starting from 1 that are less than n
so factorial of 2 is 1 x 2 = 2 and factorial of 7 is 1 x 2 x 3 x 4 x 5 x 6 x 7 = 5040
u can write a conventional program to do this which wud look sumthing like this
Let y initially represent the number 1
Let z initially be 1 but then cycle through the values [2,3,4,5,6...x]
For every cycle of z
Let y now represent the number that is the product of the old value of y with the value of z
At the end of all the cycles, we know that the Factorial of x is the value of ywhich in an actual code, looks like
def fac(x):
y=1
for z in range(1,x+1):
y = y * z
return yThis is nice cos we can see exactly what is doing.. it is multiplying y with every number between 1 to x to give us what we want
But its a lot of code for a pretty simple problem...
Can we do any better???
.......Turns out we can, if we try to be lazy (in cs, that can be a good thing)
Whats the factorial of 1?.. well its 1
Whats the factorial of 2?.. its the product of 2 and 1 = 2
Whats the factorial of 3?.. its the product of 3,2 and 1 = 6.. but wait a sec.. To calculated the factorial of 3 i had to find 3 x 2 x 1 wich is nothing but 3 x factorial of 2
Similarly for 4.. factorial of 4 is nothing but 4 x factorial of 3
Hey thats kinda nice.. with this in mind, I can make a cooler factorial function --
Factorial for a number x:
If x is 1 then the Factorial of x is also 1
Otherwise the Factorial of x is the product of x and the Factorial of (x-1)
in code
def fac(x):
if x==1: return 1
return x * fac(x-1)Both convey exactly the same information, and for all good input give identical output.. yet the 2nd one is a lot easier to read and type in and reason about.
The 2nd one recognizes the fact that any instance of the problem can be decomposed down to a simpler version of that problem until we reach the end of the line - the base case = 1
Now for the cooler non-math example...
Have u played chess?? ... If yes, u probably realize the fact that its not exactly easy to figure out what your next move should be.. in fact, in many cases, u mite have played some arbitrary move with no specific reason for choosing it, just hoping that it works out..
Making a computer play random moves is also easy.. but making a chess-playing program is a pretty complicated thing to do.. This was researched a lot in many US unis many years before I decided to get born and some people even won an award for it...
Suppose you have function called 'getBestMove' which when given a chess board will tell you what is the best move the player playing next can make and do this by giving it a score :: a number indicating how awesome that move is
def getBestMove(chessBoard):
does wotever it needs to do find best move
print bestMove
return sumNumberIndicatingHowAwsumThatMoveIs
It was easy uptill now.. but now that we need to replace the 2nd line with actual code, we r in big trouble..
How the hell can we figure out the best move for this player???
One way to think about it, is to think in our enemy's shoes..
In real life, the best way to fight competition can be
[[will finish riting this l8r]]
Example.. suppose you had a computer that could only add or subtract 1 to any number and u wanted to make a system that could add any arbitrary numbers a and b
you could do sumthing like
def add(a,b):
if a=0:
return b # because 0+b is just b for any b
else:
return 1+( add(a-1, b) ) 
No comments:
Post a Comment