What is recursion?
What is recursion?
04/01/2015
What is rec... Ok, I'll stop!
Recursion is a very powerful programming technique that involves calling a function inside itself. It works by breaking down problems into smaller versions of itself. Sounds confusing? Good, it is confusing! Here's an example:
def factorial(n) return 1 if n <= 1 return n * factorial(n - 1) end factorial(3) => 6 factorial(4) => 24 factorial(7) => 5040
The code above is the most used and simplest example to teach Recursion. It defines a factorial function, which accepts a number as a parameter. If said number is less than or equal to 1, it returns 1. Otherwise it does its job recursively, it returns the number multiplied by the factorial function of the same number minus one. It's going to keep doing that until n is equal to 1, which will then end the function.
Almost every recursive function must have at least one base case, where the input produces a result without recurring so it doesn't make an infinite loop. Notable exceptions to this are some system or server processes which will run indefinitely.
Here's another example:
def hello_world(n) return if n < 1 puts "Hello World" hello_world(n - 1) end hello_world(3)
On the example above we define a function hello_world which takes a number n as a parameter and prints Hello World n times. We start with the base case, which is in case the number is less than 1, which would mean that the program shouldn't print anything. If that is not the case, we should print Hello World at least once, so we do it and call hello_world again using the same number minus one. Do you see the pattern? It's going to keep printing Hello World and calling hello_world until the number is less than 1.
Apparently in imperative languages such as ruby you wanna stick with iteration because it works faster than recursion in most cases. On the other hand, if you work with functional languages such as Scala, recursion might be faster. In Haskell, Scheme and Clojure, all functional languages, recursion is mandatory. Other than performance, the only real reasons to use recursion would be shorter, better looking code and to take advantage of the call stack, which is a more advanced subject that I am not yet comfortable talking about!
