Find the sum of the factorial of each digit of a number using recursion-CodePudding

I need to find the sum of the factorial of each digit of a number using recursion.

Doing this iteratively would be relatively simple, but I am supposed to do it recursively.

I haven't gotten a solution yet. I have only gotten small pieces of this problem.

Method to find factorial

public static int factorial(int n) {

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

Method to find sum of digits

public static int sum_of_digit(int n) {
    if (n == 0){
        return 0;
     }
    return (n % 10   sum_of_digit(n / 10));
}

My issue is trying to use what I know to now get the factorial of each digit and add those together.

EDIT: (provided by author from comments):

Example

n=145 1! = 1 4! = 24 5!=120 (sum = 1   24   120)

CodePudding user response：

I believe this is what you want to do. I renamed your sum method to illustrate its purpose.

int v = sum_of_digit_factorials(325);
System.out.println(v);

prints

The methods

// the original factorial method
public static int factorial(int n) {

    if (n==0){
        return 1;
    }
    
    return n*factorial(n-1);
}
// the modified sum method.
public static int sum_of_digit_factorials(int n) {
    if (n == 0){
        return 0;
     }
    return  factorial(n%10)   sum_of_digit_factorials(n/10);
}

As the method is called, factorial computes the factor of the first digit. That will then be added to the subsequent call via sum_of_digit_factorials(n/10) which will expose the next digit to be computed which will again be retrieved by the factorial call and added to the previous factorial.

When n reaches 0, 0 will be returned (thus not affecting the sum) and the recursive calls will unwind returning the desired result.

I also recommend placing print statements in the sum method. You can even break up the last return statement into two parts. By printing n and the computed factorials, it will help to see how this produces the answer.

CodePudding user response：

public static int sum_of_digit(int n) {
    if (n == 0){
        return 0;
    }
    return (n % 10   sum_of_digit(n / 10));
}

In the above method, the part n % 10 is calculating the remainder after dividing n by 10, for example 32 % 10 = 2.

Then its adding that 2 to the tail calculation, using n / 10 as input. in the same example 32 / 10 = 3.

The result of the example is 2 3 = 5.

What you now want to do is not add up the digits themselves, but their factorial, so you could call your factorial function with the remainder as argument, and add that to the tail calculation rather than just the digit itself.

Note that for larger numbers this becomes a bit computation intensive. You can use a technique called 'memoization' to remember (or pre-calculate) the factorials you need. After all, you only use the factorials of 0 - 9. You could pre-calculate those and store them in an array to optimze your code. I am expecting this to be next in this obviously homework assignment ;-)

CodePudding user response：

You should implement another function invoking factorial for separate digits:

public static int sum_of_digit_factorial(int n) {
    if (n < 10) {
        return factorial(n);
    }
    return factorial(n % 10)   sum_of_digit_factorial(n / 10);
}