<?xml version="1.0"?>
<api>
  <query-continue>
    <allpages gapcontinue="SAGE_technical_support_Number_¤_P.h.o.n.e_Peachtree_!(!1844!-!313!-!4859!_Ph.on.e_t.e.c.h_su.p.port_number" />
  </query-continue>
  <query>
    <pages>
      <page pageid="105" ns="0" title="Recursion">
        <revisions>
          <rev contentformat="text/x-wiki" contentmodel="wikitext" xml:space="preserve">{{C-class}}
'''Recursion''' is a technique for solving a large computational problem by repeatedly applying the same procedure(s) to reduce it to successively smaller problems. A recursive procedure has two parts: one or more ''base cases'' and a ''recursive step''. Base cases are predetermined solutions for the simplest versions of the problem — if the given problem is a base case, no further computation is necessary to get the result. The recursive step is a set of rules that eventually reduces all versions of the problem to one of the base cases when applied repeatedly.

''Infinite recursion'' occurs if there is no base case or the recursive step does not make progress towards its base case(s).

Example for how a recursive function looks:
&lt;syntaxhighlight lang=&quot;python&quot;&gt;
def fn(input):
    if &lt;base case&gt;:
        return ...
    else:
        return &lt;combine input and fn(input_reduced)&gt;
&lt;/syntaxhighlight&gt;


==Simple recursion==
In simple recursion — the most straightforward and common form of recursion — there is usually only one base case, and in the recursive step, the recursive procedure calls itself only once. 

===Analogy===
Consider this procedure for learning the definition of recursion: &quot;If you are Andrew Huang, you already know the definition. If not, find someone who is standing closer to Andrew Huang than you are and ask them what the definition of recursion is.&quot; Here, the base case is being Andrew Huang — once you reach this situation, no further work is necessary to get the definition of recursion. If you are not yet at a base case, the recursive step is to ask someone who is closer to Andrew, reducing the problem closer to the base case.

Let's call the procedure &lt;code&gt;def_recursion&lt;/code&gt;. We can think about it in terms of the ''stack'' from [[environment diagram]]s. Suppose Matthew, Rohin, and Andrew are standing in a line. Matthew wants to know the definition of recursion, so his call to &lt;code&gt;def_recursion&lt;/code&gt; is pushed onto the stack. He isn't Andrew, so must find someone standing closer to Andrew than he is and ask them for the definition. So Matthew asks Rohin for the definition of recursion. Rohin's call to the ''same'' &lt;code&gt;def_recursion&lt;/code&gt; function is pushed on top of Matthew's call. Rohin is also not Andrew, so he must ask someone standing closer to Andrew than he is — in this case, it's Andrew himself. Now Andrew's call to &lt;code&gt;def_recursion&lt;/code&gt; is pushed on top of Rohin's call. 

Andrew is a base case, so he already knows the definition and immediately returns it to Rohin, and Andrew's frame pops off the stack. Now Rohin has the definition of recursion, which he can return to Matthew. Once he returns, Rohin's frame pops off the stack. Now Matthew's frame is the only one on the stack, and he has the definition of recursion. This was the initial goal, so Matthew's frame can return and pop off, leaving the stack empty.

In pseudocode, &lt;code&gt;def_recursion&lt;/code&gt;, which takes in the person who wants to know the definition of recursion as a parameter, can be written like this:

&lt;syntaxhighlight lang=&quot;python&quot;&gt;
def def_recursion(you):
    if you == AndrewHuang:
        return knowledge
    else:
        return def_recursion(someone closer to AndrewHuang)
&lt;/syntaxhighlight&gt;

Notice that in the recursive step, the same procedure is called again, but on a simpler version of the problem every time. If there were no base case (no one knew what recursion was), or the recursive step didn't make the problem smaller (everyone asked people ''further'' from Andrew what the answer was), then the recursion can malfunction and go into an infinite loop.

===Examples===
An example of simple recursion is the &lt;code&gt;factorial&lt;/code&gt; function:

&lt;syntaxhighlight lang=&quot;python&quot;&gt;
def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)
&lt;/syntaxhighlight&gt;

Notice that the &lt;code&gt;factorial&lt;/code&gt; procedure is called only once in the body of the recursive procedure. However, it is possible for a call to the function to appear in multiple places in the function body — if only one of those calls is ever executed in each frame, the function still exhibits simple recursion. For example, consider the function that raises a base &lt;code&gt;b&lt;/code&gt; to a power &lt;code&gt;p&lt;/code&gt; through a recursive procedure called ''repeated squaring'':

&lt;syntaxhighlight lang=&quot;python&quot;&gt;
def pow(b, p):
    if p == 0:
        return 1
    elif p % 2 == 0:
        x = pow(b, p // 2)
        return x * x
    else:
        x = pow(b, p // 2)
        return b * x * x
&lt;/syntaxhighlight&gt;

Here, the recursive call to &lt;code&gt;pow&lt;/code&gt; appears twice — once in the &lt;code&gt;elif&lt;/code&gt; clause, once in the &lt;code&gt;else&lt;/code&gt; clause. However, the whole procedure is still simply recursive, because only ''one'' of those else clauses is ever triggered in each recursive call, meaning the procedure can only ever call itself once per frame.

==Tree recursion==
A [[function]] is ''tree recursive'' if the recursive step contains more than one call to the same function. Tree recursive functions generally have more base cases than simply recursive functions as well, though this is not a necessary condition. If a tree recursive function makes repeated computations, it is more optimal to store previous return values rather than perform expensive recomputations. This technique can be implemented through [[memoization]].

===Analogy===
A tree recursive procedure can naturally be used to answer the question &quot;How many ancestors do I have, up to a certain number of generations?&quot; One natural way to answer this question is to say &quot;I have a mother and a father, making two ancestors. Additionally, my mother's ancestors are my ancestors, and my father's ancestors are my ancestors.&quot; Consider the following pseudocode:

&lt;syntaxhighlight lang=&quot;python&quot;&gt;
def num_ancestors(you, num_gen):
    if num_gen == 0:
        return 0
    else:
        return 2 + num_ancestors(mom, num_gen - 1) + num_ancestors(dad, num_gen - 1)
&lt;/syntaxhighlight&gt;

The base case occurs when we only care about ancestors 0 generations up — that is, when we only care about &lt;code&gt;you&lt;/code&gt;. Since you have no ancestors who are 0 generations older than you, we return 0. The recursive call then adds up your parents' ancestors, and adds 2 for your parents themselves. 

If we wanted to count up all your ancestors two generations up, we would start with a call to &lt;code&gt;num_ancestors(you, 2)&lt;/code&gt;. In order to compute that, we need to computer &lt;code&gt;num_ancestors(your_mom, 1)&lt;/code&gt; and &lt;code&gt;num_ancestors(your_dad, 1)&lt;/code&gt;. In order to compute &lt;code&gt;num_ancestors(your_mom, 1)&lt;/code&gt;, we must compute &lt;code&gt;num_ancestors(your_maternal_grandma, 0)&lt;/code&gt; and &lt;code&gt;num_ancestors(your_maternal_grandpa, 0)&lt;/code&gt;. Similarly, in order to compute your dad's call, we must make a call to each of your paternal grandparents.

Until &lt;code&gt;num_gen&lt;/code&gt; is equal to 0, each function call to a person produces ''two'' additional calls to the &lt;code&gt;num_ancestors&lt;/code&gt; function. In general, tree recursive functions are distinguished from simply recursive functions by generating more than one call to the same function in the recursive step. If we draw a line from each frame to the frames it directly generates, the pattern of calls looks like a tree called the ''call tree'', with each &quot;root&quot; having two &quot;branches.&quot; Here, the call tree mirrors the family tree.

===Examples===
==== Fibonacci numbers ====
Consider this Python code for generating the nth Fibonacci number:
&lt;syntaxhighlight lang=&quot;python&quot;&gt;
def fib(n):
    if n == 0:
        return 1
    if n == 1:
        return 1
    return fib(n - 2) + fib(n - 1)
&lt;/syntaxhighlight&gt;
The call tree for the &lt;code&gt;fib&lt;/code&gt; function looks similar to the call tree for the &lt;code&gt;num_ancestors&lt;/code&gt; function, with each function call that was not a base case generating two more calls to &lt;code&gt;fib&lt;/code&gt;.
[[File:Fib call tree.png|thumb|left|300px|Call tree for &lt;code&gt;fib&lt;/code&gt;]]
{{clear}}

==== Towers of Hanoi ====
{{Main|Towers of Hanoi}}

==== Power set ====
{{Main|Power set}}

==Mutual recursion==

A pair of functions are ''mutually recursive'' if they each make recursive calls to each other and are thus defined in terms of one another. 

The following example of two mutually recursive functions is taken from &quot;''Abstraction'': Trees: Mutual Recursion&quot; by Harvey and Wright (1999): 


(define (count-leaves tree)
  (if (leaf? tree)
      1
      (count-leaves-in-forest (children tree))))
 
(define (count-leaves-in-forest forest)
  (if (null? forest)
      0
      (+ (count-leaves (car forest))
         (count-leaves-in-forest (cdr forest)))))

==Tail recursion==
A function is ''tail recursive'' if the result of any recursive calls made in a function is immediately returned.  Tail recursive functions do not make further calculations after a recursive call.

In [[Scheme]], tail recursion is considered [[iteration]]. Scheme also supports tail call optimization, which will get rid of the frames that are no longer necessary, making the procedure more space efficient.

=== Example ===
The following factorial function is not tail recursive because the result from the recursive call still needs to be multiplied by &lt;code&gt;n&lt;/code&gt;:
&lt;syntaxhighlight lang=&quot;scheme&quot;&gt;
(define (fact n)
    (if (= n 0)
        1
        (* n (fact (- n 1)))))
&lt;/syntaxhighlight&gt;

&lt;code&gt;(fact 2)&lt;/code&gt; would execute as follows:
&lt;syntaxhighlight lang=&quot;scheme&quot;&gt;
(fact 2)
(* 2 (fact 1))
(* 2 (* 1 (fact 0)))
(* 2 (* 1 1))
(* 2 1)
2
&lt;/syntaxhighlight&gt;

To make &lt;code&gt;fact&lt;/code&gt; tail recursive, we use a helper function that has an extra parameter that keeps track of the running product:
&lt;syntaxhighlight lang=&quot;scheme&quot;&gt;
(define (fact n)
    (define (fact-tail n curr-product)
        (if (= n 0)
            curr-product
            (fact-tail (- n 1) (* curr-product n))))
    (fact-tail n 1))
&lt;/syntaxhighlight&gt;
&lt;code&gt;(fact 2)&lt;/code&gt; would execute as follows:
&lt;syntaxhighlight lang=&quot;scheme&quot;&gt;
(fact 2)
(fact-tail 2 1)
(fact-tail 1 2)
(fact-tail 0 2)
2
&lt;/syntaxhighlight&gt;

==See also==
* [[Iteration vs. recursion]]</rev>
        </revisions>
      </page>
      <page pageid="194" ns="0" title="Reduce">
        <revisions>
          <rev contentformat="text/x-wiki" contentmodel="wikitext" xml:space="preserve">{{DISPLAYTITLE:reduce}}
{{C-class}}
'''reduce''' is a [[higher-order function]] that is either built-in in Python 2 or can be [[import]]ed from &lt;code&gt;functools&lt;/code&gt; in Python 3.

Given a ''two-argument'' [[function]], an iterable, and optionally an initalizer, &lt;code&gt;reduce&lt;/code&gt; applies the function to each item pair in the sequence cumulatively and returns a single value.  More precisely, &lt;code&gt;reduce&lt;/code&gt; will take the first two elements of the iterable, apply the function to them, and reach a result. It will then apply the function to this result and the third element, apply the function to the result of that and the fourth element, and so on, until it reaches the end of the iterable. The return value will be the final result.

==Form==
The most general form of the &lt;code&gt;reduce&lt;/code&gt; function is:
&lt;syntaxhighlight lang=&quot;python&quot;&gt;
reduce(func, iter)
&lt;/syntaxhighlight&gt;
where &lt;code&gt;func&lt;/code&gt; is the 2-argument function and &lt;code&gt;iter&lt;/code&gt; is the iterable being processed.

==Examples==
===Sum===
We can use &lt;code&gt;reduce&lt;/code&gt; to sum all elements of a list. We define the following:
&lt;syntaxhighlight lang=&quot;python&quot;&gt;
def add(x, y):
   return x + y
lst = [1, 2, 3, 4, 5]
&lt;/syntaxhighlight&gt;

Applying &lt;code&gt;reduce&lt;/code&gt;:
&lt;syntaxhighlight lang=&quot;python&quot;&gt;
&gt;&gt;&gt; reduce(add, lst)
15
&lt;/syntaxhighlight&gt;
Behind the scenes, &lt;code&gt;reduce&lt;/code&gt; is actually computing &lt;code&gt;add(add(add(add(1, 2), 3), 4), 5)&lt;/code&gt; or &lt;code&gt;((((1 + 2) + 3) + 4) + 5)&lt;/code&gt;.

== Sources ==
* https://docs.python.org/2/library/functions.html#reduce
* https://docs.python.org/3.2/library/functools.html</rev>
        </revisions>
      </page>
    </pages>
  </query>
</api>