| Author | Message | ||
     Dolby_digital Junior Artist Username: Dolby_digital Post Number: 405 Registered: 03-2008 Posted From: 24.174.7.22 Rating: N/A |
| ||
| Simba Junior Artist Username: Simba Post Number: 293 Registered: 02-2008 Posted From: 24.228.73.121 Rating: |
Well, recursion is just another paradigm of programming like iterative/parallel/OOPs etc. It has its own pros (coding elegance) and cons (memory inefficiency). One would use the right coding depending on architecture/env. and prog. language. Anyways, question to OP (Der). I would like to know the intent of the thread. A) You don't know the answer and would like to find one. B) You know the answer but like to see if any desis are up to your caliber of thinking. C) You would like to discuss the benefits of recursion over others. D) None of the above. Don't take me wrong. I am not ready for any heated arguments. | ||
| Dolby_digital Junior Artist Username: Dolby_digital Post Number: 404 Registered: 03-2008 Posted From: 24.174.7.22 Rating: N/A |
It's not just the space complexity I am talking about, it's about performance. Consider memory swaps. Each repetitive call to a function has its own private memory which is huge overhead on cache. Please refer to chapter 5 of "Computer Systems: A programmer's perspective" which illustrates the fact. example from the book: for a given function f(x), f(x)+f(x)+f(x)+f(x) would perform slower than 4*f(x) as you have only one call to f(x) in the latter. | ||
| Jkm Side Hero Username: Jkm Post Number: 2361 Registered: 02-2008 Posted From: 216.235.145.202 Rating: N/A |
both using stack class and recursive method creates same space complexity. infact recursive function takes more space and cpu cycles. recursive code ultimately uses processor stack. i used java stack class as an example to show how recuirsive code works. If i don't have reverse method in StringBuffer, here is how i would reverse a string String reverseString(String str) { StringBuffer sb = new StringBuffer(); for (int i=str.length();i>0;--i ){ sb.append(str.substring(i-1,i)) } return sb.toString(); } in C we should free the memory by calling free function , but in java we have to rely on garbage collector. here i am muting a string by using StringBuffer. no space/CPU issues. tester may not like this code but i created a QA job to test mutable stringbuffer. ok inka chaalu ee rojuki. | ||
| Der_schuler Junior Artist Username: Der_schuler Post Number: 829 Registered: 01-2009 Posted From: 99.140.160.102 Rating: N/A |
Yes. Thats a way...But remember you create an additional space complexity of the order O(n) by creating a stack which is fine I guess cuz recursive code suffers with the same memory issue....The stack method also suffers with the same problem as a sequential code as in if you halt your program before completion, the original string might have gotten modified by that halt point(actually decreased in length). The major draw back in this is that the process of debugging involves changes of state!!!! The purely functional code on the other hand creates a new string with out muting the original string!! | ||
| Jkm Side Hero Username: Jkm Post Number: 2360 Registered: 02-2008 Posted From: 98.192.47.28 Rating: N/A |
read it as recursive function | ||
| Jkm Side Hero Username: Jkm Post Number: 2359 Registered: 02-2008 Posted From: 98.192.47.28 Rating: |
learned something new and intresting today when i googled on PUSH and POP if you don't want to use StringBuffer reverse method then go for stack class in java. just like LIFO stack in 8086 assembly language. any recusion function actually does low level PUSH and POP operations on stack when code becomes machine language. here is how we can do it in java using class Stack Stack<string> stk = new Stack<string>(); for (int i=0;i<str.length();i++){ stk.push(str.substring(i,i+1)); } String retStr = ""; while(!stk.isEmpty()){ retStr += stk.pop(); } | ||
| Dolby_digital Junior Artist Username: Dolby_digital Post Number: 402 Registered: 03-2008 Posted From: 24.174.7.22 Rating: N/A |
intha veejee ga unDaDaaniki kaaraNam strong Native language base. aa nuances understand programmers ku arthamaitae inkaa easy programs develop cheyyacchu. | ||
| Jkm Side Hero Username: Jkm Post Number: 2358 Registered: 02-2008 Posted From: 98.192.47.28 Rating: |
life entha easy kada ippudu return ( new StringBuffer(str). reverse().toString()); der thammud torture chesthunnadu ga thana intelligence tho | ||
| Rasputin Side Hero Username: Rasputin Post Number: 4078 Registered: 02-2008 Posted From: 74.131.202.205 Rating: N/A |
Reverses the string | ||
| Cinejeevi Comedian Username: Cinejeevi Post Number: 1105 Registered: 01-2008 Posted From: 69.120.84.91 Rating: N/A |
ee thread save sesi inko rendu dasabdaalu poyaka naa pillalaki soopetti appatlo naa parichayaalu ilantollato undevi ani collar egaresukuntaa naa toli santakam.... | ||
| Der_schuler Junior Artist Username: Der_schuler Post Number: 828 Registered: 01-2009 Posted From: 99.140.160.102 Rating: N/A |
Sure....You can always make one pass through the given string...start two pointers at either end and just swap...until one reaches the middle..i.e the pointers cross each other or point to the same... But the point here is elegance...you are indeed correct when you pointed out the iterative scheme but functional approach has advantages steeped in ease of debugging and look at the code. if you are a tester, its a dream to see such code. | ||
| Cinejeevi Comedian Username: Cinejeevi Post Number: 1104 Registered: 01-2008 Posted From: 69.120.84.91 Rating: N/A |
OT babai maree pichchollu anna padam baalekapoina adedo cinema lo eero ilage godala ninda evevo equations raasestaa untadu. Russel Crow anukuntaa eero.. nakenduko thread pai paina sootte ade gurtochchindi. naa std dialogue about software ala Tagore: Software lo naaku nachchani okE okka padam "Development" naa toli santakam.... | ||
| Onlytruth Legend Username: Onlytruth Post Number: 41685 Registered: 01-2007 Posted From: 173.50.165.146 Rating: |
 | ||
| Simba Junior Artist Username: Simba Post Number: 284 Registered: 02-2008 Posted From: 24.228.73.121 Rating: N/A |
Sorry boss. Porapaatu ga quote chesaanu. | ||
| Okatelugodu Side Hero Username: Okatelugodu Post Number: 4978 Registered: 02-2008 Posted From: 98.221.49.98 Rating: N/A |
Incorrect quoting anukunta..adi annadi OT  | ||
| Simba Junior Artist Username: Simba Post Number: 283 Registered: 02-2008 Posted From: 24.228.73.121 Rating: N/A |
Correcte nandi. Mari dheeniki mandhu leda? Actors ni, politicians ni caste-based comments cheste thaggipothundhantaara? Koncham salahalu ivvandi. | ||
| Okatelugodu Side Hero Username: Okatelugodu Post Number: 4977 Registered: 02-2008 Posted From: 98.221.49.98 Rating: N/A |
I mean reconstructing a string by replacing 'i' th character with (StringLength-1-i) th character. Offcourse in Java if it is done using String object lot of abandoned strings will be left in the String constant pool thus wasting memory. There are workarounds to this using say a StringBuffer in Java | ||
| Onlytruth Legend Username: Onlytruth Post Number: 41682 Registered: 01-2007 Posted From: 173.50.165.146 Rating: N/A |
Picholla thread  | ||
| Okatelugodu Side Hero Username: Okatelugodu Post Number: 4976 Registered: 02-2008 Posted From: 98.221.49.98 Rating: |
I dont understand why recursion would be of any added advantage here. Just an iteration over the string would accomplish it. | ||
| Simba Junior Artist Username: Simba Post Number: 282 Registered: 02-2008 Posted From: 24.228.73.121 Rating: N/A |
REC warangal, CSE. I never thought of studying after my B.Tech. Never went to school in US. | ||
| Der_schuler Junior Artist Username: Der_schuler Post Number: 827 Registered: 01-2009 Posted From: 99.140.160.102 Rating: N/A |
If u dont mind, where did u attend school at in India and here | ||
| Simba Junior Artist Username: Simba Post Number: 281 Registered: 02-2008 Posted From: 24.228.73.121 Rating: N/A |
Yup. It is such a short book with huge wealth of information. Every time you read this, you come across something new to learn. | ||
| Der_schuler Junior Artist Username: Der_schuler Post Number: 826 Registered: 01-2009 Posted From: 99.140.160.102 Rating: N/A |
K&R teached the semantics of a lang....but per me if one understands the formalism of a lang and proper idea of how top level semantics are written to mimic lower level assembly....its enough...ppl will write good code with that sound understanding and some training in Algos....... Imperative Langs.....say X=a X++ are properly mimicing the instruction set equivalents of Shift, fetch, Skip etc.... the biggest problem though is the following...THE CPU fetches a WORD from the memory, does a computation on it and sends the WORD back...and everything is sequential...if previous word changed something pertaining to a word before..U have caught urself in a web of serialism | ||
| Wrathchild Side Hero Username: Wrathchild Post Number: 2758 Registered: 03-2009 Posted From: 69.136.169.198 Rating: N/A |
k&r is also a good book for learning how to write good code | ||
| Der_schuler Junior Artist Username: Der_schuler Post Number: 825 Registered: 01-2009 Posted From: 99.140.160.102 Rating: N/A |
I know one by Sipser. I had very strong interests in Complexity and Computability..But now I dont find proper time...Grad school was one such heaven for intellectual replenishment | ||
| Der_schuler Junior Artist Username: Der_schuler Post Number: 824 Registered: 01-2009 Posted From: 99.140.160.102 Rating: N/A |
Agreed...but if purely functional style of prog is stuck to...I think one can overcome this..... But think abt the ease in say Unit testing code.....Dream....purely functional code doesnt have side effects so.....A function within itself is a first class entity.....doesnt alter states...of computation | ||
| Simba Junior Artist Username: Simba Post Number: 280 Registered: 02-2008 Posted From: 24.228.73.121 Rating: N/A |
That's right, it is by Donald Knuth. I had read this like 15 years ago. I don't have a habit of collecting books, so could not remember. There are nice books on "Theory of Computation" (I can't remember the author of the one I read) which gives the fundamentals of computing right from turing machines. This leads to regex, parsing and to compiler technics, followed by OS principles. An interested read if you have not yet. | ||
| Dolby_digital Junior Artist Username: Dolby_digital Post Number: 401 Registered: 03-2008 Posted From: 24.174.7.22 Rating: N/A |
Recursive programming may be comp. scientist's especially mathematician's delight, but not for an architect considering its performance complexity. It uses up memory. | ||
| Der_schuler Junior Artist Username: Der_schuler Post Number: 823 Registered: 01-2009 Posted From: 99.140.160.102 Rating: N/A |
If you are referring to Knuth's books....I have all the volumes in my book shelf...I love Knuth's style of teaching Copm Sci.... | ||
| Simba Junior Artist Username: Simba Post Number: 279 Registered: 02-2008 Posted From: 24.228.73.121 Rating: N/A |
I bet meeru "Art of Programming by Dijkstra" chadivi untaaru. But in today's world, so many libraries and frameworks are available, which makes programming a science rather than art. | ||
| Der_schuler Junior Artist Username: Der_schuler Post Number: 822 Registered: 01-2009 Posted From: 99.140.160.102 Rating: N/A |
A discipline of programming ane book chadivara...by none other than Dijkstra....I loved that book.... Mythical Man monthly kooda | ||
| Der_schuler Junior Artist Username: Der_schuler Post Number: 821 Registered: 01-2009 Posted From: 99.140.160.102 Rating: N/A |
Agree.....Having a good curriculum in always a good thing if one is willing to work hard. Naa case lo....since I was a aerospace student, our prereq was to know how to code either in c or fortran..... Naakemo physics ante pichi undedhi...naa intuition antha physical causalty meedha build cheskunna appati varaku.....so for a computational course tho...aa padathi pani cheyyala..... Learn everything from first principles naaku ee okka vishyam lo kalisi raaledhu...But it was worth the effort..oka 1 year...library lo koorchoni...weekends chadive vadni...Comp Arch and OS....appudu I became really confident...with stuff as in intuitively | ||
| Der_schuler Junior Artist Username: Der_schuler Post Number: 820 Registered: 01-2009 Posted From: 99.140.160.102 Rating: N/A |
Not included andi..Ok covention specify cheyyalsindhi...My bad | ||
| Simba Junior Artist Username: Simba Post Number: 278 Registered: 02-2008 Posted From: 24.228.73.121 Rating: N/A |
Fortunately, we had a nice curriculum for comp sci in our college. At one end we started with programming languages: Structured (pascal, c), Iterative (cobol,fortran), recursive (lisp), parallel (SmallTalk), OO (C++) over the years. On the other end, in electronics course, learnt about diodes, transistors, amps. and micro-proc along with hands-on. Towards the end we had chance to code in assembly and on micro-proc kits in machine language to understand what goes on inside the black-box. of course, there were theoretical comp sci and discrete maths class to get a detail understanding. | ||
| Mallik Side Hero Username: Mallik Post Number: 4456 Registered: 10-2008 Posted From: 162.116.29.69 Rating: N/A |
Ee logic prakaaram ath character included aa not included aa, resulting string lo? And first character ante 1 aa 0 naa? In this db, there's always someone watching you!!  | ||
| Der_schuler Junior Artist Username: Der_schuler Post Number: 819 Registered: 01-2009 Posted From: 99.140.160.102 Rating: N/A |
yeah....Garbage Collection is a big adv in Java...But You shud be careful though for computational intensive programmes....cuz Automatic Garbage collection is an art and not a science......GC algos are still very intensely researched | ||
| Der_schuler Junior Artist Username: Der_schuler Post Number: 818 Registered: 01-2009 Posted From: 99.140.160.102 Rating: N/A |
Ledhu andhi...Ex" IAM unte it will send "AM"....coz substring pointer starts at the first char and traverses till the end.....so first char is not inluded | ||
| Mallik Side Hero Username: Mallik Post Number: 4455 Registered: 10-2008 Posted From: 162.116.29.69 Rating: N/A |
I still dont understand where its reversing.. substring(1, arg.length) ante mallee adhe string ni amputundi gaa XXXS function ki? Who mama.. Psychogaallaki dooram gaa undu.. In this db, there's always someone watching you!! | ||
| Wrathchild Side Hero Username: Wrathchild Post Number: 2757 Registered: 03-2009 Posted From: 69.136.169.198 Rating: N/A |
naa very first prog in c lo malloc chesi free cheyyaledu..my mgr used to be fundoo guy in c..he gave a good analogy..C is like knife..u can cut an apple with it..cut ur hand as well | ||
| Simba Junior Artist Username: Simba Post Number: 277 Registered: 02-2008 Posted From: 24.228.73.121 Rating: N/A |
I did not use the word "Dynamic". It is a simple algo. to build tree on given set of data. Once the tree is built, a left->right traversal outputs sorted data. Everyone knows the simple traversal logic but writes unnecessary/complex logic to build the tree (which I was talking about). | ||
| Der_schuler Junior Artist Username: Der_schuler Post Number: 817 Registered: 01-2009 Posted From: 99.140.160.102 Rating: N/A |
Then I started coming to peace with that abstraction and started enjoying discrete math....especially I had to read through Operating Systems..tanenbaum and Henessey and patterson Quantitative Comp Arch for 6 months before I had sound grasps on the Von Neumann structure. | ||
| Der_schuler Junior Artist Username: Der_schuler Post Number: 816 Registered: 01-2009 Posted From: 99.140.160.102 Rating: N/A |
nenu non comp sci background....aero...but UG I hated my C course........appatlo naa mind antha...... What happens behind every key press.....What transistors get fired...how the assembly logic manifest itself at the lowest level ila alochinche vadni..... It took me 4 years of struggle to completely understand teh Von Nuemann model of computation and come to terms with the abstraction of a programming lang... | ||
| Simba Junior Artist Username: Simba Post Number: 276 Registered: 02-2008 Posted From: 24.228.73.121 Rating: N/A |
I agree totally. Nowadays, nobody bothers to learn the algorithms, just use a library to do the stuff. Unfortunately, coding the business logic looks worse where they can not use system libraries. To top that, it takes 2 minutes to google for a solution, so one does not toll the brain. | ||
| Der_schuler Junior Artist Username: Der_schuler Post Number: 815 Registered: 01-2009 Posted From: 99.140.160.102 Rating: N/A |
Right finding if a node exists or not in linked list is Log(n) and then one pass through is the min cost of data traversal....But mee statement lo Dynamic stream ante ardham kaala....I thought....may be U have an array A[] whose length and constituents change as a function change with time.....So real time data classification ante......2 much problem laaga anipinchindhi | ||
| Der_schuler Junior Artist Username: Der_schuler Post Number: 814 Registered: 01-2009 Posted From: 99.140.160.102 Rating: N/A |
But they are more fun!!!! Actually kindha ichina code has one subtle advantage....which is the crux of the Question...... IT HAS INTRINSIC PARALLELISM....in it.......One need not worry abt locks etc | ||
| Simba Junior Artist Username: Simba Post Number: 275 Registered: 02-2008 Posted From: 24.228.73.121 Rating: N/A |
Implementation depends on the programming language. In C, we just use linked list on structs. It takes one pass(n) on the input and costs log(n) to find the node to insert. Effectively making n + log(n) complexity. | ||
| Wrathchild Side Hero Username: Wrathchild Post Number: 2756 Registered: 03-2009 Posted From: 69.136.169.198 Rating: N/A |
java vacchaka progs life kasta happy ayyindi.. c lo linked lists talchukuntene kritam janma lo jeevitam anipistundi ippudu | ||
| Der_schuler Junior Artist Username: Der_schuler Post Number: 813 Registered: 01-2009 Posted From: 99.140.160.102 Rating: N/A |
tree traversals are one of the most fascinating problems I have ever seen...ilanti vaati meedha konchem study chesinappude anipistundhi...theoretical comp sci chesthe bavundedi ani | ||
| Der_schuler Junior Artist Username: Der_schuler Post Number: 812 Registered: 01-2009 Posted From: 99.140.160.102 Rating: N/A |
Input stream ante...dynamic array data meedha tree classification ah???? Hmm......Scaling should be similar to that of a static data array...but speed might suffer kadha..... So do u create pre defined buffers to append to the original data object or complete real time?? | ||
| Wrathchild Side Hero Username: Wrathchild Post Number: 2755 Registered: 03-2009 Posted From: 69.136.169.198 Rating: N/A |
lol | ||
| Bmw007 Comedian Username: Bmw007 Post Number: 1205 Registered: 10-2008 Posted From: 216.113.168.128 Rating: N/A |
  Jai Telugudesam Jai Jai Telugudesam | ||
| Der_schuler Junior Artist Username: Der_schuler Post Number: 811 Registered: 01-2009 Posted From: 99.140.160.102 Rating: N/A |
yup sorry andi | ||
| Der_schuler Junior Artist Username: Der_schuler Post Number: 810 Registered: 01-2009 Posted From: 99.140.160.102 Rating: N/A |
Simba, chaala mandhi annanu....srry if it came as generalization | ||
| One Side Hero Username: One Post Number: 9962 Registered: 09-2008 Posted From: 72.190.28.18 Rating: N/A |
plz remove desi .....konta mandi vunaru......2 weeks back oka kotha kurodi maa group lo join ayyadu......vadi code chusi nenu shock....vadi 200 lines code rasadu .....nenu code review lo dani 5 lines thagicha  ....Jai TDP | ||
| Simba Junior Artist Username: Simba Post Number: 274 Registered: 02-2008 Posted From: 24.228.73.121 Rating: N/A |
Maree ala generalize cheyyakoodandi... Maa class lo janalu katthi lanti algorithms raase vaalu. My fav one is building a binary tree from input stream data using recursion. | ||
| Der_schuler Junior Artist Username: Der_schuler Post Number: 809 Registered: 01-2009 Posted From: 99.140.160.102 Rating: N/A |
Simba cheppindhi right. Sarigga choodandi.... Simba, the intent was to show how imperative structured lang like C,Java etc are actually not the best form of expressing a problem. Chaala mandhi desi programmers can't write code recursively which surprises me. I have seen people building bulky code to accomplish this. This sort of code is a tester's paradise. assume how easy is it for unit testing. | ||
| Simba Junior Artist Username: Simba Post Number: 273 Registered: 02-2008 Posted From: 24.228.73.121 Rating: N/A |
First look lo ala ne anipinchindi. Inko saari chooste samaj ayyindi: XXXS(arg.substring(1, arg.length)) + arg.substring(0, 1); | ||
| Whoami Side Hero Username: Whoami Post Number: 5362 Registered: 10-2008 Posted From: 68.40.67.41 Rating: N/A |
http://www.chalanachithram.com/cgi-bin/discus/show.cgi?tpc=1 25&post=811662#POST811662 | ||
| Mallik Side Hero Username: Mallik Post Number: 4454 Registered: 10-2008 Posted From: 162.116.29.69 Rating: N/A |
Simba mav.. reverse ekkada chestundi ?? In this db, there's always someone watching you!! | ||
| Mallik Side Hero Username: Mallik Post Number: 4453 Registered: 10-2008 Posted From: 162.116.29.69 Rating: N/A |
Infinite loop lo padutundi kadaa.. In this db, there's always someone watching you!! | ||
| Simba Junior Artist Username: Simba Post Number: 272 Registered: 02-2008 Posted From: 24.228.73.121 Rating: N/A |
It uses recursion to print the argument in reverse. XXXS("ABCDE") return "EDCBA" Probably, suitable for first year comp sci students. | ||
| Der_schuler Junior Artist Username: Der_schuler Post Number: 808 Registered: 01-2009 Posted From: 99.140.160.102 Rating: N/A |
ee question set chesthunnamu....first year comp sci students ki....do u think its fair or not | ||
| Der_schuler Junior Artist Username: Der_schuler Post Number: 807 Registered: 01-2009 Posted From: 99.140.160.102 Rating: |
Try understanding what does this code do: String XXXS(String arg) { if(arg.length == 0) { return arg; } else { return XXXS(arg.substring(1, arg.length)) + arg.substring(0, 1); } } where substring(a,b) gives the substring starting at the a'th character and ending with the b'th character. |
