Recursion Implementation and Complexity

Recursion from repetition

// traverse a singly linked list
temp = head;
while (temp != null){
  System.out.println(temp.value);
  temp = temp.getLink();
}

private void printAll(Node temp){
  if (temp != null){
    System.out.println(temp.value);
    printAll( temp.getLink() );
  }
}

public printAll(){
   printAll(head);
}

LList.printAll();

Complexity Analysis on Recursion

The formal approach to determining the big-O complexity of an algorithm is to set up recurrence relations and solve them.

For the recursive linear search we have

T(n) = T(n-1) + 1
T(0) = 1

That is, the time for searching an array of size n is the time to search an array of size n-1 plus the cost of searching (checking or comparing) the first element which is constant. The cost for searching an empty array is constant as well.

Solving:
T(n-1) = T(n-2) + 1,
so T(n) = T(n-1)+1 = [T(n-2) + 1] + 1 = T(n-2) + 2,
and T(n-2) = T(n-3) +1
so T(n) = T(n-2) + 2 = [T(n-3) + 1]  +1 = T(n-3) + 3,

and in general T(n) = T(n-i) + i;
so finally T(n) = T(0) + n = 1 + n = O(n)

 

 

Recursive Binary Search Analysis

For the recursive binary search we have

T(n) = 1 + T(n/2)
T(1) = 1

"The time to search n elements is a constant computation plus the time it takes to search n/2 elements."

Solving (rather intuitively) and assuming n is an even power of two (if not, we add dummy elements to the array to make it a size that is the next even power of two)

T(n/2) = 1  + T(n/4),
and T(n/4) = 1 + T(n/8), etc.

So T(n) = 1 + T(n/2) = 1 + 1 + T(n/4) = 1 + 1 + 1 + T(n/8)
and the pattern is T(n) = k + T(n/2^k)
now when k = log n, then n/(2^{log n})=n/n = 1,
so T(n) = log n + 1 = O(log n)

Recursive Complexity Patterns

When you have simple recurrence relations of the form

• T(n) = T(n-1) + f(n), then you have complexity of O(n*f(n))
• T(n) = T(n/k) + f(n), then you have complexity of O(log_k n * f(n))

Recursive factorial computation is of what complexity?

Consider the Fibonacci sequence recursive calculation:

F(1) = 1
F(2) = 1
F(n) = F(n-1)+F(n-2)

Its recurrence relation time is

T(1) = 1
T(2) = 1
T(n) = T(n-1) + T(n-2) + 1

Solving is a little beyond this course, but T(n) = O(2ⁿ) or "exponential"

 

Implementation of recursion

When a function (recursive or not) is called (invoked or activated) an activation frame on the call stack is created to hold:

1. space for all local, automatic (not static) variables
2. space for all formal parameters
3. the return address
4. any other system information about the function or the function that called it

The call stack is usually the system stack-- a special area of memory is reserved for the stack and one or more CPU registers are dedicated to managing the stack.

System.out.println( fact(3)); //original call

int fact(int n){ //n==3
   if (n==0) return 1;
   return n * fact(n-1);
}
    int fact(int n){ //n==2
      if (n==0) return 1;
      return n * fact(n-1);
   }
      int fact(int n){ //n==1
         if (n==0) return 1;
         return n * fact(n-1);
      }
         int fact(int n){ //n==0
            if (n==0) return 1;
            return n * fact(n-1);
         }
      int fact(int n){ //n==1
         if (n==0) return 1;
         return n * 1;
      }
   int fact(int n){ //n==2
      if (n==0) return 1;
      return n * 1;
   }
int fact(int n){ //n==3
   if (n==0) return 1;
   return n * 2;
}
return 6;

Revisit of the system stack for recursion

A stack is used to hold activation records for each method. Further, each invocation of a method during recursion causes an activation record to be pushed on the system stack.

Consider, then the cost of recursion with respect to local variables.

Call and return process

When a method/function is called

1. An activation record is created; its size depends on the number and size of the local variables and parameters.
2. The Base Pointer value is saved in the special location reserved for it
3. The Program Counter value is saved in the Return Address location
4. The Base Pointer is now reset to the new base (top of the call stack prior to the creation of the AR)
5. The Program Counter is set to the location of the first bytecode of the method being called
6. Copies the calling parameters into the Parameter region
7. Initializes local variables in the local variable region

While the method executes, the local variables and parameters are simply found by adding a constant associated with each variable/parameter to the Base Pointer.

When a method returns

1. Get the program counter from the activation record and replace what's in the PC
2. Get the base pointer value from the AR and replace what's in the BP
3. Pop the AR entirely from the stack.