multiplicative persistence - recursion?

Question

I'm working on this:

Write a function, persistence, that takes in a positive parameter num and returns its multiplicative persistence, which is the number of times you must multiply the digits in num until you reach a single digit.

For example:

persistence(39) == 3 // because 3*9 = 27, 2*7 = 14, 1*4=4 // and 4 has only one digit

persistence(999) == 4 // because 9*9*9 = 729, 7*2*9 = 126, // 1*2*6 = 12, and finally 1*2 = 2

persistence(4) == 0 // because 4 is already a one-digit number

This is what I tried:

  public static int Persistence(long n)
        {
            List<long> listofints = new List<long>();

           while (n > 0)
            {
                listofints.Add(n % 10);
                n /= 10;
            }
            listofints.Reverse();
            // list of a splited number

            int[] arr = new int[listofints.Count];
            for (int i = 0; i < listofints.Count; i++)
            {
                arr[i] = (int)listofints[i];
            }
            //list to array

            int pro = 1;
            for (int i = 0; i < arr.Length; i++)
            {
                pro *= arr[i];
            }
            // multiply each number
            return pro;
        } 

I have a problem with understanding recursion - probably there is a place to use it. Can some1 give me advice not a solution, how to deal with that?

Answer 1

Let me take a stab at explaining when you should consider using a recursive method.

Example of Factorial: Factorial of n is found by multiplying 1*2*3*4*..*n.

Suppose you want to find out what the factorial of a number is. For finding the answer, you can write a foreach loop that keeys multiplying a number with the next number and the next number until it reaches 0. Once you reach 0, you are done, you'll return your result.

Instead of using loops, you can use Recursion because the process at "each" step is the same. Multiply the first number with the result of the next, result of the next is found by multiplying that next number with the result of the next and so on.

5 * (result of rest)
  4 * (result of rest )
    3 * (result of rest)
      ...
      1 (factorial of 0 is 1).---> Last Statement.

In this case, if we are doing recursion, we have a terminator of the sequence, the last statement where we know for a fact that factorial of 0 = 1. So, we can write this like,

FactorialOf(5) = return 5 * FactorialOf(4) = 120 (5 * 24)
FactorialOf(4) =    return 4 * FactorialOf(3) = 24 (4 * 6)
FactorialOf(3) =      return 3 * FactorialOf(2) = 6 (3 * 2)
FactorialOf(2) =        return 2 * FactorialOf(1) = 2 (2 * 1)
FactorialOf(1) =          return 1 * FactorialOf(0) = 1 (1 * 1)
FactorialOf(0) = Known -> 1.

So, it would make sense to use the same method over and over and once we get to our terminator, we stop and start going back up the tree. Each statement that called the FactorialOf would start returning numbers until it reaches all the way to the top. At the top, we will have our answer.

Your case of Persistence

It calls for recursive method as well as you are taking the result and doing the same process on it each time.

Persistence(39) (not single)   = return 1 + Persistence(3 * 9 = 27) = 3
Persistence(27) (not single)   =   return 1 + Persistence(2 * 7 = 14) = 2
Persistence(14) (not single)   =     return 1 + Persistence(1 * 4 = 4) = 1
Persistence(4)  (single digit) = Known -> 0  // Terminator.

At the end of the day, if you have same process performed after each calculation / processing with a termination, you can most likely find a way to use recursion for that process.