Recursion
COP-3223H
Table of Contents
Functions have their own variables
int g(int x) {
x = x + 1;
return x;
}
int main(int argc, char **argv) {
int x = 1;
g(x);
printf("%d\n", x);
}
Functions for iteration
int sum = 0;
for (int i = 1; i <= 3; i++) {
sum = sum + i;
}
int sum3() {
return sum2() + 3;
}
int sum2() {
return sum1() + 2;
}
int sum1() {
return sum0() + 1;
}
int sum0() {
return 0;
}
- Last function is like the initializer
- The rest of the functions follow a pattern
What is we could "generate" these functions based on a pattern?
This is what functions with parameters and their own local variables allows for.
Function calls "generate" new instance
Each call creates new copy of the functions variables, including the parameter.
This is called the recursive step
Take a specific function instance
int sum3() {
return sum2() + 3;
}
Paramterize what's different about each function
int sum(3) {
return sum(2) + 3;
}
Then generalize the pattern with the parameter
int sum(int n) {
return sum(n - 1) + n;
}
What happens when we call this function?
Recursive calls are like iteration
The call is a goto back to the top of the function
Stopping the iteration
The last call is called the base case
int sum1() {
return sum0() + 1;
}
int sum0() {
return 0;
}
Encoding the last step (base case)
int sum0() {
return 0;
}
int sum(0) {
return 0;
}
int sum(int n) {
return 0; // when n is 0
}
Combining recursive step and base case
How do we combine these two functions into one?
int sum(int n) {
// recursive step
return sum(n - 1) + n;
}
int sum(int n) {
// base case
return 0; // when n is 0
}
The base case only happens when n is 0. We can use a conditional to check for this.
When n is greater than 0
int sum(int n) {
// recursive step
return sum(n - 1) + n;
}
When n is 0
int sum(int n) {
// base case
return 0; // when n is 0
}
Use a condition inside a shared function instead of around the functions
The complete recursive function
int sum(int n) {
// recursive step
if (n > 0) {
return sum(n - 1) + n;
// base case
} else if (n == 0) {
return 0; // when n is 0
// should not happen
} else {
assert(false);
}
}
Diagram of the function calls
Lay out each copy of local variables that each function call has
Point out that it's a stack
Factorial with recursion
int factorial(int n) {
if (n > 0) {
return factorial(n - 1) * n;
} else if (0 == n) {
return 1;
} else {
assert(false);
}
}
Exponent with recursion
int exponent(int x, int e) {
if (e > 0) {
return exponent(x, e - 1) * x;
} else if (0 == e) {
return 1;
} else {
assert(false);
}
}
Eight queens
The eight queens puzzle
(Diagram)
The for loop project was to create the eiqht queens game, where the user could only place queens in legal positions.
In this exercise, we will show how to automatically solve the puzzle, using recursion.
Solution strategy
- Naive approach: try every possibility
- Try one queen in every row
- If we fail, go back and try the next column
- Recursion with backtracking
- Recursive step: given X queens, place one more
- If no solution works, go back to X - 1 and try more solutions (backtracking)
- Base case: got all rows (or had to backtrack)
- Recursive step: given X queens, place one more
Simplified stepwise refinement
init the board
place row 0
place the next row
if we're done, draw it
otherwise
try each column in the row
place a queen if safe, then place the next row
Backtracking made explicit
init the board
place row 0
place row X
if we're done, draw it
otherwise
try each column in the row
if column is safe
place a queen
check the next row X + 1
unplace a queen (so we can keep trying)
An implementation in C
#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
void draw(int board[8]) {
printf(" ");
for (int j = 0; j < 8; j++) {
printf("%d", j);
}
putchar('\n');
for (int i = 0; i < 8; i++) {
printf("%d ", i);
for (int j = 0; j < 8; j++) {
if (board[i] == j) {
putchar('Q');
} else {
putchar('.');
}
}
putchar('\n');
}
putchar('\n');
putchar('\n');
}
int safe(int board[8], int i, int j) {
// no need to check columns, we only add one queen per row anyway
/* for (int col = 0; col < 8; col++) { */
/* if (board[i] == col) { */
/* return false; */
/* } */
/* } */
// check the column
for (int row = 0; row < 8; row++) {
if (board[row] == j) {
return false;
}
}
// check each diagonal the brute force way. wirth has a clever
// optimization that makes the observation that position with the
// same difference or sum of the row, col indices means there is a
// queen in that position. it requires holding two additional
// arrays and setting/unsetting them in addition to the board
for (int row = i, col = j; (row < 8) && (col < 8); row++, col++) {
if (board[row] == col) {
return false;
}
}
for (int row = i, col = j; (row < 8) && (col >= 0); row++, col--) {
if (board[row] == col) {
return false;
}
}
for (int row = i, col = j; (row >= 0) && (col < 8); row--, col++) {
if (board[row] == col) {
return false;
}
}
for (int row = i, col = j; (row >= 0) && (col >= 0); row--, col--) {
if (board[row] == col) {
return false;
}
}
return true;
}
void place(int board[8], int i) {
if (8 == i) {
// if we're on the last row, it means we've found a solution
draw(board);
}
for (int j = 0; j < 8; j++) {
// try each column in the candidate row
if (safe(board, i, j)) {
// if the column is safe, place a queen
board[i] = j;
// then try placing a queen in the next row
place(board, i + 1);
// unplace the queen and keep trying columns
board[i] = -1;
}
}
}
int main(int argc, char **argv) {
int board[8];
// init board
for (int i = 0; i < 8; i++) {
board[i] = -1;
}
// try starting in each column in the first row
for (int j = 0; j < 8; j++) {
board[0] = j;
place(board, 1);
}
}