[IRC LOGS] Fibonacci and recursion with thewormkill.

[Phage]

2015-11-22 21:49:00   thewormkill   lets go
2015-11-22 21:49:10   thewormkill   fibbonacci numbers are a so-called sequence
2015-11-22 21:49:28   @phil   I will stay silent and only break in if I get lost, ok?
2015-11-22 21:49:31   thewormkill   which is just a function f: N -> A where N are the natural numbers 1,2,3,4....
2015-11-22 21:49:36   thewormkill   okay, phil
2015-11-22 21:49:51   thewormkill   so we basically map one element of A to every element of N
2015-11-22 21:49:56   thewormkill   that's a function
2015-11-22 21:50:13   thewormkill   in this case, it is also a sequence, because we map from the natural numbers
2015-11-22 21:50:30   thewormkill   now, A = N because all fibbonacci numbers are natural numbers
2015-11-22 21:50:36   thewormkill   so: f: N -> N
2015-11-22 21:51:05   thewormkill   now, you need a way to find appropriate elemnents
2015-11-22 21:51:18   thewormkill   so we define: f_1 = 1, f_2 = 1
2015-11-22 21:51:27   thewormkill   those are our first two elements
2015-11-22 21:51:33   thewormkill   lol
2015-11-22 21:51:43   thewormkill   please no chitchat
2015-11-22 21:51:49   @phil   ^
2015-11-22 21:52:00   thewormkill   so, phil, so far everything clear?
2015-11-22 21:52:14   @phil   I think so, yeah
2015-11-22 21:52:15   thewormkill   now we define f_n = f_(n-1) + f_(n+)
2015-11-22 21:52:19   thewormkill   now we define f_n = f_(n-1) + f_(n+2)
2015-11-22 21:52:28   thewormkill   so n >= 3
2015-11-22 21:52:36   thewormkill   because we defined f_1 and f_2 already
2015-11-22 21:52:47   thewormkill   now let's get to code, okay?
2015-11-22 21:53:05   @phil   Wait
2015-11-22 21:53:08   thewormkill   we will apply the recursive definition in a straightforward and dumb manner
2015-11-22 21:53:14   @phil   I thought it was f_(n-2) ?
2015-11-22 21:53:14   thewormkill   yeah, questions?
2015-11-22 21:53:22   thewormkill   sorry, typo
2015-11-22 21:53:26   @phil   Ah, okay
2015-11-22 21:53:29   @phil   Then proceed
2015-11-22 21:54:02   thewormkill   now, let's look at a python function, since I don't really know ruby
2015-11-22 21:54:10   thewormkill   def fib(n):
2015-11-22 21:54:25   thewormkill       if n == 1 or n == 2:
2015-11-22 21:54:33   thewormkill           return 1
2015-11-22 21:54:41   thewormkill       else:
2015-11-22 21:54:54   thewormkill           return fib(n-1) + fib(n-2)
2015-11-22 21:54:56   thewormkill   done
2015-11-22 21:55:12   thewormkill   phil: you see a direct correspondence between the code above and the deefinition
2015-11-22 21:55:16   @phil   I do now
2015-11-22 21:55:19   thewormkill   okay
2015-11-22 21:55:20   @phil   thanks
2015-11-22 21:55:24   thewormkill   the problem there is,
2015-11-22 21:55:28   @phil   Recursiveness has always been a mind-game to me
2015-11-22 21:55:29   thewormkill   it is not efficient
2015-11-22 21:55:35   thewormkill   it is slow af
2015-11-22 21:55:44   thewormkill   because we call fib() an enormous amount of time
2015-11-22 21:56:01   thewormkill   thus, the code you showed uses generators
2015-11-22 21:56:11   thewormkill   that was very brief, phil
2015-11-22 21:56:18   thewormkill   any more questions/wishes?
2015-11-22 21:57:03   @phil   Yeah, one
2015-11-22 21:57:04   @phil   4613732
2015-11-22 21:57:05   @phil   -.-
2015-11-22 21:57:18   @phil   a, b = b, a+b
2015-11-22 21:57:41   @phil   Care to explain how that works?
2015-11-22 21:57:45   thewormkill   sure
2015-11-22 21:57:59   thewormkill   you say that a and b are fib numbers already
2015-11-22 21:58:15   thewormkill   and they are adjacent
2015-11-22 21:58:29   thewormkill   so f^(-1)(b)-f^(-1)(b) = 1
2015-11-22 21:58:49   thewormkill   where f^(-1) maps from fibonacci numbers to their indices
2015-11-22 21:59:03   thewormkill   so the inverse of f
2015-11-22 21:59:15   thewormkill   now, if you want to have the next (so to say thrird) number, you add a + b
2015-11-22 21:59:39   @phil   Okay, you lost me compltely xD
2015-11-22 21:59:43   thewormkill   and to get the fourth, you add the 2nd (b) and that result...
2015-11-22 21:59:49   thewormkill   okay, where?
2015-11-22 22:00:12   @phil   "and they are adjacent"
2015-11-22 22:00:17   @phil   Adjacent numbers?
2015-11-22 22:00:22   thewormkill   no
2015-11-22 22:00:29   thewormkill   adjacent fibonaci numbers
2015-11-22 22:00:45   @phil   What do you mean by adjacent?
2015-11-22 22:00:47   thewormkill   the second and thrid fib number or the 7th and 8th... etc
2015-11-22 22:00:49   @phil   In the term of numbers?
2015-11-22 22:00:54   @phil   oh
2015-11-22 22:01:05   thewormkill   yeah, adjacent in the sequence
2015-11-22 22:01:11   @phil   I see
2015-11-22 22:01:19   @phil   f^(-1)(b)-f^(-1)(b) = 1
2015-11-22 22:01:53   @phil   ?
2015-11-22 22:02:01   thewormkill   yes, that is just a formal way of expressing the above
2015-11-22 22:02:12   thewormkill   we said that f maps from indices to fibonacci numbers
2015-11-22 22:02:25   thewormkill   f^(-1) maps from fibonacci numbers to their indices
2015-11-22 22:02:39   @phil   You're gonna have a hard time here  "maps from indices" ?
2015-11-22 22:03:19   thewormkill   okay, a function takes a parameter, right?
2015-11-22 22:03:34   @phil   yeah
2015-11-22 22:03:42   thewormkill   now, it returns a result
2015-11-22 22:03:49   @phil   yeah
2015-11-22 22:04:02   thewormkill   "mapping" is the process of giving a result for an input
2015-11-22 22:04:05   thewormkill   just a word
2015-11-22 22:04:14   thewormkill   it's like a dictionary
2015-11-22 22:04:16   <--   lenoch (~lenoch@over.the.edge) has left #fib (Leaving)
2015-11-22 22:04:18   thewormkill   as in python
2015-11-22 22:04:30   @phil   Oh
2015-11-22 22:04:42   thewormkill   d = {1:1,2:1,3:d[1]+d[2],...}
2015-11-22 22:04:50   thewormkill   see?
2015-11-22 22:05:10   @phil   I think so yeah...
2015-11-22 22:05:17   thewormkill   good
2015-11-22 22:05:28   thewormkill   now you got the second part I assume?
2015-11-22 22:05:36   thewormkill   can you guess why it is doen that way?
2015-11-22 22:07:16   thewormkill   phil: ^
2015-11-22 22:07:20   @phil   Yeah, no
2015-11-22 22:07:36   thewormkill   think abot recursion
2015-11-22 22:07:41   thewormkill   why do people fear it?
2015-11-22 22:08:04   @phil   No clue? I just find it weird that something can return the result of itself.
2015-11-22 22:10:19   thewormkill   that's not at all weird, but it seems to be to many
2015-11-22 22:10:26   thewormkill   but more importantly, it has a cost
2015-11-22 22:10:32   thewormkill   which cost you ask?
2015-11-22 22:10:40   @phil   I do
2015-11-22 22:10:44   thewormkill   well, do you know how function calls are organized?
2015-11-22 22:10:50   @phil   Not really?
2015-11-22 22:10:57   thewormkill   okay, you have a stack
2015-11-22 22:11:04   thewormkill   you know what that means?
2015-11-22 22:11:06   @phil   I do
2015-11-22 22:11:09   thewormkill   okay,
2015-11-22 22:11:19   thewormkill   this means that every function call sets up a new stackframe
2015-11-22 22:11:27   thewormkill   clear so far?
2015-11-22 22:11:30   @phil   Yup
2015-11-22 22:11:38   thewormkill   okay
2015-11-22 22:11:42   @phil   Oh, so you had a hell of a lot stackframes to the stack
2015-11-22 22:11:43   thewormkill   well, that takes memory
2015-11-22 22:11:46   thewormkill   yes
2015-11-22 22:11:46   @phil   meaning, longer execution time?
2015-11-22 22:11:53   thewormkill   no more memory usage
2015-11-22 22:11:57   @phil   Fair
2015-11-22 22:11:58   thewormkill   *no, more...
2015-11-22 22:11:59   @phil   I'm with ya
2015-11-22 22:12:11   thewormkill   yes and that's bad if you want the 20000000th fib number
2015-11-22 22:12:21   thewormkill   because you'll run out of memory
2015-11-22 22:12:25   @phil   That's obvious now, lol.
2015-11-22 22:12:36   thewormkill   so imperative programmers prefer loops and other controlflow
2015-11-22 22:12:50   thewormkill   wanna know how FP handles that where we have no loops?
2015-11-22 22:13:01   @phil   Sure, can't hurt
2015-11-22 22:13:35   thewormkill   okay, we don't have loops, so we have recursion everywhere
2015-11-22 22:13:41   thewormkill   how do we handle memory?
2015-11-22 22:13:46   @phil   I was just about to ask :p
2015-11-22 22:13:50   thewormkill   well, we don't have a callstack (sick)
2015-11-22 22:13:54   @phil   lol
2015-11-22 22:14:01   thewormkill   at least haskell hasn't
2015-11-22 22:14:14   thewormkill   this means, you have an entirely different concept
2015-11-22 22:14:23   thewormkill   haskell is lazily-evaluated
2015-11-22 22:14:38   thewormkill   so if you compute the result of a function you only do that when it is needed
2015-11-22 22:15:06   thewormkill   so you store a so-called thunk, which is basically a promise that the value will be there when asked for
2015-11-22 22:15:22   thewormkill   and have a whole load of thunks referencing each other
2015-11-22 22:15:59   thewormkill   if you want to compute the nth fib number you might get problems as well, but you can reorganize your code heavily to have less thunks by computing differently
2015-11-22 22:16:10   thewormkill   OR you can just make some parts of your program strict
2015-11-22 22:17:15   thewormkill   phil: clear so far?
2015-11-22 22:17:36   @phil   Strict?
2015-11-22 22:17:47   thewormkill   yes, as in not lazy
2015-11-22 22:18:07   @phil   So, it calculates it right away, or?
2015-11-22 22:18:14   thewormkill   if you want it to
2015-11-22 22:18:28   thewormkill   by default it does not, but you can force evaluation so to say
2015-11-22 22:18:45   @phil   Ah, that's neat
2015-11-22 22:18:54   thewormkill   yes
2015-11-22 22:19:00   thewormkill   now go the forums and post this log pls
2015-11-22 22:20:35   @phil   I'm still not one hundred percent sure how that; a,b = b, a+b thing works? :/
2015-11-22 22:20:54   thewormkill   it's mostly syntactic sugar
2015-11-22 22:21:04   thewormkill   you just calculate values based on a and b
2015-11-22 22:21:16   thewormkill   and then you assign them to a and b respectively
2015-11-22 22:21:48   thewormkill   in the recursive version we just had different a's and b's for each level of recursion so to say
2015-11-22 22:21:57   thewormkill   (those were our intermediate results)
2015-11-22 22:22:18   thewormkill   now, we just made the algorithm iterative
2015-11-22 22:22:20   thewormkill   and it works in-place
2015-11-22 22:22:39   thewormkill   phil: that's all there is to it, really
2015-11-22 22:22:59   @phil   So, instead of calling the function x times and having it do the calculation x times per function call
2015-11-22 22:23:13   @phil   you call it once, and it iterates over the numbers until it hit the result?
2015-11-22 22:23:18   thewormkill   yes

[rincewind]

Oh, cool, I have to get on IRC, I miss all the fun
Anyhow here is a good video series about recursion, might help you understand it even better
https://www.youtube.com/watch?v=_OmRGjbyzno&list=PL2_aWCzGMAwLz3g66WrxFGSXvSsvyfzCO

[kenjoe41]

This is better appreciated with a background in algorithm designs, else just take my word for it and do it everytime.

Might i say, if you are going to use recursion in production or even just a good practice for everytime you use recursion and can spare afew more lines of code, always do memoization. This is the caching of previous calculated results to reduce the number of fuction calls made. From exponential calls to linear calls. Don't remember my Nlog math but you will get it.

While you are at it, do try out dynamic programming, might be a better solution to some recursion problems sometimes.

Read up: http://rayhightower.com/blog/2014/04/12/recursion-and-memoization/

[TheWormKill]

This is better appreciated with a background in algorithm designs, else just take my word for it and do it everytime.

Might i say, if you are going to use recursion in production or even just a good practice for everytime you use recursion and can spare afew more lines of code, always do memoization. This is the caching of previous calculated results to reduce the number of fuction calls made. From exponential calls to linear calls. Don't remember my Nlog math but you will get it.

While you are at it, do try out dynamic programming, might be a better solution to some recursion problems sometimes.

Read up: http://rayhightower.com/blog/2014/04/12/recursion-and-memoization/

While all of this is true, you should keep your recursing functions referentially transparent, meaning that they only return a result based on the arguments and no other input such as PRNGs as well as perform no I/O etc. Otherwise you'd manipulate the global state of the program in a significantly different fashion.
Thus, checking out Haskell if you find this topic of memoization, recursion, referential transparency etc. inhteresting is definitely worth a shot (or two).