StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Well if you use recursion it's good to know the meaning of the function. This helps a lot to understand why the method is recursive. Furthermore calculating the function on paper is mostly done by a method called "dispatching". In this case you see that <code>mystrey(0) = 0</code> (the if-case).</p> <p>If you want to calculate the value of mystrey(10) you know it's a sum of 10, mystrey(1) and mystrey(2).</p> <p>You simply create a table where one can put:</p> <pre><code>0: 0 10: 10+f(1)+f(2) </code></pre> <p>we now calculate the value of the function with the highest argument so mystrey(2):</p> <pre><code>2: 2+f(0)+f(0) </code></pre> <p>we know the value of f(0), it's already in the table, so</p> <pre><code>2: 2+0+0=2 </code></pre> <p>now we calculate <code>f(1)=1</code></p> <p>We finally conclude that <code>f(10)=10+f(1)+f(2)=10+1+2=13</code>.</p> <p>Using a table becomes helpfull when there is a lot of recursion. A lot of times recursion results in overlap, where a huge number of times the function with the same arguments must be computed. With dispatching one can avoid the "branching". One can see recursion as a tree. Because <code>f(0)</code> has a fixed value this is called the "base case" and are the leafs of the tree. The other function values are called "branches". When calculating <code>f(10)</code> we need to calculate <code>f(1)</code> and <code>f(2)</code>, so one could draw edges from <code>f(10)</code> to <code>f(2)</code> and <code>f(1)</code>. And so one could repeat the process.</p> <p>Also in most cases a good programmer will program this dispatching in the algorithm. This is of course done by declaring an array an store values in the array and perform a lookup on it.</p> <p>In recursion theory it's common the recursion consist of two parts: a base case part, where answers are "hard coded" for some function calls (in your example when <code>x=0</code>), and a recursive part where <code>f(x)</code> is written in parts of <code>f(y)</code>. In general one can use dispatching by building an intial table with the hard coded values, and calculate the value of a specific <code>x</code> by starting to fill in the entry of <code>x</code> in the table, and work down.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload