#include <stdio.h>
int fib(int number)
{
if (number <= 1)
return number;
return fib(number-1) + fib(number-2);
}

int main ()
{
int number;
scanf("%d", &number);
printf("%d", fib(number));

return 0;
}

How is it , took help geek from geeks ,though

Python solution that uses the fact that the ratio of consecutive numbers in the sequence approaches Phi

def fib(n):
    if n < 3:
        return 1
    return int(round(1.618 * fib(n-1)))

In Perl 6 you can do something like this:

my @fib = 0, 1, * + * ... *

This make uses of the ... sequence operator, which will produce (possibly lazy) generic sequences on demand.

Then you can get the first 10 Fibonacci numbers:

@fib[0..10]

More detailed explanation about this (not mine) could be found at: perl6.online/2018/12/15/playing-wi... and perl6advent.wordpress.com/2010/12/...

// better space complexity
function fancyFib(n) {
  const computed = [0,1];
  if(n <= 1) return computed[n];
  for(i = 2; i <= n; i++)
    computed[i%2] = computed[0] + computed[1];
  return computed[n%2];
}

// maintains fidelity
function fibdelity(n) {
  const computed = [0,1];
  for(i = 2; i <= n; i++)
    computed.push(computed[i-1] + computed[i-2]);
  console.log(computed);
  return computed[n];
}

Here is the DP solution in javascript.
O(n) runtime complexity
O(1) space complexity

some loss in the fidelity of the computation since computations used to build upto fib(n) are lost.

maintaining fidelity would probably be better in practical use since saving the pre-computed values would lead to O(1) complexity for values already computed.

In compiled languages you could do this step in compile time and then cache them for O(1) runtime, but you would sacrifice some space O(n) space complexity

Ruby hashes (a.k.a dictionaries) accept a block to calculate missing entries.

You can abuse this mechanism and store only 0 and 1, and then use the default_proc for everything else:

fib = Hash.new do |hash, key|
  hash[key] = hash[key - 1] + hash[key - 2]
end.merge({ 0 => 0, 1 => 1})

(0..10).each do |n|
  puts fib[n]
end
# 0
# 1
# 1
# 2
# 3
# 5
# 8
# 13
# 21
# 34
# 55
# => 1..10

I couldn't resist one more pass, using C.

int fib(n) {
    int p[2] = {0,1};
    int* r = &(p[n%2]);
    g: p[(n--)%2] = p[0]+p[1];
    if (n) {goto g;}
    return *r;
}

I'm using a pair to calculate the sequence, ergo the 2-element integer array.

Before I can do anything, though, I need to know where my answer will show up, so I create a pointer to the element which will eventually hold the result. That way, I can mutate n without fear. How this works will become apparent in a second.

This next line has a label, g, which I'll be using in a moment. In this math, I'm alternating which of the two elements in the pair are used to store the sum, and I'm switching between them by checking if n is even or odd (n%2), yielding either 1 (odd) or 0 (even). In the middle of that, I'm also decrementing n after I've used its value. I take the sum of the two elements, and save it in the target position in the pair. This way, I always have the latest two elements.

On the next line, if n has a non-zero value, I jump back to that previous line, using its g label. I'm using a goto statement, instead of an explicit loop or recursion (so, technically I hit one of the bonus goals? Debatable.)

Once I'm done, and n has reached zero, I return whatever was in the position I originally stored to look for the answer in. Remember how I was using the modulo to alternate spots? That same logic is at work here. If the original n was even, then the last value will get written to the first spot in the pair; if the original n is odd, then the second spot will be used.

const fib = (num) => {
  if (num == 0) return 0
  let x = 'I', y = ''
  for (let i = 0; i < num; i++) {
    if (i % 2 == 0)
      x += y
    else
      y += x

    return Math.max(x.length, y.length);
  }
}

Golly that was hard to do on mobile!
No need for maths or recursion here, let's use base 0 with a loop!

I'm going for the bonus points, no explicit loops nor recursion, and O(1) time*.

import math

sq5 = math.sqrt(5.0)
def fib( n ):
    a = ((1.0 + sq5)/2) ** n
    b = ((1.0 - sq5)/2 ) ** n
    return  int( (a - b) / sq5 )

for i in range(20):
    print(fib(i))

This is a closed form evaluation of the n-th fibonnaci number.

The int cast is because the double isn't precise enough, thus a bit of error value accumulates. Remove it to see how much.

** Time complexity, you might get picky here and we can debate what the time complexity of **n is. In worst case it shouldn't be more than log(n) given that the generic pow is log(n).

Using Kotlin:

fun fib(n: Int): Int = generateSequence(Pair(1, 1)) {
    Pair(it.second, it.first + it.second)
}.elementAt(n).first

Generate a Sequence (infinite stream of data) starting with 1, 1. Each next element is the second number of the pair + their sum. Use elementAt to get the n-th pair. The result is the first number of the pair.

Try it out online: pl.kotl.in/MOeDSCD4v

Lisp version (using emacs)

(cl-defun fibonacci(n)
  (cond
   ((<= n 1) n)
   (t (+ (fibonacci (- n 1))
     (fibonacci (- n 2)))
      )
   )
  )