I need to decompose the number l into prime factors. For this I use recursion. And when l = 1, the function must exit their recursion and return the string in which the prime factors are located, however, the function continues to work and already according to a principle incomprehensible to me. Please explain what is the problem with my code?
fun factors(l: Int): String {
return if (l == 1) {
answer
} else {
for (i in 2..l) {
if (l % i == 0) {
answer = "$i "
factors(l / i)
}
}
return factors(l)
}
}
CodePudding user response:
Let's first mention some issues in your current code:
You're mixing semantics, here. What is the contract of your function? Does it return a value, or does it modify a global variable? Pick one, don't do both.
You should not use a global variable because it's way harder to follow. Instead, construct your values locally from the current information whatever the recursive call returns to you
You're already using an
if
expression with the syntaxreturn if (condition) { ... } else { ... }
. This means each branch of theif
should just end with an expression, you don't need to usereturn
again. That said, in this case the first branch is rather a special case that you want to get out of the way before doing the bulk of the general work. In this kind of situation, I would rather use a statement likeif (condition) { return X }
at the beginning and then have the rest of the body of the function unnested, instead of using anif
expression (but that is a personal preference).It is strange to compute the list of factors as a string. You likely want to avoid duplicates and maybe sort them, so a
List<Int>
or aSet<Int>
would likely be more appropriate. You can always format after the fact using things likejoinToString(" ")
I'm not sure I get the math correctly, but it seems you really will be getting all factors here, not just the prime factors.
Now, the actual cause of the behaviour you're seeing is that you're calling your function recursively with the same number at the end: return factors(l)
. This means that calling factors(l)
with any l > 1
will end up calling itself with the same value over and over. Recursive calls need to change some arguments to the function if you don't want it to be infinite.
CodePudding user response:
fun factors(value: Int, list: MutableList<Int> = mutableListOf()): MutableList<Int> {
if (value > 1) {
for (i in 2..value) {
if (value % i == 0) {
list.add(i)
list.addAll(factors(value / i))
break
}
}
}
return list
}
(2..25).forEach {
val factors = factors(it)
val result = factors.reduce { acc, i -> acc * i }.toString() " = " factors.joinToString(" × ")
println(result)
}
Output:
2 = 2
3 = 3
4 = 2 × 2
5 = 5
6 = 2 × 3
7 = 7
8 = 2 × 2 × 2
9 = 3 × 3
10 = 2 × 5
11 = 11
12 = 2 × 2 × 3
13 = 13
14 = 2 × 7
15 = 3 × 5
16 = 2 × 2 × 2 × 2
17 = 17
18 = 2 × 3 × 3
19 = 19
20 = 2 × 2 × 5
21 = 3 × 7
22 = 2 × 11
23 = 23
24 = 2 × 2 × 2 × 3
25 = 5 × 5