Recursion

Pseudocode Examples

• Factorial

   
     if N < 1 then
        N! = 1
     else
        N! = N * (N-1)!
  

• Multiplication

  	
     if b = 1 then
        a * b = a
     else
        a * b = a * (b-1) + a
  

• Fibonacci Numbers

     if n = 0 or n = 1 then
        fib(n) = n
     else
        fib(n) = fib(n-2) + fib(n-1)
  

• Binary Search

      if low > high then
         return 0
      mid = (low + high)/2
      if x = a[mid] then
        return mid
      if x < a[mid] then
        return(search(x, low, mid-1, a))
      else
        return(search(x, mid+1, high, a))
  

Good Uses of Recursion

Recursive Data Structure

   def: recursive string S

   1. if S is empty

        or

   2. if S is made up of a single char, followed by S` and S` is a string


      "abc"

      'a' "bc"

      'b' "c"

          ""

Return to CIS 350 Index Page