Forem: DamianZoirbile

The Wizard's Code: Finding the Nth Fibonacci Number in Three Ways

DamianZoirbile — Sat, 15 Feb 2025 07:15:22 +0000

In the ancient kingdom of Numaria, where magic and mathematics intertwined, a mysterious book appeared through a glowing portal. Sam, a young scholar with an insatiable curiosity, discovered this futuristic book and learned about a fascinating sequence—the Fibonacci sequence. But how could he find the nth Fibonacci number efficiently? He sought the wisdom of Eldrin, the legendary scholar wizard who knew the secrets of the past, present, and future.

The First Method: Recursion (A Bewitching but Costly Spell)

Eldrin waved his staff, and a magical projection appeared, showing the first method—recursion. "This method follows the natural definition of the Fibonacci sequence," he explained.

function fibonacciRecursive(n) {
    if (n <= 1) return n;
    return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}

console.log(fibonacciRecursive(6)); // Output: 8

Sam watched as numbers split and branched endlessly like an enchanted tree. "This spell is too chaotic! Each number calls upon two more, and the calculations grow exponentially!" he protested. Eldrin nodded. "Indeed, this method has O(2^n) time complexity, making it inefficient for large numbers. We need a better way."

The Second Method: Iterative Approach (The March of Soldiers)

Eldrin then conjured another method—iteration using loops. "Instead of invoking magic recursively, we march forward step by step," he said, drawing a straight path.

function fibonacciIterative(n) {
    let a = 0, b = 1;
    for (let i = 2; i <= n; i++) {
        let temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

console.log(fibonacciIterative(6)); // Output: 8

Sam observed, "This is better, but as numbers grow, the march becomes longer and takes more time!" Eldrin sighed. "Yes, this runs in O(n) time complexity, which is an improvement, but not the ultimate solution."

The Third Method: The Secret Formula (The Wizard’s Final Revelation)

Eldrin flipped to a hidden page in the book, revealing an ancient formula—Binet’s Formula.

function fibonacciFormula(n) {
    const sqrt5 = Math.sqrt(5);
    const phi = (1 + sqrt5) / 2;
    return Math.round((Math.pow(phi, n) - Math.pow(-phi, -n)) / sqrt5);
}

console.log(fibonacciFormula(6)); // Output: 8

Sam gasped as glowing golden symbols formed in the air. "A single formula that instantly finds any Fibonacci number?" Eldrin smiled. "Yes, this has O(1) time complexity, making it the most efficient method. It’s the true power of mathematics in programming!"

Conclusion: The Magic of Optimization

Sam learned a great lesson that day—every problem has an optimized solution, and mathematics holds the key. "Never settle for brute force," Eldrin advised. "Recognize patterns, think mathematically, and seek the best approach."

With newfound wisdom, Sam set out to apply this principle to every challenge he faced. And so, the legend of the Fibonacci Wizard spread across Numaria, inspiring generations of scholars and programmers alike.

This story highlights the importance of mathematical thinking in programming. Optimization matters! Which method do you prefer when solving problems?

How to start the programming journey in a proper and the best way

DamianZoirbile — Wed, 31 Jan 2024 06:14:55 +0000

You get the right here!!!

Do you ever find yourself wasting time researching the right path for your career, unsure of where to focus? Perhaps you've been watching numerous YouTube videos to identify a programming language that suits your career, and you're uncertain about which field to choose. If so, you're in the right place. I will guide you through a well-founded path for your future career in software development or other tech-related fields.

The Dungeons You would enter

Programming serves as the engine propelling various paths, acting as the vehicles navigating those paths. As stated in the above quote, programming is a fundamental tool within the development field. To excel, you must also acquire proficiency in other technologies relevant to your chosen path. While there is a multitude of fields to explore throughout your life, it's crucial to consistently remind yourself not to hastily jump from one to another. Mastering a skill requires time and dedication. Now, let's delve into some trending and in-demand fields, categorized for your convenience.

Note: I won't delve into the detailed explanations of these fields here; however, you can explore these topics on YouTube, where a plethora of content is readily available. Each of these sectors requires a certain level of programming expertise. The specific skill level may vary among them, but proficiency in programming is a prerequisite for success in all these sectors.

At this moment, you may already have a clear path to follow, or you might find yourself uncertain. Alternatively, you may have a chosen path but lack clarity on where to commence. Don't worry—I guarantee that the steps I will present serve as a solid foundation applicable across various sectors.

Every first step is always difficult!!

You need to prepare mentally for a career in this field, as it is constantly challenging and requires staying updated on the latest technologies. It can be overwhelming and frustrating at times, but remember, if things are difficult, you are on the right path. Facing challenges builds strength. Remind yourself that you will encounter ups and downs.

Believe in the power of a slow burn, consistency, and discipline. While motivation is important, rely on consistency and discipline to see you through. Don't bite off more than you can chew in the initial steps. Also, trust the process. Becoming a developer is not achieved simply by learning a programming language; it's a lifelong journey.

So, let's get started.

Your First Programming Language

From my experience, the most suitable programming language for beginners is Python, and here's why.

I won't delve into a detailed explanation of what Python is, but in short, it is a programming language widely used across various fields, including the medical domain. While this blog won't provide an exhaustive overview of Python's intricacies, I'll explain why it's an excellent choice for beginners.

Firstly, Python is easy to write and understand, resembling human language. This feature is crucial for beginners who might initially feel that programming involves creating something only a computer can comprehend. Python's readability is exceptionally convenient for newcomers.

Secondly, there is an abundance of resources available for self-learning. My very first programming course was on YouTube, and it was entirely free. You'll find high-quality content for Python readily accessible.

Last but not least, as previously mentioned, Python is utilized in various fields. This versatility allows you to apply your Python knowledge across sectors, making it a winning choice. Python is particularly in demand in Artificial Intelligence and widely used in web development as a backend programming language and in game development. While Python has its drawbacks, the key point I want to emphasize is that learning Python as your programming language won't leave you at a disadvantage.

The Study Plan

From my experience, my study plan is composed of three key elements.

Learning

Learning is an essential part of your journey, and you should always remind yourself that learning is a lifelong commitment in this career. Now, let's discuss "Where to learn," while the topic of "How to learn" will be covered in the next section on Practicing.

YouTube Videos

YouTube Videos are an excellent resource, especially for those seeking free and quality content rather than paid courses. Learning with free resources is not a disadvantage, and I recommend starting with YouTube, just as I did. It's a cost-effective option, and if you find it doesn't suit your preferences, don't worry—it's free, and you can explore other options.

In this context, I can assure you that playlists of videos divided by topics are much more effective than longer videos that are approximately 2 hours or more.

Noted: It's important to understand that the length of a video doesn't necessarily correlate with the amount of information it contains. Therefore, when choosing resources, focus on finding playlists of videos that offer comprehensive content. Learn systematically, going through each topic in detail. If you encounter difficulty understanding a concept, don't hesitate to rewatch the video or seek out alternative explanations from different videos. In conclusion, leverage YouTube playlists to build a solid understanding of the basic foundational knowledge.

Course

You can opt to buy or enroll in a specific course that aligns with your interests. I don't need to elaborate on this because taking a course is straightforward—you enroll and learn. However, selecting the most suitable course for yourself is a priority, and you should be mindful of the paid classes, considering that many courses are paid. Platforms I recommend for online courses include Udemy, Coursera, and Skillshare.

Book

This might not be applicable to everyone, but it's important to note that courses and videos often present topics at a higher, more generalized level. They may not delve deeply into the specifics. Books, on the other hand, consolidate numerous details in one place, offering content in an ordered manner. Similar to choosing a course, finding the most suitable book for yourself is essential.

Practicing

That is correct; you've likely heard the saying, "Practice makes perfect." However, it's crucial to practice in an effective and meaningful way. Practicing in programming doesn't mean simply rewriting code repeatedly, as you might do with other skills. For example, becoming proficient at shooting arrows involves using a bow and arrows repeatedly until you gain the skill and comfort. However, programming doesn't follow the same pattern.

In programming, problem-solving is the key skill. Essentially, programming is about solving problems using a computer. Initially, this can be an extremely challenging step for every beginner learner. Therefore, practicing programming means actively attempting to solve problems.

So, where do you find these problems? Initially, you'll encounter problems during your learning process, and these are often relatively straightforward. However, as you progress, it's beneficial to actively seek out more complex problems. I recommend CodeWars because it offers a variety of basic programming challenges, and you can explore other people's solutions in your chosen programming language. CodeWars also supports a wide range of programming languages.

Note: The vital aspect of this practicing step is to not lose hope and never give up. It certainly takes time, but perseverance is key.

Doing Project

There is a term that every programmer fears, and that is "Tutorial Hell" where individuals get stuck watching tutorials without applying their knowledge or theories in the real world. This can be a dangerous trap for those who feel they are not yet perfect to undertake a project.

The only way to break free from this trap is by working on projects, whether they are small or large, simple or complex. The key is to start and build based on your existing knowledge. Avoid beginning with ambitious projects like creating your own Facebook, especially when you may not yet grasp the basics of the programming language.

Start with something simple. Believe in the progress you make, and trust in yourself. The question to ask is, "Which project do you need to do?" This is a self-assessment to test your knowledge. However, remember that you need to learn first, practice, and then create projects based on your level of proficiency.

Absolutely, you can now see the pipeline of the programming journey and start today. Avoid postponing it to tomorrow, as many tend to say, including myself before. Remember, you need to trust yourself. The initial steps may be challenging, but don't give up and go with the flow of progress.

Good luck, soldiers!

Recursion : Linear recursion and Tail recursion

DamianZoirbile — Wed, 13 Oct 2021 16:33:31 +0000

What is Recursion?

In term of computer science, recursion is the calling the function itself. Yes, that all. But it's not simple though.

Let take an example of the real world

Have you ever see a photo in the photo of the photo in the photo the.... so on. This is the example of recursion process.

Above the exapmle, It a exactly single photo in the photo of that photo. Confused???

Here is the another photo. I named this "Recursive cat". Cute Right? HAHA.

The photo depict itself in the frame and In this frame the previous photo do the same task.

So back in computer science, Recursion is the function calling itself and doing the same things what function does. Recursion Algorithm makes the problem into the sub-problems or smaller problems and compute until the base case.
(What is base case?? I will show you later. Don't worry.)

Let get into it.

There is two recursive process....

Linear Recursion
Tail Recursion

Linear Recursion

Linear recursion is the normal recursion and It needs to understand before going to the tail recursion.
Let take a look a problem.

If we wanna write a function that compute the Factorial, How to solve it??

Before writing the code, let see what is the Factorial.

Factorial

In Mathematics. Factorial is the positive integer which is product of a number and less then it. Yes, It look like a series. Factorial of the number(n) is denoted by n!.
So the Factorial of 4 is
4! = 4*3*2*1 = 24

So the Factorial is the multiplying of the number-n until to the one.
And the general formula of Factorial is
n! = n*(n-1)!

Let substitute 4 in this Formula

4! = 4*3! # (4-1)! is 3!
     4*3*2!
     4*3*2*1! # the value of 1! is 1 so..
     4*3*2
     4*6
     24

See? the Factorial number-n multiply until one.
More About Factorial

Let Code

All of the code under is just pseudo code. I will not use any programming languages.

We will write a Factorial Function named fac() and it takes one argument n as parameter. fac(n) compute n! .
How to compute??
The formula of Factorial is n! = n*(n-1)!

So the function fac(n) return the answer of n! computing n*(n-1)! until to one.

fac(n) = n * fac(n-1) 
# fac(n-1) means (n-1)!

Here is the problem!!!

This function fac(n) doesn't execute until one. It will run forever before stack memory is full.
Because fac(n) call itself forever even it will reach one.
When it reach one

fac(1-1)
fac(0) 
fac(-1) # fac(0-1)
.........so on

It goes forever and when the stack memory full, it will rise an error. Also it will never give a result.And the Factorial of -1 makes non-sense.

The Solution is Base Case.

What is a actually Base Case.
It means that when the function recursion reach Base Case the program must stop and return the result to previous function recursion.

For our problem, the Base Case is one.

So, Here is our function definition again..

fac(n) = if n == 1
           return 1
         else n * fac(n-1)

Let excute fac(4)

fac(4)
= 4 * (fac(3))
= 4 * (3 * (fac(2)))
= 4 * (3 * (2 * (fac(1))) 
# So we reach the Base Case one and return the result one
= 4 * (3 * (2 * (1)))
= 4 * (3 * (2))
= 4 * (6)
= 24

At that time, the program will not run forever and when it reach base case, it will return 1.

That is linear recursion.

But the linear recursion has a big problem.
Yes, Efficiency.
How about if you wanna know the Factorial of 100000.
Ohh..goddd... A Huge Number!!!!
In this case, Stack Over Flow error will rise. Because if Factorial of 4 even takes many steps, How many steps does 100000 takes??

fac(100000)
= 100000 * (fac(99999))
= 100000 * (99999 * (fac(99998)))
= 100000 * (99999 * (99998 * (fac(99997))))
# ...... so on!!!!

See the Problem??
The Stack memory will be full at some steps and can't call next recursion. So, stack over flow error will rise.

It will use a lot of Memory and not efficient. It will go to the base case and come back to the recursion. So, it will expand the function call stack just like above the code.

What does it look like?

Exactly, Linear recursion looks like your workdays. On Monday, you may think "I don't need to do right now. Now I'm gonna to chill. Ok!!!". Next day, You also do the same as yesterday and next day by day. On Friday, You have a lot of things to do. It's Friday but you can't happy for weekend.
Also Linear Recursion wait the result until it reach the base case. When you call Factorial of 100000, the computer will kick off and smash you. I'm sure.
That is the problem of Linear Recursion.

Tail Recursion

In Tail Recursion, Something new happen and a little bit change.
We also declare Factorial function fac(). But now we will take two argument as parameter, number(n) and accumulator(a). Accumulator is doing the task which takes the result of Factorial instead of going until base case. And Accumulator a is initialize 1 at first

Let Code

fac(n,a=1) = fac(n-1,a*n)

Hey,Don't forget the Base Case. It is very curial in Recursion.

fac(n,a=1) = if n == 1
             return a
           else fac(n-1,n*a)

Let excute fac(4,a=1)

fac(4,a=1)
fac(3,a=4) # a=1 and 1*4 is 4
fac(2,a=12) # a=4 and 3*4 is 12
fac(1,a=24) # a=12 and 2*12 is 24
# Here is our base case and return a which is 24

In Tail recursion, Factorial function doesn't expand the function order and efficient than the Linear Recursion.

So, I hope you have a little knowledge about recursion and recursive processes.

All of the above are not the whole theory.It is just a knowledge sharing and a piece of tiny concept.

If something wrong, please inform showwaiyan555@gmail.com

Here is the reference

Applicative order Vs Normal order

DamianZoirbile — Wed, 21 Jul 2021 14:14:18 +0000

Yeah, the Topic is a little weird. You ever heard static language and dynamic language. So, this topic looks like the same static vs dynamic language.

Functional programming

In Functional programming, the evaluation of an expression rewrites the canonical form into the order(Evaluation Order).

What is rewriting the function??
It’s replacing the function body with the function call.
Eg Code Block:

//if the function the double the number
double x = x + x;
//if we call this function with a number
double 4
//It replaces by the body of the function "x + x" with argument
double 4 => 4 + 4
//so the answer is 8

This is the evaluation of the function.

Evaluation Order

There's two important order rewriting.
1.Normal order
->It rewrites or execute leftmost occurrence of a function.
2.Applicative order
->It rewrites or execute innermost occurrence of a function.

Let do some codes

//the function double the number
double x = x + x;
//the function average the two number
average x y = (x + y) / 2;

To avoid confusing the concept, let re-express operator function "+" , "*" and "/".

//so the function double change into 
double x = plus x x //change expression num1 + num2
//so the function average change into
average x y = divide (plus x y) 2 //change expression num1 / num2

Let evaluate double(average 2 4)

Normal Order

Normal order execute leftmost part of function.

double (average 2 4) =>
plus (average 2 4) (average 2 4) =>
plus (divide (plus 2 4) 2) (average 2 4) =>
plus (divide 6 2) (average 2 4) =>
plus 3 (average 2 4) =>
plus 3 (divide (plus 2 4) 2) =>
plus 3 (divide 6 2) =>
plus 3 3 =>
6

Applicative Order

Applicative Order execute innermost part of function.

 double (average 2 4) =>
 double (divide (plus 2 4) 2) =>
 double (divide 6 2) =>
 double 3 =>
 plus 3 3 =>
 6

So, We see. Normal order evaluate many steps and it is a delay evaluation. It is lazy evaluation.
Applicative Order takes the few steps.

So, This is Applicative order languages vs normal order languages.

Here is the reference link