Universidad Carlos III de Madrid

If there is no base case in a recursive function, the following calls to the function will be executed without never stopping. The base case of a recursive method is an instance that can be solved without recursion, by hand. It is a "necessary but not sufficient" condition to solve any recursive function. In the case of the harmonic function, the base case is when n=1, for which the result is 1. However, the harmonic function can launch a StackOverflowError exception; it is still necessary to make additional changes to make it work.

The existence of a base case does not guarantee that the function works. To make the function works correctly, every call to it must make progress toward a base case, in order to terminate eventually. The next recursive method that calculates the factorial of a number has these two conditions to be solved:

public long factorial(int n) {
  if (n == 1) return 1;
  return n * factorial(n-1);
}						
					

To do the conversion, the last call has to be substituted by the appropiate assignments, so as the current parameters store the values of the last call's parameter The iterative version is shown below:

		
public void hanoiTowers(int n, char from, char to, char ch){
 char temp;
 while (n>1) {
  hanoiTowers(n-1, from, ch, to);
  System.out.println("Move "+n+" from "+from+"to "+to);
  n=n-1; temp= from; d= ch; ch= temp;
 }
 if (n==1)
 System.out.println("Move 1 in"+from+"to "+to);
}

The reason of this inneficiency is that recursivity calculates the same values over and over again, because it does not store previous calculations. Examples of the number of calls with the previous method are:

		
For fib(5), 15 calls to the method are invoked.
For fib(10), 177 calls to the method are invoked.
For fib(20), 21891 calls to the method are invoked.
For fib(25), 242785 calls to the method are invoked.
...

By means of tail-recursive methods, that does not store any partial result, these partial results already obtained are passed as arguments to the next recursive call; therefore, those are not calculated more than once. The linear version of the Fibonacci series is as follows:

public static long fibo (int n,x,y){
 if (n<=1)
  return x+y;
 else
  return fibo(n-1,y,x+y);
 }
 public static long fib (int n) {
  return fibo(n,0,1);
}

Although an iterative algorithm can be more complicated than its recursive version, it allows to take the total control over its execution. Besides, the limited size of the system stack makes difficult to foresee when the stack is going to be overflow. The iterative version of Fibonacci is as follows:

		
long fib(int n){
 if (n < 3) {
  return 1;
 else{ 
  int x = 1, y = 1, count = 2; int fib;
  do{ 
    count++; 
    fib = y + x; 
    y = x;
    x = fib;
  } while (n != count);
  return fib; } }

Algorithm complexity grows when n gets very big. Complexity orders are classified in different types, according to their growing order:

O(1)		constant
O(log n) 	logarithmic
O(n)	 	linear
O(n·log n) 	linear-logarithmic
O(n^c)	 	power
O(c^n),n>1 	exponential
O(n!)	 	factorial
O(n^n)	 	exponential-factorial

The complexity order is an asymptotic measure used when n grows a lot; however, for small values, the expected result of applying certain algorithm with a certain order may vary. Imagine that the running time of an algorithm "f" takes 100n and, consequently, is of linear order O(n). Imagine now other algorithm "g" that takes n^2 and, consequently, is of quadratic order O(n^2). Asymptotically, "f" is better than "g", but this is not true for n>100. If we are not going to work ever with problems with n bigger than 100, it will be better to use the "g" algorithm.

The importance of the complexity order in the design or selection of algorithms is displayed in the next table, where the increment evolution in the running time when data size is multiplied by 2 is appreciated. As a general rule, it can be established that one should choose the less-order algorithm.

T(n) 		n=100	n=200
----------------------------------
c·log n		1h	1,20 h
c·n		1h	2h
c·n·log n		1h	2,30 h
c·n^2		1h	4h
c·n^3		1h	8h
c·2^n		1h	1,2·10^30 h

These algorithms are used to solve a problem by means of a systematic search, applying the brute-force until a solution is found or until no solution is possible to find. The search is divided into several partial searches that have themselves more searches; due to this, the nature of these algorithms is recursive:

function test (step : StepType) {
  repeat
    select_candidate
    if acceptable then {    
      anotate_candidate
      if incomplete_solution then {      
        test(next_step)
        if not sol_found then eliminate_candidate}      
      else {
        anotate_solution
        sol_found = true; }}
  until (found = true) or (no_more_candidates) }

Method of the 3 questions: Base-case Question: Does exist a non-recusive exit for the algorithm? Does the algorithm work correctly for this case? The-smaller Question: Every recursive call is invoked with a smaller case than the previous call? General-case Question: Is the solution correct for the non-base cases?

This technique consists on decomposing the original problem in several easier sub-problems, to solve them by means of an easy function. An example is the "QuickSort" algorithm, used to order arrays. This algorithm divides the array in 2 sub-arrays, to solve them separately, and then join them back. The needed time to order it is of quadratic order O(n^2). But if we apply the algorithm recursively, time is reduced till the complexity reaches the logarithmic order O(log n).

function divide_and_conquer(problem) {
  if the problem is trivial then   
    solve the problem;
  if not is trivial {
    decompose the problem in n smaller subproblems;           
    for i=1 to n do
      divide_and_conquer(subproblem_k);
    combine the n solutions;} }

This technique is used in some cases where recursion is not efficient because it makes redundant calculations. This is a method generally ascendent that solves small problems storing the partial values in a table to combine them and solve the bigger ones. For the Fibonacci series, an algorithm of order O(n) can be obtained with this technique. The pseudocode is as follows.

FUNC Fibonacci (n: NATURAL): NATURAL {
 table: ARRAY [0..n] OF NATURAL
 i: NATURAL
 if n <= 1 then 
  return 1
 else {
  table[0] = 1
  table[1] = 1
  for i = 2 TO n DO {
   table[i] = table[i-1] + table[i-2] }  
  return table[n]}}

The outer loop is executed n times, and the inner loop is executed 1, 2, 3, ... n times respectively. In total:

1 + 2 + 3 + ... + N = N*(1+N)/2  -> O(n^2)