B - Data Structures and Algorithms > Unit 4 Chapter 6 Recursion Code > Flashcards

Unit 4 Chapter 6 Recursion Code Flashcards

(8 cards)

Study These Flashcards
1
Q

triangle

A 
import java.io.*;
////////////////////////////////////////////////////////////////
class TriangleApp
   {
   static int theNumber;

   public static void main(String[] args) throws IOException
      {
      System.out.print("Enter a number: ");
      theNumber = getInt();
      int theAnswer = triangle(theNumber);
      System.out.println("Triangle="+theAnswer);
      }  // end main()
//-------------------------------------------------------------
   public static int triangle(int n)
      {
      if(n==1)
         return 1;
      else
         return  ( n + triangle(n-1) );
      }
//-------------------------------------------------------------
   public static String getString() throws IOException
      {
      InputStreamReader isr = new InputStreamReader(System.in);
      BufferedReader br = new BufferedReader(isr);
      String s = br.readLine();
      return s;
      }
//-------------------------------------------------------------
   public static int getInt() throws IOException
      {
      String s = getString();
      return Integer.parseInt(s);
      }
//--------------------------------------------------------------
   }  // end class TriangleApp
////////////////////////////////////////////////////////////////
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

towers

A 
////////////////////////////////////////////////////////////////
class TowersApp
   {
   static int nDisks = 3;

   public static void main(String[] args)
      {
      doTowers(nDisks, 'A', 'B', 'C');
      }
   //-----------------------------------------------------------
   public static void doTowers(int topN,
                               char src, char inter, char dest)
      {
      if(topN==1)
         System.out.println("Disk 1 from " + src + " to "+ dest);
      else
         {
         doTowers(topN-1, src, dest, inter);   // src to inter

         System.out.println("Disk " + topN +   // move bottom
                            " from " + src + " to "+ dest);
         doTowers(topN-1, inter, src, dest);   // inter to dest
         }
      }
//-------------------------------------------------------------
   }  // end class TowersApp
////////////////////////////////////////////////////////////////
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

stackTriangle2

A 
import java.io.*;                 // for I/O
////////////////////////////////////////////////////////////////
class StackX
   {
   private int maxSize;        // size of stack array
   private int[] stackArray;
   private int top;            // top of stack
//--------------------------------------------------------------
   public StackX(int s)        // constructor
      {
      maxSize = s;
      stackArray = new int[maxSize];
      top = -1;
      }
//--------------------------------------------------------------
   public void push(int p)     // put item on top of stack
      { stackArray[++top] = p; }
//--------------------------------------------------------------
   public int pop()            // take item from top of stack
      { return stackArray[top--]; }
//--------------------------------------------------------------
   public int peek()           // peek at top of stack
      { return stackArray[top]; }
//--------------------------------------------------------------
   public boolean isEmpty()    // true if stack is empty
      { return (top == -1); }
//--------------------------------------------------------------
   }  // end class StackX
////////////////////////////////////////////////////////////////
class StackTriangle2App
   {
   static int theNumber;
   static int theAnswer;
   static StackX theStack;

   public static void main(String[] args) throws IOException
      {
      System.out.print("Enter a number: ");
      System.out.flush();
      theNumber = getInt();
      stackTriangle();
      System.out.println("Triangle="+theAnswer);
      }  // end main()
//-------------------------------------------------------------
   public static void stackTriangle()
      {
      theStack = new StackX(10000);    // make a stack

  theAnswer = 0;                   // initialize answer
      while(theNumber > 0)             // until n is 1,
         {
         theStack.push(theNumber);     // push value
         --theNumber;                  // decrement value
         }
      while( !theStack.isEmpty() )     // until stack empty,
         {
         int newN = theStack.pop();    // pop value,
         theAnswer += newN;            // add to answer
         }
      }
//-------------------------------------------------------------
   public static String getString() throws IOException
      {
      InputStreamReader isr = new InputStreamReader(System.in);
      BufferedReader br = new BufferedReader(isr);
      String s = br.readLine();
      return s;
      }
//-------------------------------------------------------------
   public static int getInt() throws IOException
      {
      String s = getString();
      return Integer.parseInt(s);
      }
//--------------------------------------------------------------
   }  // end class StackTriangle2App
////////////////////////////////////////////////////////////////
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

stackTriangle

A 
import java.io.*;                 // for I/O
////////////////////////////////////////////////////////////////
class Params     // parameters to save on stack
   {
   public int n;
   public int returnAddress;

   public Params(int nn, int ra)
      {
      n=nn;
      returnAddress=ra;
      }
   }  // end class Params
////////////////////////////////////////////////////////////////
class StackX
   {
   private int maxSize;         // size of StackX array
   private Params[] stackArray;
   private int top;             // top of stack
//--------------------------------------------------------------
   public StackX(int s)         // constructor
      {
      maxSize = s;              // set array size
      stackArray = new Params[maxSize];  // create array
      top = -1;                 // no items yet
      }
//--------------------------------------------------------------
   public void push(Params p)   // put item on top of stack
      {
      stackArray[++top] = p;    // increment top, insert item
      }
//--------------------------------------------------------------
   public Params pop()          // take item from top of stack
      {
      return stackArray[top--]; // access item, decrement top
      }
//--------------------------------------------------------------
   public Params peek()         // peek at top of stack
      {
      return stackArray[top];
      }
//--------------------------------------------------------------
   }  // end class StackX
////////////////////////////////////////////////////////////////
class StackTriangleApp
   {
   static int theNumber;
   static int theAnswer;
   static StackX theStack;
   static int codePart;
   static Params theseParams;
//-------------------------------------------------------------
   public static void main(String[] args) throws IOException
      {
      System.out.print("Enter a number: ");
      theNumber = getInt();
      recTriangle();
      System.out.println("Triangle="+theAnswer);
      }  // end main()
//-------------------------------------------------------------
   public static void recTriangle()
      {
      theStack = new StackX(10000);
      codePart = 1;
      while( step() == false)  // call step() until it's true
         ;                     // null statement
      }
//-------------------------------------------------------------
   public static boolean step()
      {
      switch(codePart)
         {
         case 1:                              // initial call
            theseParams = new Params(theNumber, 6);
            theStack.push(theseParams);
            codePart = 2;
            break;
         case 2:                              // method entry
            theseParams = theStack.peek();
            if(theseParams.n == 1)            // test
               {
               theAnswer = 1;
               codePart = 5;   // exit
               }
            else
               codePart = 3;   // recursive call
            break;
         case 3:                              // method call
            Params newParams = new Params(theseParams.n - 1, 4);
            theStack.push(newParams);
            codePart = 2;  // go enter method
            break;
         case 4:                              // calculation
            theseParams = theStack.peek();
            theAnswer = theAnswer + theseParams.n;
            codePart = 5;
            break;
         case 5:                              // method exit
            theseParams = theStack.peek();
            codePart = theseParams.returnAddress; // (4 or 6)
            theStack.pop();
            break;
         case 6:                              // return point
            return true;
         }  // end switch
      return false;
      }  // end triangle
//-------------------------------------------------------------
   public static String getString() throws IOException
      {
      InputStreamReader isr = new InputStreamReader(System.in);
      BufferedReader br = new BufferedReader(isr);
      String s = br.readLine();
      return s;
      }
//-------------------------------------------------------------
   public static int getInt() throws IOException
      {
      String s = getString();
      return Integer.parseInt(s);
      }
//--------------------------------------------------------------
   }  // end class StackTriangleApp
////////////////////////////////////////////////////////////////
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

mergeSort

A 
////////////////////////////////////////////////////////////////
class DArray
   {
   private long[] theArray;          // ref to array theArray
   private int nElems;               // number of data items
   //-----------------------------------------------------------
   public DArray(int max)            // constructor
      {
      theArray = new long[max];      // create array
      nElems = 0;
      }
   //-----------------------------------------------------------
   public void insert(long value)    // put element into array
      {
      theArray[nElems] = value;      // insert it
      nElems++;                      // increment size
      }
   //-----------------------------------------------------------
   public void display()             // displays array contents
      {
      for(int j=0; j< theArray[highPtr] )
            workSpace[j++] = theArray[lowPtr++];
         else
            workSpace[j++] = theArray[highPtr++];

      while(lowPtr <n; j++)
         theArray[lowerBound+j] = workSpace[j];
      }  // end merge()
   //-----------------------------------------------------------
   }  // end class DArray
////////////////////////////////////////////////////////////////
class MergeSortApp
   {
   public static void main(String[] args)
      {
      int maxSize = 100;             // array size
      DArray arr;                    // reference to array
      arr = new DArray(maxSize);     // create the array

  arr. insert(64);                // insert items
  arr. insert(21);
  arr. insert(33);
  arr. insert(70);
  arr. insert(12);
  arr. insert(85);
  arr. insert(44);
  arr. insert(3);
  arr. insert(99);
  arr. insert(0);
  arr. insert(108);
  arr. insert(36);

  arr. display();                 // display items
  arr. mergeSort();               // merge sort the array
      arr.display();                 // display items again
      }  // end main()
   }  // end class MergeSortApp
////////////////////////////////////////////////////////////////
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

merge

A 
////////////////////////////////////////////////////////////////
class MergeApp
   {
   public static void main(String[] args)
      {
      int[] arrayA = {23, 47, 81, 95};
      int[] arrayB = {7, 14, 39, 55, 62, 74};
      int[] arrayC = new int[10];

      merge(arrayA, 4, arrayB, 6, arrayC);
      display(arrayC, 10);
      }  // end main()
   //-----------------------------------------------------------
                                       // merge A and B into C
     public static void merge( int[] arrayA, int sizeA,
                               int[] arrayB, int sizeB,
                               int[] arrayC )
      {
      int aDex=0, bDex=0, cDex=0;

  while(aDex < sizeA && bDex < sizeB)  // neither array empty
     if( arrayA[aDex] < arrayB[bDex] )
        arrayC[cDex++] = arrayA[aDex++];
     else
        arrayC[cDex++] = arrayB[bDex++];

  while(aDex < sizeA)                  // arrayB is empty,
     arrayC[cDex++] = arrayA[aDex++];  // but arrayA isn't
      while(bDex < sizeB)                  // arrayA is empty,
         arrayC[cDex++] = arrayB[bDex++];  // but arrayB isn't
      }  // end merge()
   //-----------------------------------------------------------
                                       // display array
   public static void display(int[] theArray, int size)
      {
      for(int j=0; j);
      }
   //-----------------------------------------------------------
   }  // end class MergeApp
////////////////////////////////////////////////////////////////
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

binary search

A 
////////////////////////////////////////////////////////////////
class ordArray
   {
   private long[] a;                 // ref to array a
   private int nElems;               // number of data items
   //-----------------------------------------------------------
   public ordArray(int max)          // constructor
      {
      a = new long[max];             // create array
      nElems = 0;
      }
   //-----------------------------------------------------------
   public int size()
      { return nElems; }
   //-----------------------------------------------------------
   public int find(long searchKey)
      {
      return recFind(searchKey, 0, nElems-1);
      }
   //-----------------------------------------------------------
   private int recFind(long searchKey, int lowerBound,
                                         int upperBound)
      {
      int curIn;

      curIn = (lowerBound + upperBound ) / 2;
      if(a[curIn]==searchKey)
         return curIn;              // found it
      else if(lowerBound > upperBound)
         return nElems;             // can't find it
      else                          // divide range
         {
         if(a[curIn] < searchKey)   // it's in upper half
            return recFind(searchKey, curIn+1, upperBound);
         else                       // it's in lower half
            return recFind(searchKey, lowerBound, curIn-1);
         }  // end else divide range
      }  // end recFind()
   //-----------------------------------------------------------
   public void insert(long value)    // put element into array
      {
      int j;
      for(j=0; j value)            // (linear search)
            break;
      for(int k=nElems; k>j; k--)    // move bigger ones up
         a[k] = a[k-1];
      a[j] = value;                  // insert it
      nElems++;                      // increment size
      }  // end insert()
   //-----------------------------------------------------------
   public void display()             // displays array contents
      {
      for(int j=0; j + searchKey);
      }  // end main()
   }  // end class BinarySearchApp
////////////////////////////////////////////////////////////////
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

anagrm

A 
///////////////////////////////////////////////////////////////
class AnagramApp
   {
   static int size;
   static int count;
   static char[] arrChar = new char[100];
   //-----------------------------------------------------------
   public static void main(String[] args) throws IOException
      {
      System.out.print("Enter a word: ");    // get word
      String input = getString();
      size = input.length();                 // find its size
      count = 0;
      for(int j=0; j< 99)
         System.out.print(" ");
      if(count < 9)
         System.out.print(" ");
      System.out.print(++count + " ");
      for(int j=0; j);
      }
   //-----------------------------------------------------------
   public static String getString() throws IOException
      {
      InputStreamReader isr = new InputStreamReader(System.in);
      BufferedReader br = new BufferedReader(isr);
      String s = br.readLine();
      return s;
      }
   //-----------------------------------------------------------
   }  // end class AnagramApp
////////////////////////////////////////////////////////////////
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
B - Data Structures and Algorithms
flashcards
Decks in class (25)
# Cards
Brainscape helps you reach your goals faster, through stronger study habits.
© 2026 Bold Learning Solutions. Terms and Conditions