** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** - Page 140 - Computer Technical Help

Two Plus Two Forums Other Topics Computer and Technical Help

** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Post Reply Subscribe

...

Page 140 of 1603

First

40 90 120 130 135 136 137 138 139 140 141 142 143 144 145 150 160 190 240 340 640 1140

Last

Page 140 of 1603

First

40 90 120 130 135 136 137 138 139 140 141 142 143 144 145 150 160 190 240 340 640 1140

Last

04-22-2012 , 04:20 PM

#3476

gaming_mouse

Carpal \'Tunnel

Join Date: Oct 2004 Posts: 13,786

Quote:

Originally Posted by kts82

like the fibonnaci algorithm, if u implement it with a recursive algorithm its way slower than with loops

not true (see my last post) -- you can still use a recursive function, it just needs to give rise to an iterative process.

Last edited by gaming_mouse; 04-22-2012 at 04:25 PM. Reason: edited for clarity

Quote

$25m Guaranteed WPM on CoinPoker

Join the action now

Daily Rewards • Splash Pots • CoinRaces

04-22-2012 , 04:39 PM

#3477

Xhad

Carpal \'Tunnel

Join Date: Jul 2005 Posts: 10,962

I do stuff like this in Project Euler problems all the time:

Code:

def fib(n, cache={0: 0, 1: 1}):
    if n not in cache:
        cache[n] = fib(n-2) + fib(n-1)
    return cache[n]

Quote

04-22-2012 , 04:56 PM

#3478

NoahSD

Is Right

Join Date: Aug 2005 Posts: 18,843

Quote:

Originally Posted by gaming_mouse

this is closer to the for loop you wrote, but there is an iterative version of the recursive function which has three arguments (last two fib numbers, and a counter which acts as your stopping point) -- i think that would be closest of all to the natural explanation.

Hmm.. yeah. That might be the best way to code the fib sequence if you want someone who doesn't know anything about programming to understand it.

I was more interested in the general question of whether there's a computation in which pure recursion is more intuitive than iteration, though (leaving the definition of "intuitive" open to interpretation).

Quote

04-22-2012 , 05:00 PM

#3479

kts82

grinder

Join Date: Nov 2010 Posts: 452

Quote:

Originally Posted by gaming_mouse

not true (see my last post) -- you can still use a recursive function, it just needs to give rise to an iterative process.

ah ok, but that is recursion with tricks

, like the Xhad code above ^^

Quote

04-22-2012 , 05:08 PM

#3480

tyler_cracker

Carpal \'Tunnel

Join Date: Apr 2005 Posts: 15,828

Quote:

Originally Posted by gaming_mouse

guess it wasn't clear, but that alligator game wasn't meant to teach recursion. it's meant to teach lambda calculus, arguably much more complex -- it was just a cool thing i remembered on the subject of teaching kids advanced concepts.

yeah i saw that it was for lambda calculus. i guess kids (or i) could use that to *do* lambda calculus but that's not the same as understanding what's going on.

Quote:

alan kay does a lot of innovative computer teaching with kids -- i wonder if he's done something with recursion.

i'm trying to think of an application for recursion in logo but i can't think of one that doesn't involve fractals.

Quote:

Originally Posted by NoahSD

Is recursion more intuitive for something like the fibonacci numbers that we naturally define inductively?

not for me, no. i think it's much easier to reason fibonacci forward: start with 1 and 1, then keep adding the last two until you've done enough. i think it's more difficult to reason it backward: i want the 8th fibonacci number, so i add the 7th and the 6th. but lo! i don't know those yet, so to get the 7th i add the 6th and the 5th...

(or basically what g_m said:

Quote:

if you had to explain the fib numbers to a total non-mathemetician, you would do constructively, i think, writing out 1, 1 ("now you just add these and write down the answer") 2, ("now you add the new one and the last one"), etc...

)

Quote:

Originally Posted by Ryanb9

Any time when someone will say this? "This problem can be solved with recursion but not loops." or "This problem is better solved with recursion than loops." Because I always use loops maybe I should use both?

"can be solved" is pretty broad, so no bet there -- it's possible to shoehorn ~any problem into a recursive algorithm or an iterative algorithm. heh, fractals might be an exception.

"better solved", definitely. certain problems, like tree traversal[1], are easier to think about with recursion while other problems, like i/o[2], are easier to think about with iteration.

practically speaking, i'd guess that most coders working on run-of-the-mill webapps and buisness logic and system administration software will encounter a keen need for recursion rarely or never. the tools you use will be using it under the hood (see my examples below) but code monkey don't care.

the trouble is, if you need recursion and don't figure that out and know how to use it, you're generally ****ed.

[1] e.g. "tell me the names of all the files on this file system"

[2] e.g. "take this file and give me all the lines that contain the word 'balls'"

Quote:

Originally Posted by Burnss

is it better to do recursion or loops? I assume loops are quicker at runtime?

i'll defer to someone with a deeper understanding of algorithms but *in general* i'd say:

a) algorithmic complexity will be the same

b) recursion takes more memory because of all the stuff shoved onto the call stack

c) for that great unwashed mass of hackers in the world, the readability of the code and understandability of the algorithm trumps any benefit we might get from telling our stratosphere-high-level languages to do something as an "optimization".

Quote

04-22-2012 , 05:09 PM

#3481

tyler_cracker

Carpal \'Tunnel

Join Date: Apr 2005 Posts: 15,828

tl;dr

THE_BIBLE = http://mitpress.mit.edu/sicp/full-te...ml#%_sec_1.2.1

s/$MY_POST/$THE_BIBLE/

Last edited by tyler_cracker; 04-22-2012 at 05:14 PM. Reason: not an easy read but if you really want to learn computer science, start by worshipping at the altar of SICP. imo.

Quote

04-22-2012 , 05:12 PM

#3482

tyler_cracker

Carpal \'Tunnel

Join Date: Apr 2005 Posts: 15,828

Quote:

Originally Posted by kts82

ah ok, but that is recursion with tricks

, like the Xhad code above ^^

the trick (memoization!) doesn't change the basic nature of the algorithm.

Quote:

Originally Posted by Xhad

I do stuff like this in Project Euler problems all the time

so write a library already!

from xhad import fib

Last edited by tyler_cracker; 04-22-2012 at 05:13 PM. Reason: trying to decide if passing in cache when calling fib(n-k) is desirable and/or if python scoping weirdness fixes that

Quote

04-22-2012 , 05:15 PM

#3483

clowntable

Carpal \'Tunnel

Join Date: Jun 2006 Posts: 45,557

Well it's a little unfair because the language I'll use only really has recursion but I think this snippet of Prolog code is a very intuitive usecase of recursion:

Code:

ancestor(A, B) :- parent(A, B).
ancestor(A, B) :- parent(A, X), ancestor(X, B).

Same for handling lists with the [Head|Tail] construct.

Edit: For people no familiar with Prolog the two lines are "or connected"

Quote

04-22-2012 , 05:19 PM

#3484

gaming_mouse

Carpal \'Tunnel

Join Date: Oct 2004 Posts: 13,786

Quote:

Originally Posted by NoahSD

I was more interested in the general question of whether there's a computation in which pure recursion is more intuitive than iteration, though (leaving the definition of "intuitive" open to interpretation).

yeah it's a good question. certainly pure recursive solutions are more compact and easier to write down for many problems.

but computationally, i think pure recursion is always more complex, simply because you have to keep deferring calculation, remembering what you are waiting on, and then going back and filling it all in once you reach the root case.

i'd think: more intuitive for descriptive purposes, less intuitive for implementation.

Quote

04-22-2012 , 05:20 PM

#3485

tyler_cracker

Carpal \'Tunnel

Join Date: Apr 2005 Posts: 15,828

clown,

when one day we meet irl i'm going to be so confused when you are not a blowfish.

lol "very intuitive". i don't know any prolog so idcwudt. are you declaring a data structure? some of that invariant **** those haskell people talk about?

do you mean doubly-linked lists?

Quote

04-22-2012 , 05:24 PM

#3486

gaming_mouse

Carpal \'Tunnel

Join Date: Oct 2004 Posts: 13,786

Quote:

Originally Posted by tyler_cracker

tl;dr

THE_BIBLE = http://mitpress.mit.edu/sicp/full-te...ml#%_sec_1.2.1

s/$MY_POST/$THE_BIBLE/

exactly what i was thinking of when i wrote my reply to kts above

Quote

04-22-2012 , 05:24 PM

#3487

kerowo

lolcat

Join Date: Nov 2005 Posts: 37,183

How long has recursion been a viable, everyday option? I seem to remember we didn't spend much time on it becauses loops were faster, smaller, better. It was a long time ago though so I may be confused. Recursion is like time travel stories, so the more of those you've dealt with, the easier recursion is.

Quote

04-22-2012 , 05:30 PM

#3488

Wraths Unanimous

Carpal \'Tunnel

Join Date: Sep 2007 Posts: 8,575

Anyone use this RoR tutorial to teach themselves: http://ruby.railstutorial.org/ruby-o...tutorial-book?

Thoughts/comments on it? Summer vacation is here and I'd like to teach myself RoR in those 2.5 months I get.

Quote

04-22-2012 , 05:31 PM

#3489

daveT

S.A.G.E. Master

Join Date: Jun 2005 Posts: 23,955

Quote:

Originally Posted by Ryanb9

Code:

def palindrome(myString):
    print(myString)
    if len(myString) == 0 or len(myString) == 1:
        return True
    elif myString[0] == myString[-1]:
        return palindrome(myString[1:-1])
    else: return False

output:

Code:

>>> palindrome('1234567890987654321')
1234567890987654321
23456789098765432
345678909876543
4567890987654
56789098765
678909876
7890987
89098
909
0
True

Good luck with the iterative version.

Quote

04-22-2012 , 05:35 PM

#3490

daveT

S.A.G.E. Master

Join Date: Jun 2005 Posts: 23,955

Quote:

Originally Posted by tyler_cracker

tl;dr

THE_BIBLE = http://mitpress.mit.edu/sicp/full-te...ml#%_sec_1.2.1

s/$MY_POST/$THE_BIBLE/

I was about to copy/paste the entire section on fib, recursive fib, and fast-fib, but I guess you beat me to it.

Quick Brag: I finally made it to chapter 3!

All hail the Lambda!

Quote

04-22-2012 , 05:44 PM

#3491

gaming_mouse

Carpal \'Tunnel

Join Date: Oct 2004 Posts: 13,786

Quote:

Originally Posted by daveT

Good luck with the iterative version.

pretty trivial actually:

Code:

def palindrome str
  len = str.length
  return true if len <= 1
  (0..(len/2)-1).each do |i|
    return false if str[i] != str[len-i-1]
  end
  true
end

input = '1234567890987654321'

puts palindrome input

Quote

04-22-2012 , 05:44 PM

#3492

clowntable

Carpal \'Tunnel

Join Date: Jun 2006 Posts: 45,557

Quote:

Originally Posted by tyler_cracker

Lists in Prolog are just a one element Head followed by a Tail of size n so you can always mentally cut off the Head and look at the remaining Tail which is pretty nice for recursion. If the Tail is the empty list you have reached "the end".

Prolog is basically some sort of pattern matching applied to a database (yeah I guess that's not accurate) so the code I posted pretty much says...
A is an ancestor of B if A is a parent of B ... OR
A is an ancestor of B if A is a parent of X AND X is an ancestor of B

Then your database would have stuff like parent('Joe','Jane') aka facts.

Quote

04-22-2012 , 05:58 PM

#3493

NoahSD

Is Right

Join Date: Aug 2005 Posts: 18,843

Quote:

Originally Posted by gaming_mouse

but computationally, i think pure recursion is always more complex, simply because you have to keep deferring calculation, remembering what you are waiting on, and then going back and filling it all in once you reach the root case.

Yeah. I think that some functional languages might have compilers that find ways around this problem, though.

Quote

04-22-2012 , 06:13 PM

#3494

gaming_mouse

Carpal \'Tunnel

Join Date: Oct 2004 Posts: 13,786

Quote:

Originally Posted by NoahSD

Yeah. I think that some functional languages might have compilers that find ways around this problem, though.

this is something i've wondered about. i remember being really disappointed when i found out that you couldn't write a fast quicksort (without hackery that defeats the purpose) in haskell, even though you can write an elegant and beautiful one:

http://c2.com/cgi/wiki?QuickSortInHaskell

Quote

04-22-2012 , 06:14 PM

#3495

clowntable

Carpal \'Tunnel

Join Date: Jun 2006 Posts: 45,557

It's usually good enough to make sure your stuff is tail-recursive to keep the stacks from pwning you. If I need more optimization than that...it's not stuff I should be coding and I'll outsource :P

Also it certainly takes me a bit to get into "thinking in recursion" mode. My brain is just drilled to be iterating over stuff I guess. That's why I think I need to do more recursion just to get a better feel for it.

Quote

04-22-2012 , 06:23 PM

#3496

NoahSD

Is Right

Join Date: Aug 2005 Posts: 18,843

Wait a minute. Is there anyone who, ignoring speed/memory concerns, would prefer coding the fibonacci numbers iteratively?

BTW.. just because why not, the fibonacci numbers actually have a closed form expression, so if you do care about speed, you can just use the closed form to compute it, which only requires raising a constant floating point to the nth power and rounding. (i.e. log(n) floating point multiplications instead of n integer sums). http://en.wikipedia.org/wiki/Fibonac...orm_expression I think there might be some even faster methods as well.

Last edited by NoahSD; 04-22-2012 at 06:35 PM.

Quote

04-22-2012 , 06:25 PM

#3497

NoahSD

Is Right

Join Date: Aug 2005 Posts: 18,843

Quote:

Originally Posted by gaming_mouse

Oh, wow, that's depressing.

Facts like that make me glad I'm a theorist and don't plan on writing too much practical code in my life.

Quote

04-22-2012 , 06:56 PM

#3498

Neko

Pooh-Bah

Join Date: Jul 2005 Posts: 4,000

Quote:

Reason: trying to decide if passing in cache when calling fib(n-k) is desirable and/or if python scoping weirdness fixes that

It's more common to use a memoization decorator so that the caching and functionality are separated. I'd prefer not to have the caching mixed in with the function logic.

Code:

class Memoize:
    """Memoize(fn) - an instance which acts like fn but memoizes its arguments
       Will only work on functions with non-mutable arguments
    """
    def __init__(self, fn):
        self.fn = fn
        self.memo = {}
    def __call__(self, *args):
        if not self.memo.has_key(args):
            self.memo[args] = self.fn(*args)
        return self.memo[args]
    
def facr(n):
    if n == 1:
        return 1
    else:
        return n*facr(n-1)
    
facr = Memoize(facr)

print facr(3)

Quote

04-22-2012 , 07:08 PM

#3499

gaming_mouse

Carpal \'Tunnel

Join Date: Oct 2004 Posts: 13,786

v nice point, neko

Quote

04-22-2012 , 07:17 PM

#3500

Neko

Pooh-Bah

Join Date: Jul 2005 Posts: 4,000

that Memo class is just something I pulled from the first link I saw..I'm not sure why they use a class instead of a function:

Code:

def memo(f):
    cache = {}
    def wrapper(*args):
        if not cache.has_key(args):
            cache[args] = f(*args)
        return cache[args]
    return wrapper

def facr(n):
    if n == 1:
        return 1
    else:
        return n*facr(n-1)
    
facr = memo(facr)