Using Recursive Methods
A method can call itself—for example, here you’ll calculate the factorial of an integer in a method, fact:
| | def fact(n) |
| | n == 0 ? 1 : n * fact(n - 1) |
| | end |
| | |
| | fact(5) # => 120 |
This method happily accepts any argument, but look what happens when you feed it a negative integer or a string:
| | fact(-2) # => Runtime error: Invalid memory access |
| | (signal 11) at address 0x7ffbff7fdff8 |
| | fact("Crystal") # => Error: undefined method '-' for String |
You can make your code more robust by using types and handling exceptions:
| | def fact(n : Int) : Int |
| | if n < 0 |
| | raise ("n cannot be negative!") |
| | end |
| | n == 0 ? 1 : n * fact(n - 1) |
| | end |
| | |
| | fact(5) # => 120 |
| | |
| | begin |
| | fact(-2) # => Runtime error: n cannot be negative! (Exception) |
| | rescue ex |
| | p ex.message |
| | end |
| | # => "n cannot be negative!" |
| | |
| | fact("Crystal") # => Error: no overload matches 'fact' with type String |
Now your program doesn’t crash: the raised exception is caught, and its message is displayed. And giving a string argument is stopped at compilation with a clear message about wrong argument types.
But if you don’t want to use the heavy begin-rescue clause, simply print out the error message and exit the program:
| | def fact(n : Int) : Int |
| | if n < 0 |
| | puts "n must be positive!" |
| | exit |
| | end |
| | n == 0 ? 1 : n * fact(n - 1) |
| | end |
| | |
| | fact(5) # => 120 |
| | fact(-2) # => "n must be positive!" |
It’s a good idea to test defensively when entering any method, especially recursive ones. This approach also lets you exit from deep recursion easily. Return immediately from the method when a necessary condition isn’t met. For example:
| | def some_method(n : Int) |
| | return nil unless n > 1 |
| | # other code, here n is > 1 |
| | end |
You could return nil or false or any other value that you see fit. Some people like to use unless here because it states the condition that has to be fulfilled, so it may be easier to understand. Remember that errors are expensive. Raise errors only when a condition needs special attention.
Tail Calls Add Up | |
|---|---|
|
Some languages derived from Ruby, notably Elixir, are designed to let recursion go infinitely deep as long as the function doesn’t require tracking additional information. When possible, they perform what is called tail call optimization, explicitly looking for recursive function calls in the last line of a function, and removing the normal overhead that would track the calls. Crystal doesn’t explicitly support tail call optimization, though the LLVM compiler underneath sometimes does that work. While you can make recursion go a long way, you may find limits to how deep you can go in a variety of circumstances. |
Your Turn 4
➤ BubbleSort: Implement the Bubblesort[32] algorithm for sorting an array, using the pseudocode you’ll find there. Make a copy of the input using the dup method. Write two versions of the algorithm, as an ascending and descending sort, using yield and a code block for each version.