Fibonacci Function

How does the fibonacci recursive function work?

You're defining a function in terms of itself. In general, fibonnaci(n) = fibonnaci(n - 2) + fibonnaci(n - 1). We're just representing this relationship in code. So, for fibonnaci(7) we can observe:

  • fibonacci(7) is equal to fibonacci(6) + fibonacci(5)
  • fibonacci(6) is equal to fibonacci(5) + fibonacci(4)
  • fibonacci(5) is equal to fibonacci(4) + fibonacci(3)
  • fibonacci(4) is equal to fibonacci(3) + fibonacci(2)
  • fibonacci(3) is equal to fibonacci(2) + fibonacci(1)
  • fibonacci(2) is equal to fibonacci(1) + fibonacci(0)
  • fibonacci(1) is equal to 1
  • fibonacci(0) is equal to 1

We now have all the parts needed to evaluate fibonacci(7), which was our original goal. Notice that the base case -- return 1 when n < 2 -- is what makes this possible. This is what stops the recursion, so that we can can start the process of unrolling the stack and summing the values we're returning at each step. Without this step, we'd continue calling fibonacci on smaller and smaller values right up until the program finally crashed.

It might help to add some logging statements that illustrate this:

function fibonacci(n, c) {
var indent = "";
for (var i = 0; i < c; i++) {
indent += " ";
}
console.log(indent + "fibonacci(" + n + ")");
if (n < 2) {
return 1;
} else {
return fibonacci(n - 2, c + 4) + fibonacci(n - 1, c + 4);
}
}

console.log(fibonacci(7, 0));

Output:

fibonacci(7)
fibonacci(5)
fibonacci(3)
fibonacci(1)
fibonacci(2)
fibonacci(0)
fibonacci(1)
fibonacci(4)
fibonacci(2)
fibonacci(0)
fibonacci(1)
fibonacci(3)
fibonacci(1)
fibonacci(2)
fibonacci(0)
fibonacci(1)
fibonacci(6)
fibonacci(4)
fibonacci(2)
fibonacci(0)
fibonacci(1)
fibonacci(3)
fibonacci(1)
fibonacci(2)
fibonacci(0)
fibonacci(1)
fibonacci(5)
fibonacci(3)
fibonacci(1)
fibonacci(2)
fibonacci(0)
fibonacci(1)
fibonacci(4)
fibonacci(2)
fibonacci(0)
fibonacci(1)
fibonacci(3)
fibonacci(1)
fibonacci(2)
fibonacci(0)
fibonacci(1)

Values at the same level of indentation are summed to produce the result for the previous level of indentation.

R function to find Fibonacci numbers

incorporate the following changes

Ms <- function(moving_sum) {
Fib <- numeric(moving_sum + 1) # Use the parameter moving_sum
Fib[1] <- Fib[2] <- 1
for (i in seq(3, moving_sum + 1)) Fib[i] <- Fib[i - 2] + Fib[i - 1]
return(Fib[-1]) # Remove the first number
}

Ms(20)
[1] 1 2 3 5 8 13 21 34 55 89 144 233 377
[14] 610 987 1597 2584 4181 6765 10946

Fibonacci function with C

in C, in a switch statement, in a case, to have a local variable, the body of the case must be enclosed in braces '{' and '}'

Java recursive Fibonacci sequence

In fibonacci sequence each item is the sum of the previous two. So, you wrote a recursive algorithm.

So,

fibonacci(5) = fibonacci(4) + fibonacci(3)

fibonacci(3) = fibonacci(2) + fibonacci(1)

fibonacci(4) = fibonacci(3) + fibonacci(2)

fibonacci(2) = fibonacci(1) + fibonacci(0)

Now you already know fibonacci(1)==1 and fibonacci(0) == 0. So, you can subsequently calculate the other values.

Now,

fibonacci(2) = 1+0 = 1
fibonacci(3) = 1+1 = 2
fibonacci(4) = 2+1 = 3
fibonacci(5) = 3+2 = 5

And from fibonacci sequence 0,1,1,2,3,5,8,13,21.... we can see that for 5th element the fibonacci sequence returns 5.

See here for Recursion Tutorial.



Related Topics



Leave a reply



Submit