Recursion problem - is this solution correct, and is there a simpler one?

Question

I am new to recursion and I found the following Java problem:
Write a function that gets an integer n, and prints the numbers 1!,2!,3!,...,n!.
Here is what I did and I would like to know if this is the simplest solution (I am not sure because I used "for" loop to do it).

public static void Print(int n) {
  if (n == 0) {
    System.out.print("1");
  } else {
    int temp = 1;
    for (int i = 1; i <= n, i++) {
      temp = temp * i;
    }
    Print(n-1);
    System.out.print(temp);
  }
}

By the way, the previous exercise was to write a function that gets an integer n and returns n!, using recursion. Do you think I need to use it here and print it instead of calculating temp (n!) and print it? Thanks!

For this function you will want to use a long instead. Factorials cause a overflow crazy fast because the growth is so high. — rasmus91, Aug 23 '19 at 16:17
It doesn't make a lot of sense to both use recursion and a for loop. You can solve the problem using either. — daniu, Aug 23 '19 at 16:18
So what should I do instead? Note that I have very little background and knowledge so I know only the basic things — Omer, Aug 23 '19 at 16:18

Butiri Dan · Answer 1 · 2019-08-23T16:35:58.637

1

Without recursion

int temp = 1;
for (int i = 1; i <= 10; ++i) {
    temp *= i;
}
System.out.println(temp);

The recursion is your loop

public static void main(String[] args) {
    System.out.println(print(10));
}

public static long print(long n) {
    if (n == 0) {
        return 1;
    }
    return n * print(n - 1);
}

Output

edited Aug 23 '19 at 16:35

answered Aug 23 '19 at 16:17

Butiri Dan

1,759
5
12
18

4

It's a bit unclear in the question, but I believe the purpose is to print n _factorial_, not literally print `n!` – Christopher Schneider Aug 23 '19 at 16:23
1

That is now how I understood the question, I think we need to print the value and not k! – Omer Aug 23 '19 at 16:24

score 1 · Answer 2 · answered Aug 23 '19 at 16:25

What you wrote works, however you are recalculating a bunch of stuff, and you're still using a for loop when you could do this entire thing recursively and with less code.

Assuming you are stuck using the function Print(int n), you can write less code and only calculate each factorial once by recursing upwards from 1 and carry the calculations with it:

public static void Print(int n) {
    PrintHelper(1, n, 1);
}

private static void PrintHelper(int i, int n, long factorial) {
    if (i > n)
        return;

    factorial *= i;
    System.out.println(factorial);
    PrintHelper(i + 1, n, factorial);
}

This is easier to read, easier to reason about, and avoids doing the same calculations over and over again.

In the example I posted above, I am doing n multiplications. In your example you are doing approximately n^2 / 2 multiplications since you iterating over every number again and again (ex: 1*2*3*...*50, then 1*2*3*...*49, then 1*2*3*...*48, ...etc).

The code I wrote omits error checking for brevity of demonstration, since you can trivially add input sanity checks to it.

score 1 · Accepted Answer · answered Aug 23 '19 at 16:25

1

Here is a simple recursive solution:

  public static long factorial(long n) {
    if(n == 0 || n == 1) {
      System.out.print(1 + " ");
      return 1;
    }

    long result = n * factorial(n - 1);
    System.out.print(result + " ");
    return result;
  }

answered Aug 23 '19 at 16:25

Enioluwa Segun

911
8
12

Thanks but I did not learn what is "long" yet, I am just starting and the exercise should use only basic things – Omer Aug 23 '19 at 16:26
`long` is a numeric type that stores more bits than `int` before overflowing. They are completely interchangeable in this case, provided n! < 2 147 483 647 – Enioluwa Segun Aug 23 '19 at 16:29
1

`long` is just a primitive data type like `int` that can store larger numbers. Using an `int` for factorials can cause integer overflows very quickly. See https://docs.oracle.com/javase/tutorial/java/nutsandbolts/datatypes.html – Christopher Schneider Aug 23 '19 at 16:29

Dimitar · Answer 4 · 2019-08-23T16:37:00.657

1

A one-liner will look like:

public static int factorial(int n) {
    return (n <= 2) ? n : n * factorial((n-1));
}

The ternary operator folds the if-statement. Then using recursion, each function call becomes a factor in the factorial function, until the base case (n <= 2) is reached:

4 * factorial(3)

4 * 3 * factorial(2)

4 * 3 * 2

edited Aug 23 '19 at 16:37

answered Aug 23 '19 at 16:29

Dimitar

4,402
4
31
47

geco17 · Answer 5 · 2019-08-23T16:57:24.630

Using recursion to get the factorial of a number (previous exercise), this method will look something like

long factorial(long n) {
    if (n > 0) {
        return n*factorial(n - 1);
    }
    return 1;
}

Given this, it's better to not use recursion and just use a loop to get the factorial of a number, like so:

long factorial(long n) {
    long factorial = 1;
    for (long i = 1; i <= n; i++) {
        factorial *= i;
    }
    return factorial;
}

if you want all numbers in the series

long[] factorials(long n) {
    long[] factorials = new long[n+1];
    long factorial = 1;
    for (long i = 1; i <= n; i++) {
        factorial *= i;
        factorials[n] = factorial;
    }
    factorials[0] = 1;
    return factorials;
}

If you only need to print them, the method becomes

void factorials(long n) {
    long factorial = 1;
    System.out.println(factorial); // 0!
    for (long i = 1; i <= n; i++) {
        factorial *= i;
        System.out.println(factorial);
    }
}

Nathan Hughes · Answer 6 · 2020-11-18T20:29:57.070

This adds printing in a way that doesn't make the recursive expression harder to read.

public class Fact {

    public static void main(String... args) {
        fact(5L);
        System.out.println();
    }

    static long fact(long n) {
        return print(
            n == 0 || n == 1 ? 1 : n * fact(n - 1));
    }

    static long print(long i) {
        System.out.print(Long.toString(i));
        return i;
    }
}

Recursion problem - is this solution correct, and is there a simpler one?

6 Answers6