Last active
October 26, 2016 20:06
-
-
Save cparnot/69082b542b386482d6ed671a4124ed85 to your computer and use it in GitHub Desktop.
Collatz function
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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 The "1+" is because there is no longer a count variable that increments every time collatz is called.
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
@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.