Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Collatz function
// Returns the number of iterations to get from n to 1
// when following the sequence that forms the basis of the
// Collatz conjecture (https://en.wikipedia.org/wiki/Collatz_conjecture)
func collatz(_ n : Int) -> Int {
if n == 1 {
// end at 1
return 0
}
else if n % 2 == 0 {
// even
return 1 + collatz(n / 2)
}
else {
// odd
return 1 + collatz(3 * n + 1)
}
}
collatz(1)
collatz(3000)
collatz(63_728_127)
collatz(999_999_999_999)
@mjcohen

This comment has been minimized.

Copy link

@mjcohen mjcohen commented Aug 10, 2016

Why the "1+" on the return? Shouldn't it just be collatz(n/2) and collatz(3*n+1)?

@erikprice

This comment has been minimized.

Copy link

@erikprice erikprice commented Aug 10, 2016

@mjcohen Both versions add 1 every time collatz() is called. Look carefully at how this version differs from the original, in terms of where this addition is done.

@tandon

This comment has been minimized.

Copy link

@tandon tandon commented Aug 11, 2016

@mjcohen The "1+" is because there is no longer a count variable that increments every time collatz is called.

@cparnot

This comment has been minimized.

Copy link
Owner Author

@cparnot cparnot commented Aug 12, 2016

What's probably unclear from the implementation is that the return value is the number of iterations. I should have made the function name more explicit about it, maybe.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.