/** | |
* This program shows the different kinds of calls that can be made for functions like the factorial, and fibonacci | |
* | |
*/ | |
public class FactorialExample { | |
public static void main(String[] args) { | |
System.out.println( factRecursive(5)); | |
System.out.println( factTailRecursive(5)); | |
System.out.println( factIterative(5)); | |
} | |
/** | |
* This is a simple version of factorial function making recursive calls. | |
* It is not tail recursive, and so cannot be optimized in a functional compiler, | |
* or be made into an iterative function for compilers like Java & C#. | |
* @param n - the number to find the factorial for | |
* @return the factorial of n (assumes positive number, negatives are treated as the value 1) | |
*/ | |
public static long factRecursive(long n) { | |
if (n <= 1) { | |
// base case - keep counting down until this case is reached (assuming positive numbers) | |
return 1; | |
} | |
else { | |
// recursive call - more work has to be done in the next call | |
return n * factRecursive(n-1); | |
} | |
} | |
/** | |
* This is the initial call for the fact2 function. The accumulator is set to 1, and other calls are made | |
* with the accumulator passed in. | |
* @param n - the number to find the factorial for | |
* @return the factorial of n (assumes positive number, negatives are treated as n = 1) | |
*/ | |
public static long factTailRecursive(long n) { | |
// set the default value for the accumulator if this is the first call | |
long accumulator = 1; | |
if (n <= 1) { | |
return accumulator; | |
} | |
else { | |
return fact2(n-1, accumulator * n); | |
} | |
} | |
/** | |
* Iterative call that does not use recursion. It is possible to do this because there is a tail recursive version. | |
* You can always rewrite tail recursive calls as iterative, and vice versa. | |
* @param n - the number to find the factorial for | |
* @return the factorial of n (assumes positive number, negatives are treated as n = 1) | |
*/ | |
public static long factIterative(long n) { | |
long acc = 1; | |
// iterative version | |
while (n > 1) { | |
acc = acc * n; | |
n--; | |
} | |
return acc; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment