Continuing with our previous post on recursions, let’s play with a couple of more simple examples to get ourselves familiar. This is just to start thinking in terms of recursive functions for the problems we try to solve. This kind of thinking will become more useful when we learn about tail recursion in one of the future posts.

Let’s write a small function, call it find, to find if a given element exists in a list. i.e., we are provided with an input list lst of integers and an integer x and the function would return true if x exists as one of the elements of lst and false otherwise.

let rec find x lst =
  match lst with
  | [] -> false
  | h::t ->
     if (h = x) then true
     else (find x t);;
(* val find : 'a -> 'a list -> bool = <fun> *)

find 2 l1;;
(* - : bool = true *)
find 0 l1;;
(* - : bool = false *)

As before, we think of the base case and the recursive step. We recursively call the function on a sub-list of the input list, till the problem reduces to the base case - the empty list.

Let’s try another simple examples - to find the minimum integer in the given list of integers. We will call the function find_min and it takes an input list lst.

exception Failure of string                   
let rec find_min lst =
  match lst with
  | [] -> failwith("empty list")
  | [h] -> h
  | h::t -> min h (find_min t);;
(* val find_min : 'a list -> 'a = <fun> *)

Let’s test it out:

find_min l1;;
(* - : int = 1 *)
let l2 = [-2; -10; 1; 9; 11; 7; 17];;
find_min l2;;
(* - : int = -10 *)

Let’s now move away from having lists as input, and work on an example that produces an output list. This is a very familiar introductory CS example - converting an input decimal number to it’s base-2 (binary) representation. Humans naturally count in base-10 (also called decimal) number system, probably because most of us were born with 10 fingers. Computers, to be technically correct I should say digital circuits, work on base-2 number system - they know 0 and 1. Just like how we count 0 .. 9 and then start counting 10 .. 19, followed by 20 .. 29, etc., digital circuits count 0, 1 followed by 10, 11 and then follow that by 100, 101, and 110, 111, etc. You see the pattern. Probably, it is more apparent if I write it one after the other:

  base-2    	   	  base-10
     0  	  	     0
     1  	  	     1
    10 	 <-- restart	     2
    11 		 	     3
   100   <-- restart 	     4
   101 	 	     	     5
   110 	 	     	     6
   111 	 	     	     7
  1000 	 <-- restart 	     8
  1001 	 	     	     9
  1010 	 	    	    10   <-- restart
  1011 	  	       	    11 
  1100           	    12
  1101           	    13
  1110           	    14
  1111           	    15

The usual way we compute the binary representation of a decimal number is to repeatedly divide it and collect the remainders. For example, if we want to compute the binary equivalent of decimal 7:

2 |_ 7 _          ^
  2 |_ 3 _   - (1) |
    2 |_ 1 _ - (1) |
         ---------->

111 is the binary equivalent of decimal 7. Here, 3, 1 are quotients (n/2 - n being the input number initally and then the quotient) and the ones on the right within parantheses are the remainders (n mod 2).

Let’s work out one more example - the binary equivalent of 13:

2 |_ 13 _               ^
  2 |_ 6 _        - (1) |
    2 |_ 3 _      - (0) |
      2 |_ 1 _    - (1) |
                -------->

If you observe carefully, what we are doing essentially is repeatedly dividing the input number n by the base we want to convert our number to - in this case base-2, and collect the remainders. Dividing a number is the expression n/2 for algorithmic purposes and the remainder is the expression n mod 2. What we are going to do is to repeatedly (think “recursively”) divide n and collect the remainder in a list which we would eventually return as the output result. @ is the OCaml syntax for list concatenation: for example lst1 @ lst2 will concatenate lst1 and lst2. Note the base case for our computation.

let rec bin_of_dec n =
  if n <= 0 then []
  else bin_of_dec (n/2) @
         (n mod 2)::[];;
(* val bin_of_dec : int -> int list = <fun> *)

Let’s check if what we worked out for 7 and 13 are consistent with what this program computes:

bin_of_dec 7;;
(* - : int list = [1; 1; 1] *)
bin_of_dec 13;;
(* - : int list = [1; 1; 0; 1] *)

I guess it became a longer post than what I intended it to be, but I hope you are getting a better hang of thinking recursively. We will see more examples in future posts - feel motivated to play around with some examples in the mean time!!

Recursion has been one of my favourite concepts for a very long time much like my fascination for mathematical induction. The subtle differences between the two would be a topic for a separate post.

Let’s do some simple recursive functions just to illustrate the beauty. I chose OCaml for this post as it is one of my favourite programming languages. Somehow, I feel that many algorithms when coded in OCaml look very intuitive and understandable than in other imperative programming languages. We will look at some algorithms in both OCaml and C in a later post and leave it to the reader to decide as to which one looks more intuitive.

OCaml is a very nice functional programming language and it offers list as a primitive data type. For example, if we want a list of five integers, this is how we do it in OCaml:

let l1 = [1;2;3;4;5];;

We would usually think of the list data type itself to be a recursive definition. i.e., a list is made of either an empty list or a list composed of a head element and tail where tail itself is a list (possibly empty list). For example, in the list l1 above, 1 constitutes the head element and the tail corresponds to the list 2;3;4;5.

Now, let’s write a recursive function to count the number of elements in the list.

1. Let’s think of the base case: when the list is empty - in which case we just return 0 as the result.
2. And let’s build our thought process this way - what if the list has just one element? This would correspond to a list where there is a single head element and an empty list as the tail. i.e., we count the single head element and the empty list (the tail) we know contributes 0 to our result (the base case we just saw in 1.).
3. Now, when the list has 2 elements, we think of it as having a head element and a tail list that consists of a single element. Now, we count the head element and apply the same function (our counting) to count the number of elements in the tail list (which now corresponds to the case we saw in 2.).

Essentially what we are doing is:

1. If the list is empty, return 0 as the result
2. If the list is not empty, count the head element (1) and call the function (recursively) to count the number of elements in the tail

Now, let’s write the above two steps in the following program which we call lst_len (for list length), that takes a single input parameter lst:

let rec lst_len lst = 
  match lst with
  | [] -> 0
  | h::t -> 1 + lst_len t;;
(* val len_lst : 'a list -> int = <fun> *)

Recursive functions in OCaml are defined with rec keyword. Let’s use this function to count the number of elements in our list l1:

lst_len l1;;
(* - : int = 5 *)

Let’s use the same thought process to write a recursive function lst_sum to sum up (add) the elements of the list.

let rec lst_sum lst = 
  match lst with
  | [] -> 0
  | h::t -> h + lst_sum t;;
(* val lst_sum : int list -> int = <fun> *)

And let’s use this function to sum up the elements in our list l1:

lst_sum l1;;
(* - : int = 15 *)

Isn’t this intuitive and elegant way of programming? We’ll talk more about simple programs that can be written in an intuitive way and try to develop our understanding of the concepts in a clear way.

Thanks for your interest and keep checking out this space for more.

This is my first post. I will keep this a very short one - nothing interesting to read and learn. The internet is a wonderful place. I learnt a lot by browsing interesting blogs, tutorials, asking questions on the various sites, twitter, etc. and it imperative that I give back to the community that helps me learn continuously. I am hoping to be regular with this effort at learning by teaching the many subjects and topics that interest me. Let’s see how much I can keep up and how much I can learn.