Recurrence Relation and Recursion

Fibonacci problems

  • recursive calls
  • we can write T(n) like this: T(n) = T(n - 1) + T(n - 2) + O(1) . For the base case, we have T(0) = O(1), T(1) = O(1)
Recursive Accessor Methods
1 print the linked list in reverse order
  public static void reversePrint (LN l)
  {
    if (l == null)
      return;
    else {
      reversePrint(l.next);
      System.out.println(l.value);
    };
  }
note, if use iterative method, we need stack and iteration.


2 search the linked list node
  public static LN search (LN l, int value)
  {
    if (l == null || l.value == value)
      return l;
    else
      return search(l.next, value);
  }


Recursive Mutator Methods
Recursive mutator methods follow a pattern in which they return a reference to the mutated linked list 
(instead of being void); such a generalization allows for a simple recursive implementation of the method. 
This approach takes a bit of getting used to, but it is a pattern that is used repeatedly here and in the 
recursive processing of tree with mutators.
1 insertRear
  public static LN insertRear (LN l, int value)
  {
    if (l == null)
      return new LN(value,null);
    else {
      l.next = insertRear(l.next, value);
      return l;
    }
  }

2 insertOrdered
  public static LN insertOrdered (LN l, int value)
  {
    if (l == null || value < l.value)
      return new LN(value,l);
    else {
      l.next = insertOrdered(l.next, value);
      return l;
    }
  }

3 removeFirst
  public static LN removeFirst(LN l, int value)
  {
    if (l == null)
      return null;
    else
      if (l.value == value)
        return l.next;
      else {
        l.next = removeFirst(l.next, value);
        return l;
      }
  }

4 removeAll
  public static LN removeAll(LN l, int value)
  {
    if (l == null)
      return null;
    else
      if (l.value == value)
        return removeAll(l.next,value);
      else {
        l.next = removeAll(l.next, value);
        return l;
      }
  }

results matching ""

    No results matching ""