Recursion
General overview
Recursion is a method where the solution to a problem depends on solutions to smaller instances of the same problem (as opposed to iteration). The approach can be applied to many types of problems.
Recursive functions invoke themselves, allowing an operation to be performed over and over until the base case is reached.
Recursion in Scala
Recursion plays a big role in pure functional programming and Scala supports recursion functions very well. Nevertheless, Scala can not infer the return type of a recursive function. You have to explicitly declare the return type.
For instance, the function f is incorrect:
> def f(x: Int) = 1 + f(x -1)
error: recursive method f needs result type
You should instead use:
def f(x: Int): Int = 1 + f(x - 1)
fibonacci
