Recursive functions are amazing tools for programmers to do iteration without using a traditional for-loop. It is also the only tool in function programming language to do iteration.
In Haskell, recursive functions look like this:
sum_up x
' x == 0 = 0
' otherwise = x + sum_up (x - 1)
This is a recursive functions that returns the sum of natural numbers from 0 to n in just three line of code. Amazing right?
But, sometimes, recursive functions are hard to understand, so we need to formulate a way to comprehend the algorithm and check if the algorithm is working.
To prove a recursive algorithm is working, we need to prove three idea of this algorithm:
- Initialization: Checking the boundary of inputs, make sure the variable is properly initialized.
- Maintenance: the assumption for the algorithm holds before and after every recursive calls
- Termination: we do not want a recursive algorithm that never terminates( infinite recursive calls will consumes large amount of memory.) If you read through my code for sum up again, you will see that it is not properly initialized. What if I gave a negative number as an input? We need to code defensively to make a more robust program. (Such idea is called defensive programming)
To understand better for recursive algorithm, I will give you a example of Fibonacci function, which calculates the nth number in a Fibonacci sequence.
fib :: Integer -> Integer
fib x
' x < 1 = error "n should be greater than 0"
' x == 1 = 1
' x == 2 = 2
' otherwise = fib (x - 1) + fib (x - 2)
Note that this is just a simple version, and it is not the optimal algorithm for calculating Fibonacci number.(the time complexity is exponential, and there is a solution to reduce this algorithm to linear time, think about it.)