Open Side Menu Go to the Top

04-22-2012 , 04:20 PM
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
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **
$25m Guaranteed WPM on CoinPoker
Join the action now
Daily Rewards • Splash Pots • CoinRaces
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **
04-22-2012 , 04:39 PM
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]
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
04-22-2012 , 04:56 PM
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).
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
04-22-2012 , 05:00 PM
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 ^^
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
04-22-2012 , 05:08 PM
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".
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
04-22-2012 , 05:09 PM
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.
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
04-22-2012 , 05:12 PM
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
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
04-22-2012 , 05:15 PM
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"
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
04-22-2012 , 05:19 PM
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.
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
04-22-2012 , 05:20 PM
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?
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
04-22-2012 , 05:24 PM
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
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
04-22-2012 , 05:24 PM
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.
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
04-22-2012 , 05:30 PM
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.
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
04-22-2012 , 05:31 PM
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?
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.
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
04-22-2012 , 05:35 PM
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!

** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
04-22-2012 , 05:44 PM
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
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
04-22-2012 , 05:44 PM
Quote:
Originally Posted by tyler_cracker
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?
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.
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
04-22-2012 , 05:58 PM
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.
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
04-22-2012 , 06:13 PM
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
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
04-22-2012 , 06:14 PM
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.
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
04-22-2012 , 06:23 PM
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.
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
04-22-2012 , 06:25 PM
Quote:
Originally Posted by gaming_mouse
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
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.
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
04-22-2012 , 06:56 PM
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)
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
04-22-2012 , 07:08 PM
v nice point, neko
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
04-22-2012 , 07:17 PM
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)
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **
$25m Guaranteed WPM on CoinPoker
Join the action now
Daily Rewards • Splash Pots • CoinRaces
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

      
m