{"id":1069,"date":"2021-04-02T16:22:00","date_gmt":"2021-04-02T16:22:00","guid":{"rendered":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/?p=1069"},"modified":"2021-04-30T12:35:57","modified_gmt":"2021-04-30T12:35:57","slug":"solving-the-tower-of-hanoi-puzzle-using-recursion","status":"publish","type":"post","link":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/solving-the-tower-of-hanoi-puzzle-using-recursion\/","title":{"rendered":"Solving the Tower of Hanoi puzzle using recursion"},"content":{"rendered":"\t\t<div data-elementor-type=\"wp-post\" data-elementor-id=\"1069\" class=\"elementor elementor-1069\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-f7d4d4f elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"f7d4d4f\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-1e19cb8\" data-id=\"1e19cb8\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-5068e57 elementor-widget elementor-widget-text-editor\" data-id=\"5068e57\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p class=\"MsoNormal\">In the puzzle known as Tower of Hanoi (named after the style of buddhist temples in Vietnam, I assume) , you have three rods or pegs and a number of disks of different diameters. The puzzle begins with a set up like the one shown below (for three disks) where all of the disks are placed on one of the rods (rod A) with the largest at the bottom and the smallest at the top. The aim of the puzzle is to move all of these disks from rod A to rod C whilst obeying the following rules:<\/p><ul><li>Only one disk can be moved at a time<\/li><li>Only the disk at the top of a stack can be moved<\/li><li>A disk cannot be placed on top of another disk with smaller diameter<\/li><\/ul>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-6a93284 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"6a93284\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-957a8d5\" data-id=\"957a8d5\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-483c579 elementor-widget elementor-widget-image\" data-id=\"483c579\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"image.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<img fetchpriority=\"high\" decoding=\"async\" width=\"1024\" height=\"408\" src=\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-content\/uploads\/sites\/24\/2021\/04\/TOHmain-1024x408.png\" class=\"attachment-large size-large wp-image-1098\" alt=\"Diagram showing the setup in the Tower Of Hanoi puzzle\" srcset=\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-content\/uploads\/sites\/24\/2021\/04\/TOHmain-1024x408.png 1024w, https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-content\/uploads\/sites\/24\/2021\/04\/TOHmain-300x119.png 300w, https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-content\/uploads\/sites\/24\/2021\/04\/TOHmain-768x306.png 768w, https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-content\/uploads\/sites\/24\/2021\/04\/TOHmain-1536x612.png 1536w, https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-content\/uploads\/sites\/24\/2021\/04\/TOHmain.png 1750w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/>\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-ecb3862 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"ecb3862\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-f904af0\" data-id=\"f904af0\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-781482d elementor-widget elementor-widget-text-editor\" data-id=\"781482d\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p style=\"font-size: 16px;font-style: normal\"><span style=\"font-weight: 400\">It\u2019s a relatively simple task, with a little trial and error, to solve this puzzle for the three-disk problem shown here but what if there are more disks? Is there some kind of rule we can come up with to be able to solve this no matter the number of disks, \\( N [\\latex], present? The answer is yes, kind of \u2026 In that we can find these rules by leveraging a programming\/problem solving concept known as <\/span><b>recursion<\/b> but as I\u2019ll explain later there is something else that limits our ability to solve the problem for large numbers of disks.<\/p><p style=\"font-size: 16px;font-style: normal\"><span style=\"font-weight: 400\">The philosophy behind solving problems using <\/span><b>recursion<\/b> is that we break a large problem down into sub-problems which can be solved using the same procedure in a simpler way. The solutions of the subproblems are then collected together to give the solution to the larger problem.<\/p><p style=\"font-size: 16px;font-style: normal;font-weight: 400\">For the tower of Hanoi problem, the important thing to realise is that because of how the puzzle works, at some stage we will have the situation shown below where\u00a0<span style=\"font-size: 16px;font-style: normal;font-weight: 400\">\\(\\) (N-1) \\)<\/span>\u00a0disks are on rod B and we have to move the largest disk from A to C and then all of the remaining disks from B to C. This means that we can break the problem down into the subproblems of moving\u00a0<span style=\"font-size: 16px;font-style: normal;font-weight: 400\">\\( (N-1) \\)\u00a0<\/span>disks from A to B, moving A to C (which is trivial) and then moving \\( (N-1) \\) from B to C.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-ba05fd4 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"ba05fd4\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-0803d4c\" data-id=\"0803d4c\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-b336240 elementor-widget elementor-widget-image\" data-id=\"b336240\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"image.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<img decoding=\"async\" width=\"1024\" height=\"408\" src=\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-content\/uploads\/sites\/24\/2021\/04\/TOH2-1024x408.png\" class=\"attachment-large size-large wp-image-1201\" alt=\"TOH2\" srcset=\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-content\/uploads\/sites\/24\/2021\/04\/TOH2-1024x408.png 1024w, https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-content\/uploads\/sites\/24\/2021\/04\/TOH2-300x119.png 300w, https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-content\/uploads\/sites\/24\/2021\/04\/TOH2-768x306.png 768w, https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-content\/uploads\/sites\/24\/2021\/04\/TOH2-1536x612.png 1536w, https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-content\/uploads\/sites\/24\/2021\/04\/TOH2.png 1750w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/>\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-ce3e638 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"ce3e638\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-d34b6cc\" data-id=\"d34b6cc\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-3d44110 elementor-widget elementor-widget-text-editor\" data-id=\"3d44110\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p><span style=\"font-size: 16px;font-style: normal;font-weight: 400\">If we were going to write this like a function\u00a0<\/span><span style=\"font-size: 16px;font-style: normal;font-weight: 400\">(called TOH)<\/span><span style=\"font-size: 16px;font-style: normal;font-weight: 400\">\u00a0in a programming language where we would take in a series of arguments and then produce an output which is the solution to the TOH problem, we would get something that looks like this:<\/span><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-c5e1117 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"c5e1117\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-7f3f2cc\" data-id=\"7f3f2cc\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-9621205 elementor-widget elementor-widget-image\" data-id=\"9621205\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"image.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<img decoding=\"async\" width=\"664\" height=\"634\" src=\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-content\/uploads\/sites\/24\/2021\/04\/TOHfunction.png\" class=\"attachment-large size-large wp-image-1110\" alt=\"TOHfunction\" srcset=\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-content\/uploads\/sites\/24\/2021\/04\/TOHfunction.png 664w, https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-content\/uploads\/sites\/24\/2021\/04\/TOHfunction-300x286.png 300w\" sizes=\"(max-width: 664px) 100vw, 664px\" \/>\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-5714eb7 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"5714eb7\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-11264fa\" data-id=\"11264fa\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-de12893 elementor-widget elementor-widget-text-editor\" data-id=\"de12893\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p style=\"font-size: 16px;font-style: normal;font-weight: 400\">The function TOH takes four arguments; the first is the number of disks being moved , \\( N \\), and the next three arguments indicate the rod being moved from, the intermediate rod and the rod being moved to respectively. In this case, the first function wants to move\u00a0<span style=\"font-size: 16px;font-style: normal;font-weight: 400\">\\( N \\)<\/span>\u00a0disks from rod A to rod C via rod B. As I mentioned earlier, this can be decomposed into the problem of moving the\u00a0<span style=\"font-size: 16px;font-style: normal;font-weight: 400\">\\( (N-1) \\)\u00a0<\/span>smaller disks from A to B then moving the largest disk from A to C and then moving the\u00a0<span style=\"font-size: 16px;font-style: normal;font-weight: 400\">\\( (N-1) \\)<\/span>\u00a0smaller disks from B to C. Notice how this is achieved in this function by executing TOH within TOH with\u00a0<span style=\"font-size: 16px;font-style: normal;font-weight: 400\">\\( (N-1) \\)<\/span>\u00a0disks being moved from A to B via C then moving A to C and then executing TOH again with\u00a0<span style=\"font-size: 16px;font-style: normal;font-weight: 400\">\\( (N-1) \\)<\/span>\u00a0disks being moved from B to C via A. These TOH functions with\u00a0<span style=\"font-size: 16px;font-style: normal;font-weight: 400\">\\( (N-1) \\)<\/span>\u00a0disks as arguments will themselves call TOH functions with\u00a0<span style=\"font-size: 16px;font-style: normal;font-weight: 400\">\\( (N-2) \\)<\/span>\u00a0disks and so on until TOH is called with \\( 0 \\) disks as an argument and the function STOPS. This repeated calling of a function within itself is a feature that is common to any kind of recursive method.<\/p><p style=\"font-size: 16px;font-style: normal;font-weight: 400\">\u00a0<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-0946558 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"0946558\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-b02702c\" data-id=\"b02702c\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-1e92dd4 elementor-widget elementor-widget-image\" data-id=\"1e92dd4\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"image.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<a href=\"http:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-content\/uploads\/sites\/24\/2021\/04\/Recursion-diagrams.png\" data-elementor-open-lightbox=\"yes\" data-elementor-lightbox-title=\"Recursion diagrams\" data-e-action-hash=\"#elementor-action%3Aaction%3Dlightbox%26settings%3DeyJpZCI6IjEyMDkiLCJ1cmwiOiJodHRwczpcL1wvd3d3LmxhbmNhc3Rlci5hYy51a1wvc3Rvci1pLXN0dWRlbnQtc2l0ZXNcL2phY2stdHJhaW5lclwvd3AtY29udGVudFwvdXBsb2Fkc1wvc2l0ZXNcLzI0XC8yMDIxXC8wNFwvUmVjdXJzaW9uLWRpYWdyYW1zLnBuZyJ9\">\n\t\t\t\t\t\t\t<img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"370\" src=\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-content\/uploads\/sites\/24\/2021\/04\/Recursion-diagrams-1024x370.png\" class=\"attachment-large size-large wp-image-1209\" alt=\"Recursion diagrams\" srcset=\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-content\/uploads\/sites\/24\/2021\/04\/Recursion-diagrams-1024x370.png 1024w, https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-content\/uploads\/sites\/24\/2021\/04\/Recursion-diagrams-300x108.png 300w, https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-content\/uploads\/sites\/24\/2021\/04\/Recursion-diagrams-768x278.png 768w, https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-content\/uploads\/sites\/24\/2021\/04\/Recursion-diagrams-1536x555.png 1536w, https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-content\/uploads\/sites\/24\/2021\/04\/Recursion-diagrams.png 2002w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/>\t\t\t\t\t\t\t\t<\/a>\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-3de8c72 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"3de8c72\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-6d04fc9\" data-id=\"6d04fc9\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-cdd2413 elementor-widget elementor-widget-image\" data-id=\"cdd2413\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"image.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<a href=\"http:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-content\/uploads\/sites\/24\/2021\/04\/Recursion-functions.png\" data-elementor-open-lightbox=\"yes\" data-elementor-lightbox-title=\"Recursion functions\" data-e-action-hash=\"#elementor-action%3Aaction%3Dlightbox%26settings%3DeyJpZCI6IjEyMTAiLCJ1cmwiOiJodHRwczpcL1wvd3d3LmxhbmNhc3Rlci5hYy51a1wvc3Rvci1pLXN0dWRlbnQtc2l0ZXNcL2phY2stdHJhaW5lclwvd3AtY29udGVudFwvdXBsb2Fkc1wvc2l0ZXNcLzI0XC8yMDIxXC8wNFwvUmVjdXJzaW9uLWZ1bmN0aW9ucy5wbmcifQ%3D%3D\">\n\t\t\t\t\t\t\t<img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"393\" src=\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-content\/uploads\/sites\/24\/2021\/04\/Recursion-functions-1024x393.png\" class=\"attachment-large size-large wp-image-1210\" alt=\"Recursion functions\" srcset=\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-content\/uploads\/sites\/24\/2021\/04\/Recursion-functions-1024x393.png 1024w, https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-content\/uploads\/sites\/24\/2021\/04\/Recursion-functions-300x115.png 300w, https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-content\/uploads\/sites\/24\/2021\/04\/Recursion-functions-768x295.png 768w, https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-content\/uploads\/sites\/24\/2021\/04\/Recursion-functions-1536x590.png 1536w, https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-content\/uploads\/sites\/24\/2021\/04\/Recursion-functions.png 1972w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/>\t\t\t\t\t\t\t\t<\/a>\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-972342e elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"972342e\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-611fc07\" data-id=\"611fc07\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-c54cde6 elementor-widget elementor-widget-text-editor\" data-id=\"c54cde6\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p style=\"font-size: 16px;font-style: normal;font-weight: 400\">In my opinion, the best way to visualise this recursion is by trying an example. To this end, I have included 2 tree diagrams (Click these diagrams to enlarge them). The first shows which disks are being moved by each TOH function. Notice that the steps highlighted in red are a step by step solution to the puzzle. The second diagram shows the functions to which these steps correspond. Notice that the first function calls the second row of functions that calls the third row. I haven\u2019t included the final row of function calls because these have an \\( N = 0 \\) argument and therefore stop without making an action.<\/p>\n<p style=\"font-size: 16px;font-style: normal;font-weight: 400\"><span style=\"font-size: 16px;font-style: normal;font-weight: 400\">So, we now how a set of rules that we can employ to solve the tower of Hanoi problem for any number of disks, right? In theory, yes. In practice, no. The reason behind this can be discovered by looking at the number of steps in the solution as \\( N \\) gets larger. &nbsp;For our example with&nbsp;<\/span><span style=\"font-size: 16px;font-style: normal;font-weight: 400\">\\( N = 3 \\)<\/span><span style=\"font-size: 16px;font-style: normal;font-weight: 400\">&nbsp;disks given here, the number of steps to solve the puzzle is 7. It turns out that the number of steps taken to solve the puzzle as a function of&nbsp;<\/span><span style=\"font-size: 16px;font-style: normal;font-weight: 400\">\\( N \\)<\/span><span style=\"font-size: 16px;font-style: normal;font-weight: 400\">&nbsp;is&nbsp;<\/span><span style=\"font-size: 16px;font-style: normal;font-weight: 400\">\\( 2^{N} &#8211; 1 \\)<\/span><span style=\"font-size: 16px;font-style: normal;font-weight: 400\">. This is a big problem as you may realise having read my previous blog on the <a href=\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/the-p-vs-np-problem\/\">P vs NP problem<\/a> . A scaling with&nbsp;<\/span><span style=\"font-size: 16px;font-style: normal;font-weight: 400\">\\( N \\)<\/span><span style=\"font-size: 16px;font-style: normal;font-weight: 400\">&nbsp;like this means that for&nbsp;<\/span><span style=\"font-size: 16px;font-style: normal;font-weight: 400\">\\( N = 64 \\)<\/span><span style=\"font-size: 16px;font-style: normal;font-weight: 400\">, which is a fairly modest number the solution has so many steps that even at the rate of one disk moved per second, it would take 42 times the age of the universe to solve the puzzle.&nbsp; Even worse, even if an omnipotent being gave us the solution it would still take this long just to check he wasn\u2019t lying to us. Ouch! Although maybe it\u2019s not such as bad thing. There is a legend about some Indian Brahmin priests that are trying to solve the puzzle with 64 golden disks and should they solve it, the end of the world will come. It\u2019s comforting to know that your plans won\u2019t be interrupted by the world ending, at least for the next 585 billion years.<\/span><\/p>\n<p style=\"font-size: 16px;font-style: normal;font-weight: 400\"><span style=\"font-size: 16px;font-weight: 700\">Relevant Links<\/span><\/p>\n<p style=\"font-size: 16px;font-style: normal;font-weight: 400\"><a href=\"http:\/\/Relevant Links Statement of the P vs NP problem Minesweeper is NP complete Proposed (and debunked) proofs\">Youtube video that covers this topic with some nice animations!<\/a><\/p>\n<p style=\"font-size: 16px;font-style: normal;font-weight: 400\"><a href=\"https:\/\/science.sciencemag.org\/content\/153\/3731\/34\/tab-pdf\">Paper on dynamic programming &#8211; A recursive solution method to optimisation problems frequently encountered in Operational Research<\/a><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"<p>In the puzzle known as Tower of Hanoi (named after the style of buddhist temples in Vietnam, I assume) , you have three rods or pegs and a number of disks of different diameters. The puzzle begins with a set up like the one shown below (for three disks) where all of the disks are [&hellip;]<\/p>\n","protected":false},"author":19,"featured_media":1079,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"site-sidebar-layout":"default","site-content-layout":"default","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"default","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"slim_seo":{"title":"Solving the Tower of Hanoi puzzle using recursion - JACK TRAINER","description":"In the puzzle known as Tower of Hanoi (named after the style of buddhist temples in Vietnam, I assume) , you have three rods or pegs and a number of disks of di"},"footnotes":""},"categories":[14,28],"tags":[19,31,30],"class_list":["post-1069","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-computer-science","category-operational-research","tag-algorithms","tag-puzzles","tag-recursion"],"_links":{"self":[{"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-json\/wp\/v2\/posts\/1069","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-json\/wp\/v2\/users\/19"}],"replies":[{"embeddable":true,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-json\/wp\/v2\/comments?post=1069"}],"version-history":[{"count":29,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-json\/wp\/v2\/posts\/1069\/revisions"}],"predecessor-version":[{"id":1213,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-json\/wp\/v2\/posts\/1069\/revisions\/1213"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-json\/wp\/v2\/media\/1079"}],"wp:attachment":[{"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-json\/wp\/v2\/media?parent=1069"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-json\/wp\/v2\/categories?post=1069"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-json\/wp\/v2\/tags?post=1069"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}