Since this problem is such a basic introduction to recursion, I like to go against the grain and like solving it without recursion. This problem can be trivialized with a little mathematical insight. Binet's formula is a formula for calculating the nth fibonacci number.

return ((pow(((1+sqrt(5))/2),x-1)-pow(((1-sqrt(5))/2),x-1))/sqrt(5)).toInt

In a mathematically perfect universe the function would always output an integer, but due to floating point error it will usually be a little off. Rounding it to the nearest integer will solve this issue for all practical purposes (I have a hunch that if the input is allowed to be arbitrarily large then the error might make it round to the wrong int, but the input would probably be far outside any range one would reasonably be working with at that point).

This is the basic introduction to the recurssion chapter and probably this problem is always first approached when someone tries to present this topic. As with every recursion problem you need to cover your base cases and end the recursive stack. For this problem, the base case is different than your usual Fibonacci problem, but should not be to hard to code. Here's how it would look like in Scala:

def fibonacci(x:Int): Int = {
          if (x <= 1) 0;
          else if (x == 2) 1;
          else fibonacci(x-1) + fibonacci(x-2);
}

Oddly, it seems that Python 3 is not a language option...

Oddly, it seems that Python 3 is not a language option...

Easy in Haskell

fib n = fibs !! (n -1) where
    fibs = 0:1:[(a+b)|(a, b) <- zip fibs (tail fibs)]