API tools faq
paste
Advertisement
Guest User

wk5

a guest
Feb 18th, 2019
104
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
HTML 5 19.16 KB | None | 0 0
raw download clone embed print report
  1.  
  2. <!DOCTYPE html>
  3. <html lang="en">
  4.  
  5. <head>
  6.  
  7. <meta charset="utf-8" />
  8. <meta name="viewport" content="width=device-width,initial-scale=1.0" />
  9. <meta name="description" content="Tabbed List" />
  10. <title>Data Structures &amp; Algorithms : Recursion</title>
  11.    
  12. <link rel="stylesheet" type="text/css" href="css/Tabs.css" />
  13. <link rel="stylesheet" type="text/css" href="css/printstyle.css" media="print" />
  14.    
  15. <script src="js/jquery-2.1.4.min.js"></script>  
  16. <script src="js/tabbed-list.js"></script>
  17.    
  18. <script src='https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js?config=TeX-MML-AM_CHTML'>
  19.     MathJax.Hub.Config({
  20.         jax:["input/TeX","output/HTML-CSS"],
  21.         tex2jax: {inlineMath: [["$","$"],["\\(","\\)"]]},
  22.         displayAlign: "left"
  23.        
  24.     });
  25. </script>
  26.  
  27. </head>
  28.  
  29. <body oncontextmenu="return false">
  30.  
  31.     <!-- Beginning of Wrapper -->
  32. <div id="wrapper">
  33. <!-- Start of Navigation Menu -->
  34. <div id="main">
  35.     <div class="container">
  36.         <header role="heading">
  37.         <div id="main-head">05</div>
  38.         </header>
  39.         <div id="spacer"></div>
  40.         <nav role="navigation">
  41.         <ul id="nav-list" role="menubar">
  42.             <li class="active" role="menuitem" accesskey="1">Intro</li>
  43.             <li role="menuitem" accesskey="2">5.1</li>
  44.             <li role="menuitem" accesskey="3">5.2</li>
  45.             <li role="menuitem" accesskey="4">5.3</li>
  46.             <li role="menuitem" accesskey="5">5.4</li>
  47.             <li role="menuitem" accesskey="6">5.5</li>
  48.             <li role="menuitem" accesskey="7">5.6</li>
  49.             <li role="menuitem" accesskey="8">5.7</li>
  50.             <li role="menuitem" accesskey="9">5.8</li>
  51.             <li role="menuitem" accesskey="0">5.9</li>
  52.  
  53.         </ul>
  54.         </nav>
  55. <!-- End of Menu -->
  56.        
  57. <!-- Start of Content Area -->
  58.         <main role="main">
  59.         <ul id="content-Area" role="presentation">
  60.             <li class="active" role="presentation">
  61.                 <h1>Introduction</h1>
  62.                 <p></p>
  63.                 <p class="mainpara">A recursive method calls itself in the method's body.  This means that before the original method calls return, another call to the same method is issued from its body.  This might seem a strange way of writing programs but very elegant solutions can be written using recursion.</p>
  64.                
  65.                 <p class="mainpara">Not all problems are amenable to a recursive solution.  However, the following are the essential conditions for recursion:</p>
  66.                 <p class="mainpara" style="padding-left:3.000em;">a. A recursive call that acts on a smaller and smaller version of the original problem.</p>
  67.                 <p class="mainpara" style="padding-left:3.000em;">b. A terminating or base case, at which further recursion calls stop and the control/values start returning towards the first call to the method.</p>
  68.                 <p></p>
  69.                 <p class="mainpara">Failing to abide by above conditions can result in the method calling itself repeatedly as in an infinite loop.</p>
  70.                 <p></p>
  71.                 <dl>
  72.                     <dt style="padding-bottom:0.350em;">This week will:</dt>
  73.                     <dd style="padding-bottom:0.350em;">Understand how recursive solutions can be written</dd>
  74.                     <dd style="padding-bottom:0.350em;">Introduce some simple exercises of recursion</dd>
  75.                     <dd style="padding-bottom:0.350em;">Understand merge sort algorithm</dd>
  76.                 </dl>
  77.                 <p></p>
  78.                 <p class="mainpara">In general any problem that can be solved by recursion can also have an iterative solution.  Very elegant solutions can be written using recursion, such as for tree traversals as would be covered later on.</p>
  79.             </li>
  80.             <li role="presentation">
  81.                 <h1>Recursion</h1>
  82.                 <p></p>
  83.                 <p class="mainpara">In computer programming, recursion is concerened with the ability of a function (or subroutine) to call itself.</p>
  84.                 <p></p>
  85.                 <p class="subheading">Factorial Function</p>
  86.                 <p class="mainpara">On of the best known recursive functions is the factorial function.  This is defined as:</p>
  87.                 <p class="mainpara"><span style="padding-left:2.500em;">$n! = (n)(n-1)(n-2)...(2)(1)$</span></p>
  88.                 <p class="mainpara"><span style="padding-left:3.800em;">$ = (n)(n-1)!$</span></p>
  89.                 <p class="mainpara">also $(n-1)! = (n - 1)(n - 2)!$ and so on</p>
  90.                 <p></p>
  91.                 <p class="subheading">Example</p>
  92.                 <p class="mainpara">$3!  =  (3)(2)(1)  =  6$</p>
  93.                 <p class="mainpara">$4!  =  (4)(3!)      =  (4)(6)    = 24$</p>
  94.                 <p class="mainpara">$5!  =  (5)(4!)      =  (5)(24)  = 120$</p>
  95.                 <p></p>
  96.                 <p class="mainpara">Now as the factorial function is a function we have values for $0!$ and $1!$.</p>
  97.                 <p class="mainpara"><span style="padding-left:2.500em;">$0! = 1$</span></p>
  98.                 <p class="mainpara"><span style="padding-left:2.500em;">$1! = 1$</span></p>
  99.                 <p class="mainpara">The factorial function is a special case of the gamma function where $T(n) - nT(n-1)$.</p>
  100.             </li>
  101.             <li role="presentation">
  102.                 <h1>Programming a Factorial Function</h1>
  103.                 <p></p>
  104.                 <p class="mainpara">We might have an intial attempt at writing code as follows:</p>
  105.                 <p class="mainpara"><span style="padding-left:2.500em;">declare function factorial $(int n)$</span></p>
  106.                 <p class="mainpara"><span style="padding-left:2.500em;">return $n \times$ factorial $(n -1)$</span></p>
  107.                 <p class="mainpara">If this psuedo code is tested, then we would have for example for $n = 3$:</p>
  108.                 <figure>
  109.                     <img src="images/Fig1.png" alt="Factorial Function Diagram" style="width:60%; height:auto">
  110.                 </figure>
  111.                 <p class="mainpara">Clearly, there is a problem, as there is no end to the call of the function, the computer would eventually run out of stack space and crash</p>
  112.             </li>
  113.             <li role="presentation">
  114.                 <p class="mainpara">We need a halting case ( or base case ) and we need to deal with incorrect input.</p>
  115.  
  116.                 <p class="mainpara">The $n$ in the factorial function should not be less than $0$.  If it is, an error value can be returned.  Also 0! = 1 and 1! = 1.</p>
  117.  
  118.                 <p class="mainpara">So psuedo code could look like:</p>
  119.                 <p class="mainpara"><span style="padding-left:2.500em;">declare function factorial $(int\; n)$</span></p>
  120.                 <p class="mainpara"><span style="padding-left:3.000em;">if $n &lt; 0$ the return $0$    // error code</span></p>
  121.                 <p class="mainpara"><span style="padding-left:4.000em;">else if $n = 0$ or $n = 1$  return $1$</span></p>
  122.                 <p class="mainpara"><span style="padding-left:4.000em;">else return $n \times$ factorial $(n - 1)$</span></p>
  123.                 <p></p>
  124.                 <p class="mainpara">Now if we look at some examples</p>
  125.                 <p class="mainpara">factorial $(-4) = 0$<span style="padding-left:2.000em;">; return $0$, so it is an error</span></p>
  126.                 <p class="mainpara">factorial $(0)    = 1$</p>
  127.                 <p class="mainpara">factorial $(1)    = 1$</p>
  128.                 <p class="mainpara">factorial $(4)    = (4)(3)(2)(1) = 24$</p>
  129.             </li>
  130.             <li role="presentation">
  131.                  <h1>A Recursive Power Function</h1>
  132.                 <div class="scrollingSection">
  133.                 <p></p>
  134.                 <p class="mainpara">Computes an integer power of a floating point number</p>
  135.                 <p></p>
  136.                 <div class="mainpara">
  137. <pre class="prettyprint">
  138. double power(double base, int exponent) {
  139.     if (exponent &lt; 1) {
  140.         return 1.0;
  141.     } else {
  142.         return power(base, exponent-1) * base;
  143.     }
  144. }
  145. </pre></div>
  146.                 <p></p>
  147.                 <p class="mainpara">The function is called as follows:</p>
  148.                 <p></p>
  149.                 <div class="mainpara">
  150. <pre class="prettyprint">
  151. System.out.println( power(1.7, 3) );
  152. </pre></div>
  153.                 <p></p>
  154.                 <dl>
  155.                 <dt>Initial bindings</dt>
  156.                 <dd>base = 1.7</dd>
  157.                 <dd>exponent = 3</dd>
  158.                 </dl>
  159.                 <p></p>
  160.  
  161.                 <p class="mainpara">This diagram shows how the contents of the call stack change as recursive calls are made. Each time <span style="font-weight:bold;">power</span> executes, it makes another call to <span style="font-weight:bold;">power</span>, and pushes a new stack frame to the call stack. The value of the <span style="font-weight:bold;">exponent</span> parameter is different each time – look at the code to see why. At the fourth call, exponent is now &lt; 1, so the other branch of the if statement executes and power is not called again. This is the stopping condition – without it the recursion would go on forever!</p>
  162.                 <p></p>
  163.                 <p class="subheading2">Call stack with recursive calls</p>
  164.                 <figure>
  165.                 <img src="images/Call-Stack.png" alt="Call Stack with recursive calls" style="width:80%; height:auto">
  166.                 </figure>
  167.                 <p class="mainpara">In the fourth call, power returns 1.0 and that frame is popped from the stack. Execution returns to the third call, which returns the result of calculating:</p>
  168.                 <p></p>
  169.                 <p class="subheading2" role="heading">power(base, exponent-1) * base</p>
  170.                 <p class="mainpara">which is:</p>
  171.  
  172.                 <span class="subheading2" style="padding-left:1.800em;">value returned by fourth call * base</span><br/>
  173.                 <span class="subheading2" style="padding-left:1.800em;">= 1.0 * 1.7</span><br/>
  174.                 <span class="subheading2" style="padding-left:1.800em;">= 1.7</span>
  175.  
  176.                 <p class="mainpara">Now the third frame is popped from the stack and execution returns to the second call, which in turn returns the result of calculating:</p>
  177.  
  178.                 <span class="subheading2" style="padding-left:1.800em;">value returned by third call * base</span><br/>
  179.                 <span class="subheading2" style="padding-left:1.800em;">= 1.7 * 1.7</span><br/>
  180.                 <span class="subheading2" style="padding-left:1.800em;">= 2.89</span>
  181.    
  182.                 <p class="mainpara">Now the second frame is popped from the stack and execution returns to the first call, which in turn returns the result of calculating:</p>
  183.  
  184.                 <span class="subheading2" style="padding-left:1.800em;">value returned by second call * base</span><br/>
  185.                 <span class="subheading2" style="padding-left:1.800em;">= 2.89 * 1.7</span><br/>
  186.                 <span class="subheading2" style="padding-left:1.800em;">= 4.913</span>
  187.                 <p></p>
  188.                 <dl>
  189.                 <dt>Each return does the following:</dt>
  190.                 <dd>Pops a frame off of the stack</dd>
  191.                 <dd>Restores its data state</dd>
  192.                 <dd>Replaces the call to power with the return value</dd>
  193.                 <dd>Continues execution at the return address</dd>
  194.                 </dl>
  195.                 <p></p>
  196.                 <p class="subheading2" role="heading">Call stack as recursive calls return</p>
  197.                  <figure>
  198.                 <img src="images/Call-Stack2.png" alt="Call Stack with recursive calls" style="width:80%; height:auto">
  199.                 </figure>
  200.                 <p class="subheading2" role="heading">Recursion and RAM</p>
  201.  
  202.                 <p class="mainpara">Recursive functions may require more space in memory than non-recursive calls. With some deeply recursive algorithms this can be a problem.  It is possible to run out of memory space on the stack – <span style="font-weight:bold;">stack overflow</span>.</p>
  203.  
  204.                 <p class="mainpara">It can also be a problem with poorly written recursive functions with bad stopping condition definitions (result is like an infinite loop only on the stack)</p>
  205.  
  206.                 <p class="mainpara">Advantages of recursion</p>
  207.                 <p class="mainpara">Recursion’s big advantage is the elegance with which it embodies the solution to many problems</p>
  208.                 <p class="mainpara">It closely follows the mathematical definition of many functions</p>
  209.                 <p class="mainpara">This makes it easier to prove correctness</p>
  210.                 <p class="mainpara">Some problems are much easier to solve recursively than iteratively, e.g. Towers of Hanoi</p>
  211.                 <p></p>
  212.                     <dl>
  213.                 <dt>Disadvantages of recursion</dt>
  214.                 <dd>Use of system resources slows the process down compared to iterative solutions, although this may not be a big factor on modern machines</dd>
  215.                 <dd>Possibility of stack overflow</dd>
  216.                 <dd>Difficult to ‘think recursively’</dd>
  217.                     </dl>
  218.                 </div>
  219.             </li>
  220.             <li role="presentation">
  221.                 <h1>Fibonacci Numbers</h1>
  222.                 <p></p>
  223.                 <p class="mainpara">The Fibonacci number are also recursive.</p>
  224.                 <p class="mainpara">The numbers start as follows:</p>
  225.                 <p></p>
  226.                 <p class="mainpara">$1, 1, 2, 3, 5, 8, 13, \cdots$</p>
  227.                 <p></p>
  228.                 <p class="mainpara">Now the first number $f_1 = 1$, the second number $f_2 = 1$.</p>
  229.                 <p></p>
  230.                 <p class="mainpara">The third number is formed as follows:</p>
  231.                 <p></p>
  232.                 <p class="mainpara">$f_3 = f_2 + f_1 = 1 + 1 = 2$</p>
  233.                 <p></p>
  234.                 <p class="mainpara">The fourth number is:</p>
  235.                 <p></p>
  236.                 <p class="mainpara">$f_4 = f_3 + f_2 = 2 + 1 = 3$</p>
  237.                 <p></p>
  238.                 <p class="mainpara">In general,</p>
  239.                 <p></p>
  240.                 <p class="mainpara">$f_n = f_{n-1} + f_{n-2}$</p>
  241.                 <p class="mainpara">Strangely though, these numbers appear in computing and in biology in a natrual way.</p>
  242.             </li>
  243.             <li role="presentation">
  244.                <h1>Merge Sort</h1>
  245.                 <p></p>
  246.                 <p class="mainpara">The sorting process is used to arrange the items in a collection, for example an array, in an increasing or decreasing order. Sorting algorithms would be covered in Week 6 and 7 but here we study Merge sort, a very efficient sorting algorithm that is based on divide-and-conquer technique nicely implemented using recursion.</p>
  247.                
  248.                 <p class="mainpara">Merge sort has a time complexity of Ο(n log n).</p>
  249.                 <p class="mainpara">Merge sort has two steps, divide and merge:</p>
  250.                
  251.                 <p class="mainpara" style="padding-left:2.850em; text-indent:-16px;">1) The array is divided into equal halves and this halving process is performed recursively until an array of size one results; an only item in an array is already sorted.</p>
  252.                
  253.                 <p class="mainpara" style="padding-left:2.850em; text-indent:-16px;">2) The merging step is then performed that combines two array halves (that have already been sorted) into one larger array, ultimately combining the whole array by merging (and thus sorting the original array).</p>
  254.                 <p></p>
  255.                 <dl>
  256.                     <dt style="padding-bottom:0.350em;">This merge sort algorithm can be expressed as,</dt>
  257.                     <dd style="padding-bottom:0.350em;">Divide the array in two halves</dd>
  258.                     <dd style="padding-bottom:0.350em;">Merge sort the first half</dd>
  259.                     <dd style="padding-bottom:0.350em;">Merge sort the second half</dd>
  260.                     <dd style="padding-bottom:0.350em;">Merge the two halves</dd>
  261.                 </dl>
  262.             </li>
  263.             <li role="presentation">
  264.              <h1>Psuedocode</h1>
  265.                 <p></p>
  266.                 <div class="mainpara">
  267. <pre>
  268. mergeSort ( array arr of size n )
  269. {
  270.        if ( n == 1 ) return arr
  271.        left_arr = arr[0] to arr[n/2]
  272.        right_arr = arr[n/2+1] to arr[n]
  273.        left_arr = mergeSort( left_arr )
  274.        right_arr = mergeSort( right_arr )
  275.        return merge( left_arr, right_arr )
  276. }
  277.  
  278. merge(leftarr as array, rightarr as array)
  279. {
  280. resultarr as array
  281.        
  282. while ( length(leftarr) > 0 and length(rightarr) > 0)
  283.  
  284.         if(smallest item in leftarr &lt; smallest item in rightarr)
  285.             add (smallest item in leftarr) to resultarr
  286.             remove (smallest item from leftarr)
  287.         else
  288.             add (smallest item in rightarr) to resultarr
  289.             remove (smallest item from rightarr)
  290.  
  291.         if length(leftarr) > 0
  292.         add leftarr to resultarr
  293.         if length(rightarr) > 0
  294.         add rightarr to resultarr
  295.    
  296. return resultarr
  297. }
  298. </pre>
  299.                 </div>
  300.             </li>
  301.             <li role="presentation">
  302.                <h1>Recursive Calls in Merge Sort</h1>
  303.                 <div class="scrollingSection">
  304.                 <p></p>
  305.                 <p class="mainpara">The array is recursively divided into two halves until both halves consist of only a single item, which can be considered sorted. At this point, the merge is performed that puts the items from both halves in a sorted order. This merge process is repeated until whole of the array is sorted.</p>
  306.                 <figure>
  307.                     <img src="images/Fig2.png" alt="Recursive Calls in Merge Sort Diagram" style="width:70%; height:auto"/>
  308.                 </figure>
  309.                 </div>
  310.             </li>
  311.             <li role="presentation">
  312.                <h1>Summary</h1>
  313.                 <p></p>
  314.                 <dl>
  315.                     <dt></dt>
  316.                     <dd style="padding-bottom:0.350em;">Recursion is a problem-solving technique where a method calls itself again and again on progressively smaller version of the original problem.</dd>
  317.                     <dd style="padding-bottom:0.350em;">A recursive solution must have a terminating or base case at which point no further method calls are made.</dd>
  318.                     <dd style="padding-bottom:0.350em;">Recursion can result in very simple and elegant solutions.</dd>
  319.                     <dd style="padding-bottom:0.350em;">Recursive solutions are slower and require more memory compared to iterative solutions due to maintaining the call stack.</dd>
  320.                     <dd style="padding-bottom:0.350em;">Merge sort is an efficient sorting algorithm which uses a divide-and-conquer strategy.</dd>
  321.                 </dl>
  322.             </li>
  323.         </ul>
  324.         </main>
  325.    
  326. <!--  End of Content Area -->
  327.  
  328. <!-- Beginning of Footer -->
  329. <footer>
  330.    School of Computing, Engineering and Built Environment
  331. </footer>
  332.      </div>
  333. </div>  
  334. <!-- End of footer -->
  335.  
  336. </div>
  337.  
  338.  <!-- End of wrapper -->
  339. </body>
  340. </html>
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!