Difference between revisions of "Recursion"
Jhernandez3 (talk | contribs) m |
Jhernandez3 (talk | contribs) m |
||
Line 2: | Line 2: | ||
<breadcrumbs> Analytica User Guide > {{PAGENAME}}</breadcrumbs><br /> | <breadcrumbs> Analytica User Guide > {{PAGENAME}}</breadcrumbs><br /> | ||
− | A recursive function is a function that calls itself within its definition. This is often a convenient way to define a function, and sometimes the only way. As an example, consider this definition of factorial: | + | A '''''recursive''''' function is a function that calls itself within its definition. This is often a convenient way to define a function, and sometimes the only way. As an example, consider this definition of factorial: |
− | Function Factorial2(n: Positive Atom) | + | <code>Function Factorial2(n: Positive Atom)</code> |
− | |||
− | If its parameter, n, is greater than 1, Factorial2 calls itself | + | <code>Definition: IF n > 1 THEN N*Factorial2(n-1) ELSE 1</code> |
+ | |||
+ | If its parameter, <code>n</code>, is greater than 1, <code>Factorial2</code> calls itself with the actual parameter value <code>n-1</code>. Otherwise, it simply returns 1. Like any normal recursive function, it has a termination condition under which the recursion stops — when <code>n <= 1</code>. | ||
<Tip Title="Tip"> The built-in function Factorial does the same, and is fully abstractable, to boot. We define Factorial2 here as a simple example to demonstrate key ideas.</Tip > | <Tip Title="Tip"> The built-in function Factorial does the same, and is fully abstractable, to boot. We define Factorial2 here as a simple example to demonstrate key ideas.</Tip > | ||
− | Normally, if you try to use a function in its own definition, it complains about a cyclic dependency loop. To enable recursion, you must display and set the Recursive attribute: | + | Normally, if you try to use a function in its own definition, it complains about a cyclic dependency loop. To enable recursion, you must display and set the '''Recursive''' attribute: |
− | # Select | + | # Select '''Attributes''' from the '''Object''' menu. |
::[[File:procedure_attributes.png|300px]] | ::[[File:procedure_attributes.png|300px]] | ||
− | <ol start="2"><li>Select Functions from the Class menu | + | <ol start="2"><li>Select '''Functions''' from the '''Class''' menu.</li></ol> |
− | <ol start="3"><li>Scroll down the list of attributes and click Recursive twice, so that it shows √, meaning that the recursive attribute is displayed for each function in its Object window and the Attribute panel.</li></ol> | + | <ol start="3"><li>Scroll down the list of attributes and click '''Recursive''' twice, so that it shows √, meaning that the recursive attribute is displayed for each function in its '''Object''' window and the '''Attribute''' panel.</li></ol> |
− | <ol start="4"><li>Check OK to close Attributes dialog.</li></ol><br /> | + | <ol start="4"><li>Check '''OK''' to close '''Attributes''' dialog.</li></ol><br /> |
For each function for which you wish to enable recursion:<br /> | For each function for which you wish to enable recursion:<br /> | ||
− | <ol start="5"><li>Open the Object Window for the function by double-clicking its node (or | + | <ol start="5"><li>Open the '''Object Window''' for the function by double-clicking its node (or selecting the node and clicking the '''Object''' button).</li></ol> |
− | + | <ol start="6"><li>Type '''<code>1</code>''' into its '''Recursive''' field.</li></ol> | |
− | <ol start="6"><li>Type 1 into its Recursive field.</li></ol> | ||
::[[File:factorial2.png|500px]] | ::[[File:factorial2.png|500px]] | ||
− | As another example, consider this recursive function to compute a list of the prime factors of an integer, x, equal to or greater than y: | + | As another example, consider this recursive function to compute a list of the prime factors of an integer, <code>x</code>, equal to or greater than <code>y</code>: |
+ | |||
+ | <code>Function Prime_factors(x, y: Positive Atom)</code> | ||
+ | |||
+ | <code>Definition:</code> | ||
+ | |||
+ | <code>Var n := Floor(x/y);</code> | ||
+ | |||
+ | <code>IF n<y THEN [x]</code> | ||
+ | |||
+ | <code>ELSE IF x = n*y THEN Concat([y], Factors(n, y))</code> | ||
+ | |||
+ | <code>ELSE Prime_factors(x, y+1)</code> | ||
− | + | <code>Factors(60, 2) → [2, 2, 3, 5]</code> | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | Factors(60, 2) → [2, 2, 3, 5] | ||
− | In essence, Prime_factors says to compute n as x divided by y, rounded down. If y is greater than n, then x is the last factor, so return x as a list. If x is an exact factor of y, then concatenate x with any factors of n, equal or greater than n. Otherwise, try y+1 as a factor. | + | In essence, <code>Prime_factors</code> says to compute <code>n</code> as <code>x</code> divided by <code>y</code>, rounded down. If <code>y</code> is greater than <code>n</code>, then <code>x</code> is the last factor, so return <code>x</code> as a list. If <code>x</code> is an exact factor of <code>y</code>, then concatenate <code>x</code> with any factors of <code>n</code>, equal or greater than <code>n</code>. Otherwise, try <code>y+1</code> as a factor. |
<Tip Title="Tip">To prevent accidental infinite recursion, it stops and gives a warning if the stack reaches a depth | <Tip Title="Tip">To prevent accidental infinite recursion, it stops and gives a warning if the stack reaches a depth |
Revision as of 15:11, 15 December 2015
A recursive function is a function that calls itself within its definition. This is often a convenient way to define a function, and sometimes the only way. As an example, consider this definition of factorial:
Function Factorial2(n: Positive Atom)
Definition: IF n > 1 THEN N*Factorial2(n-1) ELSE 1
If its parameter, n
, is greater than 1, Factorial2
calls itself with the actual parameter value n-1
. Otherwise, it simply returns 1. Like any normal recursive function, it has a termination condition under which the recursion stops — when n <= 1
.
Normally, if you try to use a function in its own definition, it complains about a cyclic dependency loop. To enable recursion, you must display and set the Recursive attribute:
- Select Attributes from the Object menu.
- Select Functions from the Class menu.
- Scroll down the list of attributes and click Recursive twice, so that it shows √, meaning that the recursive attribute is displayed for each function in its Object window and the Attribute panel.
- Check OK to close Attributes dialog.
For each function for which you wish to enable recursion:
- Open the Object Window for the function by double-clicking its node (or selecting the node and clicking the Object button).
- Type
1
into its Recursive field.
As another example, consider this recursive function to compute a list of the prime factors of an integer, x
, equal to or greater than y
:
Function Prime_factors(x, y: Positive Atom)
Definition:
Var n := Floor(x/y);
IF n<y THEN [x]
ELSE IF x = n*y THEN Concat([y], Factors(n, y))
ELSE Prime_factors(x, y+1)
Factors(60, 2) → [2, 2, 3, 5]
In essence, Prime_factors
says to compute n
as x
divided by y
, rounded down. If y
is greater than n
, then x
is the last factor, so return x
as a list. If x
is an exact factor of y
, then concatenate x
with any factors of n
, equal or greater than n
. Otherwise, try y+1
as a factor.
Enable comment auto-refresher