Designing a non-recursive algorithm for factorial problem?

Answer 1

This is a non-recursive implementation of n factorial that supports arbitrary length decimal arithmetic. For very large values of n, you may need to tell your linker to increase the size of the run-time stack.

#include <stdlib.h>

#include <stdio.h>

/* Portable arbitrary length decimal iterative */

/* one node of a linked list of digits, the first node being low-order */

struct _decimal {

int digit;

struct _decimal *next;

};

typedef struct _decimal decimal;

/* Portable arbitrary length decimal iterative */

/* Initialize the list - necessary on second pass, if main recoded */

void decimal_initialize (decimal *d, int n) {

decimal *next, *nextsave;

d->digit = n;

nextsave = d->next;

d->next = NULL;

next = nextsave;

while (next != NULL) {

nextsave = next->next;

free (next);

next = nextsave;

}

return;

}

/* Portable arbitrary length decimal iterative */

/* Append a digit at the high order position */

void decimal_add_digit (decimal *d, int n) {

decimal *new_digit = (decimal*) malloc (sizeof (decimal));

while (d->next != NULL) d = d->next;

new_digit->digit = n;

new_digit->next = NULL;

d->next = new_digit;

return;

}

/* Portable arbitrary length decimal iterative */

/* Print the digits in reverse order - recursive */

void decimal_print_digits (decimal *d, int last_digit) {

if (d->next != NULL) decimal_print_digits (d->next, false);

printf ("%d", d->digit);

if (last_digit) printf("\n");

return;

}

/* Portable arbitrary length decimal iterative */

/* multiply the list by N */

void decimal_multiply (decimal *d, int N) {

int carry = 0;

while (d != NULL) {

d->digit = d->digit * N + carry;

carry = d->digit / 10;

d->digit %= 10;

if (carry != 0 && d->next 2) {

decimal_initialize (d, 2);

return;

}

while (N > 2) {

decimal_multiply (d, N);

N--;

}

return;

}

/* Generates all variations to show differences in results */

int main (int argc, char *argv[]) {

int N;

decimal Decimal = {2, NULL};

if (argc < 2) {

printf ("Enter N (or use command line) : ");

scanf ("%d", &N);

} else {

N = atoi (argv[1]);

}

printf ("Arbitrary: %u! = ", N);

decimal_NFactIterative (&Decimal, N);

decimal_print_digits (&Decimal, true);

return 0;

}