# Difference between revisions of "Recursion"

m |
|||

Line 3: | Line 3: | ||

4E - Recursion (author: Tao Yue, state: unchanged) | 4E - Recursion (author: Tao Yue, state: unchanged) | ||

− | ''Recursion'' | + | '''Recursion''' means allowing a function or procedure to call itself until some limit is reached. |

− | + | The summation function, designated by an uppercase letter ''sigma'' (Σ) in mathematics, can be written recursively: | |

− | |||

− | The summation function, designated by an uppercase Sigma in mathematics, | ||

<syntaxhighlight> | <syntaxhighlight> | ||

function Summation (num : integer) : integer; | function Summation (num : integer) : integer; | ||

begin | begin | ||

− | if num = 1 then | + | if num = 1 |

− | + | then Summation := 1 | |

− | else | + | else Summation := Summation(num-1) + num |

− | |||

end; | end; | ||

</syntaxhighlight> | </syntaxhighlight> | ||

Line 32: | Line 29: | ||

Recursion works backward until a given point is reached at which an answer is defined, and then works forward with that definition, solving the other definitions which rely upon that one. | Recursion works backward until a given point is reached at which an answer is defined, and then works forward with that definition, solving the other definitions which rely upon that one. | ||

− | All recursive procedures/functions should have | + | All recursive procedures/functions should have a test to stop the recursion, the base condition. Under all other conditions, the recursion should go deeper. If there is no base condition, the recursion will either not take place at all, or become infinite. |

+ | |||

+ | In the example above, the base condition was <tt>if num = 1</tt>. | ||

{|style=color-backgroud="white" cellspacing="20" | {|style=color-backgroud="white" cellspacing="20" |

## Revision as of 15:31, 21 February 2015

│
**български (bg)** │
**English (en)** │
**français (fr)** │
**日本語 (ja)** │
**中文（中国大陆） (zh_CN)** │

4E - Recursion (author: Tao Yue, state: unchanged)

**Recursion** means allowing a function or procedure to call itself until some limit is reached.

The summation function, designated by an uppercase letter *sigma* (Σ) in mathematics, can be written recursively:

```
function Summation (num : integer) : integer;
begin
if num = 1
then Summation := 1
else Summation := Summation(num-1) + num
end;
```

Suppose you call `Summation` for `3`.

`a := Summation(3);`

`Summation(3)`becomes`Summation(2) + 3`.`Summation(2)`becomes`Summation(1) + 2`.- At
`1`, the recursion stops and becomes`1`. `Summation(2)`becomes`1 + 2 = 3`.`Summation(3)`becomes`3 + 3 = 6`.`a`becomes`6`.

Recursion works backward until a given point is reached at which an answer is defined, and then works forward with that definition, solving the other definitions which rely upon that one.

All recursive procedures/functions should have a test to stop the recursion, the base condition. Under all other conditions, the recursion should go deeper. If there is no base condition, the recursion will either not take place at all, or become infinite.

In the example above, the base condition was `if num = 1`.

previous | contents | next |