It seems like almost every programming book uses the Fibonacci Sequence to teach recursion. At first glance, this seems logical: to calculate the Nth Fibonacci number, you must know the two before it. To calculate the 10th number, you add the 8th and 9th together. <\/p>\n\n\n\n
<\/p>\n\n\n\n
Recursion seems to make sense here, because if you want 10 you need 8 and 9. If you need 8 and 9, you need to calculate 6 and 7. This goes on all the way down. That makes a lot of sense and it does<\/strong> demonstrate recursion pretty well. <\/p>\n\n\n\n <\/p>\n\n\n\n My issue is this: recursion is the worst way to calculate the Fibonacci Sequence. So yes, we are teaching students how recursion works. But we’re also teaching them a very bad use for it. I know, I know: when are programmers ever going to need to calculate Fibonacci numbers in the Real World? Maybe they will, maybe they won’t. But if they ever do need it, they’ll think back to almost every programming course they ever took and think: “Aha! I will use recursion like I learned in class.”<\/p>\n\n\n\n <\/p>\n\n\n\n I could go into all the theoretical math involving time complexity, but let’s just try them instead. There’s nothing like actually seeing the difference first hand. <\/p>\n\n\n\n <\/p>\n\n\n\n Let’s compare two methods in Python:<\/p>\n\n\n\n As you can see, I used an iterative function first and then the recursive version second. I did them in this order so I could get results for the iterative version quickly and then the recursive results eventually. I tracked the total addition operations, function calls and execution time. I played around with various inputs but for the demonstration here I went with 25, 30 and 7718. The iterative function did pretty well: <\/p>\n\n\n\n The recursive version did not do as well:<\/p>\n\n\n\n You can see that the iterative versions both took just a few milliseconds<\/em>. The recursive version took almost 25 seconds for the 25th number (not too bad) but then just asking for 5 more made the time jump up to almost five minutes thanks to exponential growth. Asking for 50 makes it take days. When I was learning C ages ago in a DOS environment, asking for too many would give me a stack overflow pretty quickly. Thankfully, we aren’t limited to very tiny stack\/heap sizes anymore so you can reasonably expect to get results for pretty high values assuming you’ve got the free time and the Sun doesn’t go out before it’s done calculating. \ud83d\ude09 <\/p>\n\n\n\n <\/p>\n\n\n\n I asked the iterative version for 7718 (it’s a strange number but I’m pretty sure) and it took about 1.5 seconds. My iterative version isn’t even the most efficient way, there are other algorithms that may do better in some cases (such as Binet’s formula). But it’s pretty clear that recursion is one of the worst ways to calculate any relatively large value.<\/p>\n\n\n\n <\/p>\n\n\n\n <\/p>\n\n\n\n I know the Quicksort algorithm may be too complicated for a programming class that is just learning about recursion. So what’s something simple that most people know? When I took Java in college our recursion exercise was one simple thing that (at least here in the states) is widely known. The assignment was to print the lyrics of The Twelve Days of Christmas. I found this change of pace refreshing. <\/p>\n\n\n\n <\/p>\n\n\n\n In The Twelve Days of Christmas, the singer is describing all the gifts their true love gave them on each day of Christmas. Each day a new gift is introduced and the quantity matches the day. Finally, on day twelve, the ridiculous amount of gifts are finally all given with the arrival of the twelve drummers drumming. Since each day repeats all of the previous days, recursion does work well for this use. <\/p>\n\n\n\n I used the same basic shell of the program and decided to time the iterative and recursive versions. This time, the recursive version actually wins:<\/p>\n\n\n\n <\/p>\n\n\n\n I’m a bit surprised that the recursive version is faster. I would have thought the overhead of the function calls plus the repeated checking of the boolean “max” parameter to see if the heading needed to be printed would have added more time. I expected it to be pretty close, though, and close enough to justify using this to teach recursion. <\/p>\n\n\n\n <\/p>\n\n\n\n We talked about the Fibonacci sequence and why it’s a bad way to teach recursion since it’s not something you would actually want to use recursion for. We need to be more creative when teaching this concept. The Towers of Hanoi and The Twelve Days of Christmas are the only two I’ve seen in a programming book. How about you? Have you seen some other simple uses for recursion? How about real-world uses for the Fibonacci Sequence? Put your favorite ones in the comments:<\/p>\n","protected":false},"excerpt":{"rendered":" It seems like almost every programming book uses the Fibonacci Sequence to teach recursion. At first glance, this seems logical: to calculate the Nth Fibonacci number, you must know the two before it. To calculate the 10th number, you add the 8th and 9th together. Recursion seems to make sense here, because if you want […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"hide_page_title":"","footnotes":""},"categories":[5,6],"tags":[4,3],"jetpack_featured_media_url":"","_links":{"self":[{"href":"http:\/\/www.hairballgamesllc.com\/blog\/wp-json\/wp\/v2\/posts\/47"}],"collection":[{"href":"http:\/\/www.hairballgamesllc.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.hairballgamesllc.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.hairballgamesllc.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.hairballgamesllc.com\/blog\/wp-json\/wp\/v2\/comments?post=47"}],"version-history":[{"count":5,"href":"http:\/\/www.hairballgamesllc.com\/blog\/wp-json\/wp\/v2\/posts\/47\/revisions"}],"predecessor-version":[{"id":58,"href":"http:\/\/www.hairballgamesllc.com\/blog\/wp-json\/wp\/v2\/posts\/47\/revisions\/58"}],"wp:attachment":[{"href":"http:\/\/www.hairballgamesllc.com\/blog\/wp-json\/wp\/v2\/media?parent=47"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.hairballgamesllc.com\/blog\/wp-json\/wp\/v2\/categories?post=47"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.hairballgamesllc.com\/blog\/wp-json\/wp\/v2\/tags?post=47"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}Why is recursion bad (in this case)?<\/h2>\n\n\n\n
import timeit\nimport sys\n\ndef recursive(n):\n global additions, function_calls\n\n function_calls += 1\n sys.stderr.write(f\"Recursive({n}) \\r\") # Ease user anxiety\n\n if n <= 0:\n return \"I am not doing that.\"\n elif n == 1:\n # Not counting these as additions\n return 1\n elif n == 2:\n # Not counting these as additions\n return 1\n else:\n # Add my own instance's values.\n additions += 1\n return recursive(n-1) + recursive(n-2)\n\ndef iterative(n):\n global additions, function_calls\n\n function_calls += 1\n\n if n <= 0:\n return \"I am still not doing that.\"\n elif n == 1:\n # Still not counting these as additions\n return 0\n elif n == 2:\n # Still not counting these as additions\n return 1\n else:\n a, b = 1, 1\n for i in range(n-2):\n a, b = b, a + b\n additions += 1\n sys.stderr.write(f\"Iterative({i}) \\r\") # Ease user anxiety\n return b\n return result\n\nn = sys.stderr.write(\"Please enter a value for N: \")\nn = input()\nn = int(n)\n\n\n# Time the iterative algorithm\nfunction_calls = additions = 0 # These will be used as global variables\nstart_time = timeit.default_timer()\nresult = iterative(n)\nend_time = timeit.default_timer()\nexecution_time = end_time - start_time\n\nprint(f\"Iterative\\nResult: {result} Additions: {additions} Function calls: 1 Execution time: {execution_time}\") \n\n# Time the recursive version\nfunction_calls = additions = 0 # Reset our global variables\nstart_time = timeit.default_timer()\nresult = recursive(n)\nend_time = timeit.default_timer()\nexecution_time = end_time - start_time\n\n\nprint(f\"Recursive\\nResult: {result} Additions: {additions} Function calls: {function_calls} Execution time: {execution_time}\") \n\n<\/code><\/pre>\n\n\n\nIterative\nResult: 75025 Additions: 23 Function calls: 1 Execution time: 0.004399699973873794\nResult: 832040 Additions: 28 Function calls: 1 Execution time: 0.005835500021930784\n\n<\/code><\/pre>\n\n\n\nRecursive\nResult: 75025 Additions: 75024 Function calls: 150049 Execution time: 24.754127599997446\nResult: 832040 Additions: 832039 Function calls: 1664079 Execution time: 274.5497388999793\n<\/code><\/pre>\n\n\n\nSo how should<\/em> we teach recursion? <\/h2>\n\n\n\n
import timeit\nimport sys\n\ndays = [\"first\",\"second\",\"third\",\"fourth\",\"fifth\",\"sixth\",\"seventh\",\"eighth\",\"ninth\",\"tenth\",\"eleventh\",\"twelfth\"]\ngifts = [\"a partridge in a pear tree.\",\n \"two turtle doves, and\",\n \"three French hens,\",\n \"four calling birds,\",\n \"five golden rings,\",\n \"six geese a-laying,\",\n \"seven swans a swimming,\",\n \"eight maids a milking,\",\n \"nine ladies dancing,\",\n \"ten lords a-leaping,\",\n \"eleven pipers piping,\",\n \"twelve drummers drumming,\"\n ]\n\n\ndef recursive(n, max):\n global function_calls, days, gifts\n\n function_calls += 1\n\n if n < 0:\n return\n else:\n if max:\n print(f\"\\nOn the {days[n]} day of Christmas, my true love gave to me: \")\n\n print(gifts[n])\n recursive(n-1, False)\n\ndef iterative(n):\n global function_calls, days, gifts\n\n function_calls += 1\n\n for n in range(12):\n\n print(f\"\\nOn the {days[n]} day of Christmas, my true love gave to me: \")\n for i in range(n, -1, -1):\n print(gifts[i]);\n return\n\nfunction_calls = 0 # These will be used as global variables\nstart_time = timeit.default_timer()\n\niterative(12)\n\n\n\nend_time = timeit.default_timer()\nexecution_time = end_time - start_time\n\nprint(f\"\\n\\nIterative\\nFunction calls: {function_calls} Execution time: {execution_time}\")\n\n# Time the recursive version\nfunction_calls = 0 # Reset our global variables\nstart_time = timeit.default_timer()\nfor n in range(12):\n recursive(n, True)\nend_time = timeit.default_timer()\nexecution_time = end_time - start_time\n\n\nprint(f\"\\n\\nRecursive\\nFunction calls: {function_calls} Execution time: {execution_time}\")\n\n<\/code><\/pre>\n\n\n\nIterative\nFunction calls: 1 Execution time: 0.00044239999260753393\nRecursive\nFunction calls: 90 Execution time: 0.0003551999689079821\n<\/code><\/pre>\n\n\n\nIn Conclusion<\/h2>\n\n\n\n