CODEWITHSUNDEEP
javarecursion
KabirGandhiok
KabirGandhiok

Reputation: 29

Cannot understand why 1 is added to each recursive call

I have been working on a code challenge which asks to keep multiplying the digits of a number until the digits are reduced to a single digit and then return the number of times the multiplication took place. If the argument passed in is a single digit then the method must return 0.

I have solved the problem using a loop, but I would like to understand how to do it using recursion. Below is the code I found that I could understand for the most part except for why 1 is being added to each call? Can anyone help me understand this? Thanks!

public static int persistence(int num) {
    int mul = 1;
    if (num < 10) return 0;
    while (num != 0) {
        mul *= num % 10;
        num /= 10;
    }
    return 1 + persistence(mul);   // reason for 1 + method call?
}

persistence(39)  //should return 3
persistence(999) //should return 4
persistence(4)   // should return 0

// 39: 3 * 9 = 27, 2 * 7 = 14, 1 * 4 = 4. Value returned 3
// 4: 4 * 1 = 4. Value returned 0

Upvotes: 0

Views: 122

Answers (2)

Soner from The Ottoman Empire
Soner from The Ottoman Empire

Reputation: 20911

Yeah .. Similar issues arise while learning recursion! The path on which every engineer walks. Let's hold the 1 just in a variable and persistence(mul)'s another one. That is,

int oneStepResult = persistence(mul); // watch out that the rest of the line is evaluated when returned 0, that is, base case
int isDone = 1;
return oneStepResult + isDone;

Try to think it like that. As an advice, whenever you run into difficulty while answering question of "what does the recursion do", try to dissect its method body.

with 34

enter image description here

with 39

enter image description here

Upvotes: 1

KingMathCS
KingMathCS

Reputation: 19

Each time the method is called, it will return 1 + the result of the next method call. Basically, it is counting how many times it has to go through and multiply the numbers. Here is a (simplified) visual showing what gets returned each time:

persistence(39) -> 1 + persistence(27)

1 + (persistence(27)) -> 1 + (1 + persistence(14)) -> 2 + persistence(14)

2 + (persistence(14)) -> 2 + (1 + persistence(4)) -> 3 + persistence(4)

3 + (persistence(4)) -> 3 + (0) -> 3

Upvotes: 1

Related Questions