Chapter 14
Recursion

1. Recursion is repetitive process in which an algorithm calls itself.

2. Every recursive call either solve part of the problem or reduce the size of the problem.

3. Factorial example.

   int fact(int n)
   {
       if(n == 0 ) return 1;
       else return n * fact (n-1);
   }
   

4. Non Tail Recursion

   void reverse()
   {
      char ch;
      cin.get(ch);
      if(ch != '\n') {
         reverse();
         cout.put(ch);
      }
   }
   

5. Excessive Recursion

   int Fib( int n)
   {
      if (n < 2 ) return n;
      else return Fib(n-2) + Fib (n-1);
   }
   

6. On a recursive data structure.
   1. Code

      #include <string>
      #include <windows.h>
      #include <iostream>
      
      
      using namespace std;
      
      void ScanDir(string dirname, int indent)
      {
          bool            fFinished;
          HANDLE          hList;
          string          NowDir;
          string          NetxDir;
          WIN32_FIND_DATA FileData;
          string          space_over(indent,' ');
      
          // Get the proper directory path
          NowDir=dirname + "\\*";
       
          // Get the first file
          hList = FindFirstFile(NowDir.c_str(), &FileData);
          if (hList == INVALID_HANDLE_VALUE)
              cout << "No files found" << endl;
          else
          {
              // Traverse through the directory structure
              fFinished = false;
              while (!fFinished)
              {
                  //  don't print . and ..
                  if ((strcmp(FileData.cFileName, ".") != 0) &&
                      (strcmp(FileData.cFileName, "..") != 0))
                  {
                      cout << space_over << FileData.cFileName <<endl;
                     // Check the object is a directory or not
                     if (FileData.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY)
                     {
                          // Get the full path for sub directory
                          NetxDir=dirname + "\\";
      		    NetxDir+=FileData.cFileName;
                          // Recurse to sub dir
                          ScanDir(NetxDir, indent+3);
      	        }
                  }
                  if (!FindNextFile(hList, &FileData))
                      if (GetLastError() == ERROR_NO_MORE_FILES)
                         fFinished = true;
               }
          }
          FindClose(hList);
      }
      
      void main()
      {
          string DirStart("C:\\ask");
          ScanDir(DirStart, 0);
          cout << "Done" << endl;
      }
      

   2. Execution

      Assignment1.zip
      assn1.31130DEFANGED-zip
      Bass
         Random Numbers
            cRandomInteger.cpp
            cRandomInteger.h
            Debug
               BuildLog.htm
               cRandomInteger.obj
               Main.obj
               Random Numbers.exe
               Random Numbers.ilk
               Random Numbers.pdb
               vc70.idb
               vc70.pdb
            Main.cpp
            Random Numbers.ncb
            Random Numbers.sln
            Random Numbers.suo
            Random Numbers.vcproj
         Random Numbers.19934DEFANGED-zip
      datastrctzip.zip
      exam1.rtf
      exam2.rtf
      exam3.rtf
      file_id.diz
      Nelson
         assn1
            assn1.cxx
            output.txt
            random.cxx
            random.h
      Peschke
         a1_output1.gif
         a1_output2.gif
         main.cpp
         pseudorandom.cpp
         pseudorandom.h
      programs.rtf
      rc
      syllabus.rtf
      Done
      Press any key to continue
      

7. Backtracking
   1. Header file

      #ifndef QUEEN1
      #define QUEEN1
      
      class queen {
      private:
      	int board[9];	// actually uses 1..8
      
      public:
      	queen();	        // constructor
      	bool safe(int);     //
      	bool placequeen(int); //
      	void printboard();
      };
      #endif
      

   2. Implementation functions

      #include "queens.h"
      #include <cstdlib>
      #include <iostream>
      using namespace std;
      #include <string>
      
      queen::queen() // constructor
      {
      	int i;
      	for(i=0;i<9;i++) board[i]=0;  // clear the board;
      }
      
      bool queen::safe(int here)
      {
      //
      //  checks to see if the placing on queen here
      //  is safe.  Not safe in same column or same
      //  diagonal as another quuen
      
          bool answer = true;
          int i;
          if (board[here] == 0) answer=false;
          if (board[here] > 8 ) answer=false;
          for(i=1;answer && i<here;i++)  {
             if(board[here] == board[i]) answer=false;  // same column
             // check diagonal
             if(here-i == abs(board[here]-board[i])) answer=false;
          }
          return answer;
      }
      
      bool queen::placequeen(int thisqueen)
      {
          int attempt=1;
          while(1) {
      	board[thisqueen]=attempt;
      	if(safe(thisqueen)) {
                 if(thisqueen == 8) return true;
                 if (placequeen(thisqueen+1)) return true;
                 else attempt++;
      	} else {
      		attempt++;
      		if (attempt > 8) return false;
      	}
           }
      }
      
      void queen::printboard()
      {
      	char a[]=" ABCDEFGH";
      	static int solution=0;
      	int i,j;
      	solution++;
      	cout << "Solution : " << solution << " : ";
      	for (i=1;i<9;i++)
      		cout << a[i] <<  board[i] << " ";
      	cout << endl;
      	// pretty print
      	for(i=1;i<9;i++) {
      		string line=" ........";
      		line[board[i]]='Q';
      		cout << line << endl;
      	}
      }
      

   3. Usage

      #include <iostream>
      #include <stdlib.h>
      #include "queens.h"
      
      int# safe( int, int[]);
      void print(int[],int);
      
      using namespace std;
      
      void main()
      {
      	queen what;
      	if(what.placequeen(1))
      		what.printboard();
      
      
      }
      

   4. Execution

      Solution : 1 : A1 B5 C8 D6 E3 F7 G2 H4
       Q.......
       ....Q...
       .......Q
       .....Q..
       ..Q.....
       ......Q.
       .Q......
       ...Q....
      Press any key to continue