A Simple Recursion
Recursion is used quite extensively in a number of algorithms, like quick sort, dynamic programming, stack-based operations…and the list goes on. Recursion is highly expressive and intuitive. Sometimes we also use recursion to avoid mutation. Let’s look at a use of recursion here. We’ll keep the problem simple so we can focus on the issues with recursion instead of dealing with problem or domain complexities.
| ProgrammingRecursions/factorial.scala | |
| Line 1 | def factorial(number: Int) : BigInt = { |
| 2 | if(number == 0) |
| 3 | 1 |
| 4 | else |
| 5 | number * factorial(number - 1) |
| 6 | } |
The factorial function receives a parameter and returns a value of 1 if the parameter is zero. Otherwise, it recursively calls itself to return a product of that number times the factorial of the number minus one.
Writing a recursive function in Scala is much like writing any function, except the return-type inference takes a vacation—Scala insists on seeing the return-type explicitly for recursive functions. The reason for this is, since the function calls itself in at least one path of execution, Scala doesn’t want to take the burden of figuring out the return type.
Let’s run the factorial function for a relatively small input value:
| | println(factorial(5)) |
The call will run quickly and produce the desired result, showing that Scala handled the recursive call quite well:
| | 120 |
Take a close look at the code on line 5 in the factorial function; the last operation is the multiplication (*). In each call through the function, the value of the number parameter will be held in a level of stack, while waiting for the result from the subsequent call to arrive. If the input parameter is 5, the call will get six levels deep before the recursion terminates.
The stack is a limited resource and can’t grow boundlessly. For a large input value, simple recursion will run into trouble rather quickly. For example, try calling the factorial function with a large value, like so:
| | println(factorial(10000)) |
Here’s the fate of that call:
| | java.lang.StackOverflowError |
It’s quite sad that such a powerful and elegant concept meets such a terrible fate, incapable of taking on some real demand.
Most languages that support recursion have limitations on the use of recursion. Thankfully, some languages, like Scala, have some nice support to avoid these issues, as you’ll see next.