FP Module 2 - 101 Scala
Bubu
5,506 views
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
package fp101.tp01.functions
object ExerciceFunctionsRecursion {
/**
*
* Using recursion, write bellow the fibonacci recursion function.
*
* The Fibonacci numbers are the numbers characterized by the fact that every number is the sum of the two preceding ones.
* - the recurrence relation is F(n) = F(n - 1) + F(n - 2)
* - the base case is: F(0) = 1, F1 = 1
*
*/
def fibonacci = ???
}
Create your playground on Tech.io
This playground was created on Tech.io, our hands-on, knowledge-sharing platform for developers.
Suggested playgrounds