Iteration to Recursion: The Collatz Conjecture (Swift 4)
This week, I was asked to investigate the Collatz conjecture and write a function that determines the amount of steps it takes for a given input to get to 1. The Collatz conjecture is named after Lothar Collatz, an early 20th century German mathematician. The main idea behind the conjecture is that for any given number, n (i.e. 12), if that given number is even, you half that number. You continue to half the resulting number if it is even. If not (meaning, if the number is odd), then you take the odd number and multiply it by 3 and add 1. You continue to apply these two operations (either n * 2 or 3n + 1) until n = 1.
To Illustrate:
If even, I divide by 2. If odd, I multiply by 3 and add 1. I continue to do this until I get to the number 1.
Above, I numbered the steps I took to get to 1. It took 9 steps.
Below, I will investigate how to count the number of steps through code (Swift, of course!) . Note: sometimes I spell “Collatz” like “Colletz”, sorry!
Collatz Conjecture without Recursion
I’ll address my steps above.
1 = I create a variable that will hold my current count of steps.
2 = I create a copy of my input, n, so that I can update its value as I do n*2 OR 3n + 1 in the function.
3 = I use a while loop to loop through the operations n*2 OR 3n + 1 while copy is greater than 1.
4–6 = If the copy is even, then I half copy and increment the countOfSteps by 1.
7 = I print out my current copy value.
8 = If the copy value is odd, I multiply it by 3 and add 1. I also increment countOfSteps here as well as print out the current copy value.
9 = I want to create some sort of timer on this so I initialize a start . This creates a `DispatchTime` relative to the system clock.
10 = I initialize another DispatchTime as end and subtract the nanoseconds from end to start . I convert nanoseconds into seconds and print out a sentence that states the elapsed time it took me to run this function.
alt + command + left_arrow will let you fold a function (line 5).Running this function WITHOUT recursion when n = 12 took 0.009045888 seconds.
Collatz Conjecture WITH Recursion
Let me walk you through my steps:
1 = I create a variable that will hold my current count of steps.
2 = I create a copy newN of my input, n, so that I can update its value as I do n*2 OR 3n + 1 in the function. I initially set newN ‘s value to 0 but I could have also assigned it to n’s value. It doesn’t matter, because newN is going to eventually be an updated value.
3 = If n is equal to 1, then it will take 1 step to be 1, so I return 1.
4 = If n is not equal to 1 (i.e. 12), I check to see if n is even.
5 = If n is even, I assign newN to half of n.
6 = If n is odd, I assign newN to 3n+ 1
7–8 = I increment my counter, countOfSteps and print out the current number of steps.
9 = I use a ternary conditional here. If newN is equal to 1, then return the current countOfSteps . If newN is not equal to 1, then I return a call to my function collatzConjectureRecursion(:) . This call will continue to iterate through this Collatz process until n is equal to 1.
10 = I want to create some sort of timer on this so I initialize a start . This creates a `DispatchTime` relative to the system clock.
11 = I initialize another DispatchTime as end and subtract the nanoseconds from end to start . I convert nanoseconds into seconds and print out a sentence that states the elapsed time it took me to run this function.
Running this function WITH recursion when n = 12 took 0.000402969 seconds in its last iteration. Note that in its first call, it took 0.008834584 seconds, which is less time than the first function I wrote WITHOUT recursion.
I hope you enjoyed learning more about the Collatz conjecture, using DispatchTime and refactoring a function with a for-loop into a function with recursion. Please enjoy a little Gosling/Culkin recursion below.
Resources:
