# Recursion

## Program #1: Factorial

This computes a factorial recursively.

```#include <stdio.h>

/*
* compute n! recursively
*/
int fact(int n)
{
/* error check */
if (n < 0)
return(-1);
/* base case */
if (n == 0)
return(1);
/* recursion */
return(n * fact(n-1));
}

/*
* convert string to int with error checking
* no leading signs or magnitude checking
*/
int cvttoint(char *s)
{
int n = 0;			/* integer being read */

/* skip leading white space */
while(isspace(*s))
s++;
/* if it's not a digit, it's not an integer */
if (!isdigit(*s))
return(-1);
/* read in the integer */
while(isdigit(*s))
n = n * 10 + *s++ - '0';
/* if it's ended by a NUL, it's an integer */
return(*s ? -1 : n);
}

int main(int argc, char *argv[])
{
int i;		/* counter in a for loop */
int n;		/* number read in */
int rv = 0;		/* exit status code */

/*
* do each arg separately
*/
for(i = 1; i < argc; i++)
if ((n = cvttoint(argv[i])) != -1)
printf("%d! = %d\n", n, fact(n));
else{
/* error handler*/
rv++;
printf("%s: invalid number\n", argv[i]);
}

/*
* bye!
*/
return(rv);
}
```

## Program #2. Greatest Common Divisor

This computes the GCD recursively.

```/*
* gcd -- compute the GCD of pairs of integers
*
* History
* 1.0			Matt Bishop; original program
* 1.1			Matt Bishop; made it recursive
*/
#include <stdio.h>

/*
* macros
*/
#define BAD_GCD -1              /* error in arguments -- */
/* MUST be non-positive */

/*
* recursive GCD
*/
int gcdr(int m, int n)
{
/* base case(s) */
if (m == 0)
return(n);
if (n == 0)
return(m);
/* now recurse */
return(gcd(n, m % n));
}

/*
* This function returns the greatest common divisor of its arguments
* Notes: (1) if m = n = 0, the GCD is undefined -- so we return BAD_GCD
*        (2) if m < 0 or n < 0, then gcd(m,n) > 0; so we can just make
*            m and n both positive
*        (3) if m = 0 and n != 0, gcd(m,n) = n (and vice versa)
*/
int gcd(int m, int n)
{
int rem;			/* remainder for Euclid's algorithm */

/*
* special cases
*/
/* error check -- if both 0, undefined */
if (m == 0 && n == 0)
/* make all negatives positive */
if (m < 0) m = -m;
if (n < 0) n = -n;

/*
* now apply the recursive algorithm
*/
return(gcdr(m, n));
}

/*
* the main routine
*/
void main(void)
{
int m, n;			/* numbers to take the GCD of */
int g;			/* the GCD of m and n */
int c;			/* used to gobble up rest of line */

/*
* loop, asking for numbers and printing the GCD
*/
while(printf("Enter two numbers: "),
scanf("%d %d", &m, &n) != EOF){
while((c = getchar()) != EOF && c != '\n')
;
/* print the result -- note that if the input */
/* is invalid, gcd() simply returns BAD_GCD   */
printf("The GCD of %d and %d is ", m, n);
if ((g = gcd(m, n)) == BAD_GCD)
printf("undefined.\n");
else
printf("%d.\n", g);
}

/*
* clean up output and exit
*/
putchar('\n');
exit(0);
}
```

## Program #3. Sorting

This is a very simple recursive sorting program.

```#include <stdio.h>

/*
* the array and its size
*/
int list[] = { 13, 82, 0, 16, 5, -1, 99, 0 };
int nlist = sizeof(list)/sizeof(int);

/*
* recursive sort -- put smallest element at head of array
* and then sort the rest
*/
void sort(int l[], int lsz)
{
int i;          /* counter in a for loop */
int tmp;        /* used to swap ints */
int min;        /* index of minimum element */

/* base case */
if (lsz == 1)
return;

/* find index of smallest number in array */
min = 0;
for(i = 1; i < lsz; i++)
if (l[i] < l[min])
min = i;

/* move smallest element to 0-th element */
tmp = l[0];
l[0] = l[min];
l[min] = tmp;

/* recurse */
sort(&l[1], lsz-1);
}

int main(void)
{
int i;			/* counter in a for loop */

/* print initial array */
printf("initial array: ");
for(i = 0; i < nlist;i++)
printf(" %3d", list[i]);
putchar('\n');

/* now sort */
sort(list, nlist);

/* print sorted array */
printf("final array:   ");
for(i = 0; i < nlist;i++)
printf(" %3d", list[i]);
putchar('\n');
return(0);
}
```

 ECS 30-A, Introduction to Programming Spring Quarter 2002 Email: cs30a@cs.ucdavis.edu