25-2 • Recursive Functions • Related Chapter: ABC 5.14, 5.1525-3 Recursive functions are defined in terms of themselves; i.e., a function is recursive if it contains calls back to itself or to another function that calls the original function. Recursive programming usually requires more memory and runs more slowly than non-recursive programs. This is due to the cost of implementing the “stack”. However, recursion is often a natural way to define a problem.25-4 1. Problem Definition Write a factorial function. 0! = 1 and n! = n*(n-1)!. Use “recursion” to implement the factorial function. 2. Refine, Generalize, Decompose the problem definition (i.e., identify sub-problems, I/O, etc.) Input = Non-negative integers as input. Output= return the factorial of the input value. Note: that 69! = 1.711224524... x 1098 so our function will only work for small integer values. It would be better to return a value of data-type double (Why?)25-5 double fact(int n) { if (n = =0) /* Voom! */ return 1.0; else return (n * fact(n - 1)); /* recursive call */ } In main we can call the factorial function by the following command: printf("%lf", fact(3)); or by (if x is of data-type int and y is of data-type double) : x = 3; y = fact(x);(push) return ( 3 * fact(2)); (n = 3) (push) return ( 2 * fact(1)); (n = 2) (push) return ( 1 * fact(0)); (n = 1) (push/pop) return 1.0; (n = 0) (pop) return ( 1 * 1.0); (n = 1) (pop) return ( 2 * 1.0); (n = 2) (pop) return ( 3 * 2.0); (n = 3) return 1.0; (n = 0) return ( 1 * fact(0)); (n = 1) return ( 2 * fact(1)); (n = 2) return ( 3 * fact(2)); (n = 3) (STACK) return ( 1 * 1.0); (n = 1) return ( 2 * fact(1)); (n = 2) return ( 3 * fact(2)); (n = 3) return ( 2 * 1.0); (n = 2) return ( 3 * fact(2)); (n = 3) return ( 3 * 2.0); (n = 3) printf("%lf", fact(3) );25-7 1. Problem Definition Write a solve_maze function. Read the maze from a file, “maze.txt” and display one path that traverses the maze. Use “recursion” to implement the maze function. 2. Refine, Generalize, Decompose the problem definition (i.e., identify sub-problems, I/O, etc.) Input = The file “maze.txt” contains the following ********** * * **** * *O* * * *** * * *X* * ** *** * * * * * *** ** * * * * ********** Your program will have to find its way through a 10x10 maze where the symbols “ * ” , “O” and “X” denote: “ * ” are solid walls through which you cannot travel "O" denotes the starting position, "X" is the exit for which you are looking for* * * * * * * * * * * * * * * * * * O * * * * * * * * * X * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *25-9 2. Refine, Generalize, Decompose the problem definition Input (continued): Read the maze into the 2D array, ********** * * **** * *O* * * *** * * *X* * ** *** * * * * * *** ** * * * * ********** char maze[NUMROWS][NUMCOLS]; where NUMROWS and NUMCOLS are constants with value 10. The upper left-hand corner of the maze has the value maze[0][0] . If we want to test whether the cell in the fourth row and fourth column contains a wall then it's enough to use an if statement like this: if (maze[3][3] == ‘ * ')25-10 2. Refine, Generalize, Decompose the problem definition Output : Display a solution as follows: ********** * OOOOO* ****O* *O* * *O* *** * *O* *X* * **O***O* * OO *O* * ***O**O* * * OOOO* **********25-11 3. Develop Algorithm (processing steps to solve problem) Step 1 Read in the “maze” and find the starting Row and Column (the position of the “O”). Use variables “curRow” and “curCol” to keep track of the current position as we traverse through the maze (the 2D matrix “maze”). Step 2 Display the maze. Step 3 Check to see if current position is an “X” then we are done. Otherwise first try to go up and if not then down and if not then left and if not then right and if you can go up/down/left/right then go back to Step 2. Otherwise, go back to the previous position [curRow,curCol] and try another direction.#include <stdio.h> #include <stdlib.h> #define NUMROWS 10 #define NUMCOLS 10 /* prototypes */ int read_maze (char[][], int *, int *); void display_maze (char[][]); void solve_maze (char[][], int, int);void main (void) { int startRow, startCol; /* Starting point in maze. */ char maze[NUMROWS][NUMCOLS]; /* Stores maze read from input file. */ if (read_maze(maze, &startRow, &startCol) == 0) { printf ("Error reading maze from file maze.txt!\n"); return; } solve_maze(maze, startRow, startCol); } /*end of main */void solve_maze(char maze[][NUMCOLS], int curRow, int curCol) { int i; display_maze(maze); /* Check if solution found. */ if ((maze[curRow - 1][curCol] == 'X') || (maze[curRow + 1][curCol] == 'X') || (maze[curRow][curCol + 1] == 'X') || (maze[curRow][curCol - 1] == 'X')) exit (0); /* Recurse in each possible direction that is empty. */ /* Move up */ if (maze[curRow - 1][curCol] == ' ') { maze[curRow - 1][curCol] = 'O'; solve_maze(maze, curRow - 1, curCol); maze[curRow - 1][curCol] = ' '; } /* continued on next slide *//* Move down */ if (maze[curRow + 1][curCol] == ' ') { maze[curRow + 1][curCol] = 'O'; solve_maze (maze, curRow + 1, curCol); maze[curRow + 1][curCol] = ' '; } /* Move left */ if (maze[curRow][curCol - 1] == ' ') { maze[curRow][curCol - 1] = 'O'; solve_maze (maze, curRow, curCol - 1); maze[curRow][curCol - 1] = ' '; } /* Move right */ if (maze[curRow][curCol + 1] == ' ') { maze[curRow][curCol + 1] = 'O'; solve_maze (maze, curRow, curCol + 1); maze[curRow][curCol + 1] = ' '; } usleep (600000); return; }/* Display the maze passed as a parameter to standard output. */ void display_maze (char maze[ ][NUMCOLS]) { int i, row, col; for (row = 0; row < NUMROWS; row++) { for (col = 0; col < NUMCOLS; col++) { printf ("%c", maze[row][col]); } printf ("\n"); } usleep (600000); printf ("\n"); }int read_maze (char maze[ ][NUMCOLS], int *sRow, int *sCol) { FILE *fpMaze; int row, col; char endofline; /* end of line character */ /* Open maze text file, make sure it opens OK. */ if ((fpMaze = fopen ("maze.txt", "r")) == NULL) return 0; for (row = 0; row <