Recursion, PPT, Semester, Engineering - Computer Science Engineering (CSE) PDF Download

Recursion
(With applications to Searching and Sorting)

•Definition of a Recursion

•Simple Examples of Recursion

•Conditions for Recursion to Work

•How Recursion Works Internally

•Binary Search

•Merge Sort

Recursion.............................................................NextSlide.......................................................................

Definition of Recursion

•A function is said to be recursive if it calls itself

//Precondition: n is a non-negative integer

//Postcondition: returns n!, which is 1*2*3*…*n; 0!=1

// Principle for recursion: n!=(n-1)! * n.

long factorial(int n){

  if (n==0) return 1;

  long m=factorial(n-1);  // recursion

  m *=n;

  return m;

}

Recursion.............................................................NextSlide.......................................................................

One Example of Recursion: Investment Accounts

•Suppose you invest in an account $x every year, and that the account grows at an interest rate of 8%.

•Write a function that computes how much money you have in your account at the end of year n.

•Call S(n) the amount of money in the account at the end of year n.

Recursion...........................................................NextSlide.......................................................................

Investment Example (contd.)

The math:

S(n) = S(n-1) + interest of past year + new deposit $x

S(n)=S(n-1)+0.08*S(n-1)+x

S(n)=1.08*S(n-1) + x

Note that S(0)=x (the first deposit when opening the acct)

//The recursive code:

//Precondition: n is a non-negative integer

//Postcondition: returns S(n) = 1.08*S(n-1) + x; S(0)=x

double S(int n, double x){

  if (n==0) return x;

  double lastYearS = S(n-1,x);  // recursion

  return (1.08*lastYearS+x); 

}

Recursion.........................................................NextSlide.......................................................................

Another Recursion Example: Finding the Minimum in an Array

// Precondition: the input is a a double array x[ ] of at least end

// elements. start and end are nonnegative integer indexes

// marking the portion of x[ ] over which to find the minimum.

// end >= start;

// Postcondition: returns the smallest value in x[ ].

// Recursion principle: if you we have the minimum of the 1st

// half of x and the minimum of the 2nd half of x, then the

// global minimum is the smaller of those two minimums

double min(double x[ ], int start, int end){

  // …. On the next slide

}

Recursion.............................................................NextSlide.......................................................................

The Minimum Example (Contd.)

double min(double x[ ], int start, int end){

  assert(end >= start && start >=0);

  if (end == start)          // one number to minimize over

  return x[start];

   int mid=(start+end)/2;               // mid-point index

   double min1=min(x, start, mid);    // 1st recursive call

   double min2=min(x, mid+1, end); // 2nd recursive call

   if (min1 <= min2)

   return min1;

  else

   return min2; 

}

Recursion............................................................NextSlide.......................................................................

Conditions for Valid Recursion

•For recursive functions to work, the following two conditions must be met:

–The input (parameters) of every recursive call must be smaller in value or size than the input of the original function

–There must be a basis step where the input value or size is

•the smallest possible, and

•in which case the processing is non-recursive.

Recursion...........................................................NextSlide.......................................................................

Ilustration of the Conditions

long factorial(int n){

  if (n==0) return 1; // basis step. Input value n is minimum (0).

  long m=factorial(n-1);  // recursion. Input value of recursive call is n-1<n

  m *=n;

  return m;

}

double S(int n, double x){

     if (n==0) return x; // basis step. Input value n is minimum (0).

     double lastYearS = S(n-1,x);

    // recursion. First-input value of recursive call is n-1<n

     return (1.08*lastYearS+x); 

}

Recursion..........................................................NextSlide.......................................................................

llustration of the Conditions (Contd.)

double min(double x[ ], int start, int end){

  assert(end >= start && start >=0);

  if (end == start)          // Basis step. Input size is minimum = 1.

  return x[start];  // No recursion

  int mid=(start+end)/2;               // mid-point index

  double min1=min(x, start, mid);    // 1st recursive call

  double min2=min(x, mid+1, end); // 2nd recursive call

  // In both recursive calls, the input size is half the original, and so less. 

  if (min1 <= min2)

   return min1;

  else

   return min2; 

}

Recursion.............................................................NextSlide.......................................................................

How Recursion Works Internally

•It is illustrated in class on the factorial function and the min function

Recursion..........................................................NextSlide.......................................................................

How to Think Recursively

•When coding, do not concern yourself how recursion is unfolding during execution

•Rather, think of yourself as a boss, and treat each recursive call as an order to one of your trusted subordinates to do something.

•As a boss, you need not worry how the subordinate does their work. Instead, take the outcome of their work

•Finally, take the outcome of the subordinate’s work, and use it to compute by yourself the final result.

Recursion..........................................................NextSlide.......................................................................

llustration of Recursive Thinking

double min(double x[ ], int start, int end){

  assert(end >= start && start >=0);

  if (end == start)                // Basis step.

  return x[start];  // The boss does the basis step

  int mid=(start+end)/2;               // mid-point index

  double min1=min(x, start, mid);    // subordinate produces min1

  double min2=min(x, mid+1, end); // subordinate produces min2

  // The two recursive calls are the work of  “subordinates”. Don’t

  // worry how the subordinates do their work.

  if (min1 <= min2)

   return min1;

  else

   return min2; 

}

// You, the boss, take the

// outcome min1 and min2

// from subordinates, and use

// them to get the final result.

Recursion.........................................................NextSlide.......................................................................

Binary Search

•Input:

–A sorted array X[ ] of size n

–A value b to be searched for in X[ ]

•Output:

–If b is found, the index k where X[k]=b

–If b is not found, return -1

•Definition: An X[ ] is said to be sorted if:

  X[0] ≤ X[1] ≤ X[2] ≤ … ≤ X[n-1]

Recursion...........................................................NextSlide.......................................................................

Binary Search: Method

•The method is recursive:

•Compare b with the middle value X[mid]

•If b = X[mid], return mid

•If b < X[mid], then b can only be in the left half of X[ ], because X[ ] is sorted. So call the function recursively on the left half.

•If b > X[mid], then b can only be in the right half of X[ ], because X[ ] is sorted. So call the function recursively on the right half.

Recursion............................................................NextSlide.......................................................................

Ilustration of Binary search

Recursion.........................................................NextSlide.......................................................................

The Recursive Code of Binary Search

int binarySearch(double b, double X[], int left, int right){

  if (left == right)

  if (b==X[left]) return left;

  else return -1;

  int mid = (left+right)/2;

  if (b==X[mid]) return mid;

  if (b < X[mid]) return binarySearch (b, X, left, mid-1);

  if (b > X[mid]) return binarySearch(b, X, mid+1, right);

}

Recursion.......................................................NextSlide.......................................................................

Time Complexity of binarySearch

•Call T(n) the time of binarySearch when the array size is n.

•T(n) = T(n/2) + c, where c is some constant representing the time of the basis step and the last if-statement to choose between min1 and min2

•Assume for simplicity that n= 2k. (so k=log2 n)

•T(2k)=T(2k-1)+c=T(2k-2)+c+c=T(2k-3)+c+c+c = … = T(20)+c+c+…c=T(1)+kc=O(k)=O(log n)

•Therefore, T(n)=O(log n).

Recursion...........................................................NextSlide.......................................................................

MergeSort

•The general problem of sorting is to take as input an unordered array X[ ], and give as output the same set of data but sorted in increasing order

•Example:

–Input: 3 5 2 7 10 8 20 15 14 3 -1 2 -5

–Output: -5 -1 2 2 3 3 5 7 8 10 14 15 20

•We are interested in developing an algorithm that does the sorting.

Recursion..........................................................NextSlide.......................................................................

MergeSort: Recursive Sorting

A recursive sorting function works as follows:

1.Make a recursive call to the sorting function to sort the first half of the input array

2.Make another recursive call to sort the 2nd half of the input array

3.Finally, merge the two sorted halves into a single fully sorted array.

Recursion..........................................................NextSlide.......................................................................

How to Merge Two Sorted Arrays

•Say Y[ ] and Z[ ] are two sorted arrays to be merged into a single sorted array

•Call the first element of an array the head

•While both arrays Y and Z are non-empty, repeat the following steps:

–Compare the two heads of Y and Z

–Remove the smaller head and put it next in the output

•Now either Y or Z is empty. Move the non-empty array to the end of output, and stop.

•The output is now fully sorted.

Recursion........................................................NextSlide.......................................................................

Illustration of Merging

•(In class)

Recursion.........................................................NextSlide.......................................................................

Code for Merge

void merge(double X1[ ], int left1, int right1,  //merge X1[left1..right1]

          doubleX2[ ], int left2, int right2,  // and X2[left2..right2]

          doubleX, int left)  {         // to X[left…]

    int i1 = left1; int i2=left2; int i= left; // heads of X1, X2, X.

    while (i1 <=  right1 && i2  <=  right2)

  if (X1[i1] <= X2[i2]) {X[i]=X1[i1]; i1++; i++;}

  else {X[i]=X2[i2]; i2++; i++;}

    if (i1<right1) // copy leftovers of X1 to the end of X

        while (i1<= right1) {X[i]=X1[i1]; i1++; i++;}

    if (i2<right2) // copy leftovers of X2 to the end of X

        while (i2<= right2) {X[i]=X2[i2]; i2++; i++;}

}

Recursion............................................................NextSlide.......................................................................

Code for MergeSort

void mergeSort(double X[ ], doubleY[ ], int left, int right){

    if (left==right) {Y[left] = X[left]; return;}

    int mid = (left+right)/2;

    double Z[right+1];

    // next, sort left half of X and put the result in left half of Z

    mergeSort(X,Z,left,mid);

    // next, sort right half of X and put the result in right half of Z

    mergeSort(X,Z,mid+1,right);

    // next, merge the two halves of Z and put result in Y

    merge(Z,left,mid, Z,mid+1,right, Y,left);

}

Recursion...........................................................NextSlide.......................................................................

Illustration of mergeSort

•(In class)

Recursion..........................................................NextSlide.......................................................................

Additional Things for YOU to Do

•Modify binarySearch so that even if the item b is not found, the function returns the index k where X[k] < b<X[k+1].

•Write a function that inserts a new element b into an already sorted array, assuming the array has additional room for a new element. Hint: use binarySearch as modified above to find where b should be inserted, then shift the right portion of the array by one position to the right, and then insert the element.

Recursion..........................................................NextSlide.......................................................................

More Things You can Do

•Write a function (called partition) that takes as input an unsorted array X to do the following:

–Let b=the first element of X

–Move the data around inside X so that at the end b lands in some position k where X[i] ≤ b for all i < k, and X[i] > b for all i > k.

•Hint: Have an empty array Y of same size as X. Scan the array X; for each element X[i], if X[i] ≤ b, insert X[i] in the left end of Y, but if X[i]>b, insert X[i] in the right end of Y. At the end, you can copy Y onto X.

•Use partition to develop another recursive sorting algorithm: 1. call partition; 2. call recursively on X[0..k-1]; 3. call recursively on X[k+1..n-1].