Discover Ruby Programming Through Fun Examples/

...

/

Fibonacci and HCF (Recursion)

Fibonacci and HCF (Recursion)

Learn about recursion and try to find the HCF by implementing the Euclidean algorithm.

We'll cover the following...

Introduction to recursion

We want to explore the idea behind recursion by looking at a program that uses recursion for finding the nthn^{th} Fibonacci number. Before we explain what recursion is, let’s examine the formula for the nthn^{th} Fibonacci number:

fib(1) = 1
fib(2) = 1
fib(n) = fib(n-1) + fib(n-2)
Formula of N-th Fibonacci number

If we are asked the question: “what is the 6th6^{th} ...