Recursion in three languages

[bjl]

recursion - see recursion

I start off with that worn out joke to emphasize the main point of recursion: that a function can call itself. However, one thing this joke fails to show is that recursion can do work in a fairly efficient way. In this tutorial I will start out with how to define a problem recursively and then solve two commonly offered problems in three different languages, Common Lisp, Python, and C++.

The First Issue
To define a problem recursively, break it up into several small parts. The two most important being a base case (or when to stop calling the function and return an actual value) and when to call the function.

To illustrate, here is an example. In statistices it is often necessary to calculate a factorial. Here are two ways to define a factorial, with the second being a recursive definition

Given an integer N: N! = N x N-1 x N-2 ...

Given an integer N: 0! = 1, N! = (N-1)!

The Problems

Problem 1: Given a list (or vector of integers) return true if all the integers are even,
else, return false.

Common Lisp

(defun all-even-p (lst)
   (cond ((null lst) t))
	 ((oddp lst) nil))
	 (t (all-even-p (rest lst)))))

Python

def all_even_p (lst):
       if not lst:
               return True
       elif lst[0] % 2 == 1:
	       return False
       else:
	       all_even_p(lst(1:))

C++

// Please note that I have not debugged this code.  I'm not sure if the 'lst.size() == 0' 
// line will work as a means of determining if a container is empty.  If anyone has an 
// easier way to do that, let me know and I'll change that (C++ is not my best language ;))
bool all_even_p(vector<int> lst){
    if(lst.size() == 0)
         return true;
    else if(lst[0] % 2 == 1)
         return true;
    else {
         vector<int> temp;
         for(int i = 1; i =! lst.size(); ++i){
              int x = 0;
              temp[x] = lst[i];}
         all_even_p(temp);}
}

Problem 2: Given an integer calculate the factorial as defined above.

Common Lisp

(defun factorial (x)
   (if ((equal x 0) 1)
       (* x (factorial(1- x)))))

Python

def factorial (x):
       if x == 0:
               return True
       else:
               x * factorial(x - 1)

C++

int factorial(int x) {
    if(x == 0)
         return true;
    else
         x * factorial((x - 1))
}

Thanks for reading,
bjl

[Jordan]

Not bad, thanks for sharing! +rep