display | more...

A term used when designing recursive algorithms to describe the case where the problem has been reduced to its simplest or most trivial form. If a recursive algorithm doesn't have this element, it will never unravel (that is, it will never stop recursing and begin returning results back up the chain). Here's some code: everyone's favorite trivial recursion algorithm, the factorial. In a factorial n!, the most trivial cases are where n == 1 (1! == 1) or n == 0 (0! = 0). Otherwise, n! == n * (n - 1)!, which is solved in the recursive case.

#include <stdio.h>
#include <stdlib.h>

int factorial(int n) {
  if (n < 2)  			        /* base case */
    return(1);
  else	                                /* recursive case */
    return(n * factorial(n - 1));
}

int main(int argc, char *argv[]) {
  printf("%d", factorial(atoi(argv[1])));
}

This is extra-bad code which will return bad results if given a number bigger than 19 (that's on my x86 -- that number will change on different architectures). Just an example.

Log in or register to write something here or to contact authors.