Recursive Functions

Recursive functions are simply functions that refer to/call themselves in their definition. Recursion is a powerful technique to solve problems in an intuitive and compact manner. The common example used to illustrate this is the factorial function: $n! = n*(n-1)!$.

This is natural to do in mathematics, can we do the same in an Elm program? The answer is yes. Let us see how this looks. As you can see below the definition of the function facRrefers to itself. This looks identical to the definition of the function in mathematics!

import Graphics.Element exposing (..)
import List exposing (..)

--Recursion
facR : Int -> Int
facR n =
  if n < 1 then
    1
  else
    n*facR(n-1)

hemachandra : Int -> Int
hemachandra n =
  if n==0 then
     1
  else if  n==1 then
     1
  else
   hemachandra (n-1) + hemachandra (n-2)

main = flow down
        [
           print "factorial(5) is : " (facR 5)
          ,print "The 5'th Hemachandra number is : " (hemachandra 5)
        ]

--a helper function to make display easier
print message value = show (message ++ (toString value))

You can just enter this code in the online editor/runner to see how it works.

The recursion pattern has two ingredients:

• The termination condition: Need to handle all conditions that the recursion has to terminate for. For the factorial function it is when n gets to 0 we terminate the recursion. For those using recursion this is often the source of bugs, which leads to infinite recursion and program crashes!
• The recursive step: For all values of n other than the terminal one we describe how to compute the next value.

The second example that I have included generates the Fibonacci sequence. These numbers we noticed much earlier by an indian mathematician of ancient times Hemachandra.. Fields medallist Manjul Bhargava has been referring to the Hemanchandra numbers and how he was inspired by ancient Indian mathematicians. So we called the function hemachandra.

While recursion is a good technique to use to solve problems, often in programs we just end up combining library functions to write our code. So we could write the factorial function as factorial n = product [1..n]. (Try this out and see.)

Exercises

• Define a recursive function power such that power x y raises x to the y power.

Recursive functions a powerful tool to solve problems:

Let me illustrate the power of recursive functions with an example from mathematics. We have all computed the square root of a number at some point. (Have we?). Anyway try and think about writing a program to do that.

import Graphics.Element
import List exposing (..)

until : (a -> Bool) -> (a -> a) -> a -> a
until p f x = case (p x) of
   True -> x
   False -> until p f (f x)

sqrt x = 
  let
    goodenough y = abs(y*y - x) < eps*x
    improve y = (y +x/y)/2
    eps = 0.00001
  in until goodenough improve x


main =Graphics.Element.show (sqrt 27)

Now let us see if we can generalize this to a method to compute all the nthRoots of a number!

This is called Newton's method, named after Isaac Newton. Here is the code implementing Newton's method:

import Graphics.Element exposing (show, flow, down)
import List exposing (..)

until : (a -> Bool) -> (a -> a) -> a -> a
until p f x = case (p x) of
   True -> x
   False -> until p f (f x)

-- Newtons Method
deriv f x = 
  let 
    dx = 0.0001
  in  (f(x + dx) - f(x))/dx 

newton f = let 
             satis y = abs(f y) < eps
             eps = 0.0001
             improve y = y-(f y/deriv f y)
           in until satis improve

sqRtNewton x = let f y = y^2 - x 
                in newton f x

cubeRtNewton x = let f y = y^3 - x 
                in newton f x


main = flow down [
              print "square root of 2 using Newton's method : " (sqRtNewton 3)
             ,print "cube root of 2 using Newton's method : " (cubeRtNewton 3)
            ]

--a helper function to make display easier
print message value = show (message ++ (toString value))