Learning Clojure - Part 4 | Finding the nth Fiboncci number

in #clojure3 years ago

Learning Clojure.jpg
Today I revisited my goal of learning Clojure. If you're not familiar with Clojure, it's descibed by repl.it as

A modern JVM-based Lisp dialect with a focus on immutability

If that description didn't enlighten you, let's just agree that it's a programming language.

Having previously solved Project Euler Problem 1 in Clojure, I decided to give Problem 2 a shot as well.

Problem 2
Even Fibonacci numbers
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

This problem introduces a series of challenges, most notably, being able to find Fibonacci numbers, which this post will focus on.

Since I'm not yet very familiar with Clojure, I'm don't feel confident working iteratively on variables, so my first implementation of a function to find the nth Fibonacci number was a recursive one. Its design is pretty simple:
  • If you want to find the first Fibonacci number, the function returns 1.
  • If you want to find the second Fibonacci number, the function returns 2.
  • If you want to find any other Fibonacci number, the function returns the sum of the the return values from the same function called with an input value decremented with 1 and 2 respectively.
I implemented the function in Clojure like this:
;; Recursive fibonacci
(defn rfib [number]
  (if (= number 1)
    1 
    (if (= number 2)
      2
      (+ (rfib (- number 1)) (rfib (- number 2)))
    )
  )
)
(println (rfib 5)) ;; => 8

The problem with a recursive approach is that it's slow. REALLY SLOW. The online REPL I was using crashed when I tried to find the 20th Fibonacci number. What we would like is to repeatedly find the next number by adding the two previous numbers, without having to recalculate every previous number for every new number. This is where my lack of familiarity with Clojure becomes apparent.

I decided to start small, and solve the problem one step at a time. First, I would like to be able to add an element to a list, or an array, which I believe they're called in Clojure. It turns out that there is a function called conj. I think it means conjoine, whatever that means.
(println (conj [1 2 3] 4)) ;; => [1 2 3 4]

My goal here is to be able to repeatedly add an element to the end of an array, with the value being the sum of the array's last two elements. That means that I have to be able to get the value of the last element in an array. To do this, I use a function called last. I love it when functions are actually have descriptive names.
(println (last [1 2 3 4])) ;; => 4

Next, we need to be able to get the value of the second to last element of a list. To be able to do this, I first use a function called butlast, which returns the whole array except for the last element. Then I use the last function, which we're already familiar with.
(println (last (butlast [1 2 3 4]))) ;; => 3

Now, let's combine what we've learnt to make a function which extends an array with the sum of its last two elements:
(defn sum-end [vector] (conj vector (+ (last vector) (last (butlast vector)))))

(println (sum-end [1 2 3])) ;; => [1 2 3 5]

Now that we have this useful function to find the next Fibonacci number given an array of all the previous Fibonacci numbers, it shouldn't be too difficult to create a function which returns the nth Fibonacci number.

Or so I thought...

I got this far:
(defn fib [number]
  (def vector [1 2])
  (while (<= (count vector) number)
    (println vector)
    (let [vector (sum-end vector)]) ;; I'm not sure about this part.
  )
)

I'll ask a colleague at work tomorrow for some insight. Until then...
Sort:  

Next times do yourself a favor:
When you naively browse the blockchain use steemit.com while in night mode.
When you post a thread, busy.org/busy.pay will reward you generously if once a day you will post it through busy.org if you also tag it under the 'busy' tag while doing so. No need to use 'busy' as the first and main tag.
No need to post all your thread through it if you have a high volume, because it has a 12 hours, which I believe was revised to a 24 hours time limit between individualized rewards.
I also highly recommend buying votes through:
luckyvotes, proffit, upyourpost, steemdiffuser, lrd, lightnongbolt (still in recovery)
and to a lesser degree, but still, through sleeplesswhale.
If you are not interested in buying votes on comment, then lost-ninja, sneaky-ninja, pwrup, sunrawhale, bid4joy and to a lesser degree, but still, megabot, provide good services too.
Why not learn whichever one of the following languages that you still do not know: assembly, or C or C++ or some web or cellular phone language?

Well that was a lot of comment.
To the degree where I'm wondering if you're a bot.
But to answer your question, I already have experience with C (if I "know it" depends of course),
C++,
JavaScript (web language),
Java (cellular phone language, amongst others),
python, oz, matlab...
I haven't tried assembly, but I doubt I would use it even if I learnt it.

I decided to learn Clojure as it forces me to think more functionally, which I believe will make me a better programmer overall.

This comment has received a 100.00 % upvote from @steemdiffuser thanks to: @stimialiti.

Bids above 0.1 SBD may get additional upvotes from our trail members.

Get Upvotes, Join Our Trail, or Delegate Some SP

You got a 66.67% upvote from @sleeplesswhale courtesy of @stimialiti!

Now I defineitely think you're a bot.

I am not a bot...i am new on steemit...okk please remove your flags...👦

I guess you're a bot as well, then.

I am new bro...please remove your flag...please bro...👦...i need some followers so i create a message for creating a community... and invite some people...I apologize for giving you pain...i am new on steemit...please try to remove your ...flag...Thankss👷

This comment has received a 82.50 % upvote from @steemdiffuser thanks to: @stimialiti.

Bids above 0.1 SBD may get additional upvotes from our trail members.

Get Upvotes, Join Our Trail, or Delegate Some SP

You got a 63.80% upvote from @proffit courtesy of @stimialiti!
2-25% Return on investment. Check steembottracker.com for current status
Minimum 0.01 SBD/STEEM to get upvote , Minimum 1 SBD/STEEM to get upvote + resteem

Congratulations @oyvindsabo! You have completed the following achievement on Steemit and have been rewarded with new badge(s) :

Award for the number of comments received

Click on the badge to view your Board of Honor.
If you no longer want to receive notifications, reply to this comment with the word STOP

Do not miss the last post from @steemitboard:
SteemitBoard World Cup Contest - Home stretch to the finals. Do not miss them!


Participate in the SteemitBoard World Cup Contest!
Collect World Cup badges and win free SBD
Support the Gold Sponsors of the contest: @good-karma and @lukestokes


Do you like SteemitBoard's project? Then Vote for its witness and get one more award!

Coin Marketplace

STEEM 0.68
TRX 0.10
JST 0.076
BTC 58134.78
ETH 4688.92
BNB 639.71
SBD 7.37