Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Tail recursion means you must be directly returning the result of a recursive call, with no further manipulation.</p> <p>The obvious recursion in map is to compute the function on one element of the list, then use a recursive call to process the rest of the list. However, you need to combine the result of processing one element with the result of processing the rest of the list, which requires an operation after the recursive call.</p> <p>A very common pattern for avoiding that is to move the combination <em>inside</em> the recursive call; you pass in the processed element as an argument, and make it part of <code>map</code>'s responsibility to do the combining as well.</p> <pre><code>def map(l, f): if l == []: return [] else: return map(l[1:], f, f(l[0])) </code></pre> <p>Now it's tail recursive! But it's also obviously wrong. In the tail recursive call, we're passing 3 arguments, but map only takes two arguments. And then there's the question of what do we do with the 3rd value. In the base case (when the list is empty), it's obvious: return a list containing the information passed in. In the recursive case, we're computing a new value, and we have this extra parameter passed in from the top, and we have the recursive call. The new value and the extra parameter need to be rolled up together to be passed into the recursive call, so that the recursive call can be tail recursive. All of which suggests the following:</p> <pre><code>def map(l, f): return map_acc(l, f, []) def map_acc(l, f, a): if l == []: return a else: b = a + [f(l[0])] return map_acc(l[1:], f, b) </code></pre> <p>Which can be expressed more concisely and Pythonically as other answers have shown, without resorting to a separate helper function. But this shows a general way of turning non-tail-recursive functions into tail recursive functions.</p> <p>In the above, <code>a</code> is called an <em>accumulator</em>. The general idea is to move the operations you normally do <em>after</em> a recursive call into the next recursive call, by wrapping up the work outer calls have done "so far" and passing that on in an accumulator.</p> <p>If <code>map</code> can be thought of as meaning "call <code>f</code> on every element of <code>l</code>, and return a list of the results", <code>map_acc</code> can be thought of as meaning "call <code>f</code> on every element of <code>l</code>, returning a list of the results combined with <code>a</code>, a list of results already produced".</p>
    singulars
    1. This table or related slice is empty.
    1. POCoverting a recursive function to a tail recursive one in python
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USBen
    1. USBen
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COWould it be ok ,instead of typing another function, to have the third parameter with a default value as an argument in the main function? Which gets modified once the first call is done.
      singulars
      1. PO
      1. USJuan Gallostra
    2. CO@JuanGallostra Yep, that works (so long as you're careful about never mutating or returning values that might be bound to the default argument in some code paths).
      singulars
      1. PO
      1. USBen
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

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