Difference between revisions of "Recursion"

From Lazarus wiki
m (Fixed syntax highlighting)
 
(8 intermediate revisions by 6 users not shown)
Line 1: Line 1:
 +
{{Recursion}}
 +
{{TYNavigator|Scope|Forward_Referencing}}
 +
 
4E - Recursion (author: Tao Yue, state: unchanged)
 
4E - Recursion (author: Tao Yue, state: unchanged)
  
''Recursion'' is a difficult topic to grasp. However, it's very easy to apply once you understand it. The programming assignment for this chapter will involve recursion.
+
'''Recursion''' means allowing a function or procedure to call itself until some limit is reached.
  
Recursion means allowing a function or procedure to call itself. It keeps calling 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, is a popular example of recursion:
+
<syntaxhighlight lang=pascal>
 +
function Summation (num : integer) : integer;
 +
begin
 +
  if num = 1
 +
  then Summation := 1
 +
  else Summation := Summation(num-1) + num
 +
end;
 +
</syntaxhighlight>
  
<font color="#006699"><strong>function</strong></font> Summation <font color="#000000"><strong>(</strong></font>num <font color="#000000"><strong>:</strong></font> <font color="#0099ff"><strong>integer</strong></font><font color="#000000"><strong>)</strong></font> <font color="#000000"><strong>:</strong></font> <font color="#0099ff"><strong>integer</strong></font><font color="#000000"><strong>;</strong></font>
+
Suppose you call <tt>Summation</tt> for <tt>3</tt>.
<font color="#006699"><strong>begin</strong></font>
 
  <font color="#006699"><strong>if</strong></font> num <font color="#000000"><strong>=</strong></font> <font color="#ff0000">1</font> <font color="#006699"><strong>then</strong></font>
 
    Summation <font color="#000000"><strong>:=</strong></font> <font color="#ff0000">1</font>
 
  <font color="#006699"><strong>else</strong></font>
 
    Summation <font color="#000000"><strong>:=</strong></font> Summation<font color="#000000"><strong>(</strong></font>num<font color="#000000"><strong>-</strong></font><font color="#ff0000">1</font><font color="#000000"><strong>)</strong></font> <font color="#000000"><strong>+</strong></font> num
 
<font color="#006699"><strong>end</strong></font><font color="#000000"><strong>;</strong></font>
 
  
Suppose you call <tt>Summation</tt> for <tt>3</tt>.
+
<syntaxhighlight lang=pascal>
a := Summation(3);
+
a := Summation(3);
 +
</syntaxhighlight>
  
 
* <tt>Summation(3)</tt> becomes <tt>Summation(2) + 3</tt>.
 
* <tt>Summation(3)</tt> becomes <tt>Summation(2) + 3</tt>.
Line 27: Line 32:
 
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 some sort of test so stop the recursion. Under one condition, called the base condition, the recursion should stop. Under all other conditions, the recursion should go deeper. In the example above, the base condition was <tt>if num = 1</tt>. If you don't build in a base condition, the recursion will either not take place at all, or become infinite.
+
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"
+
{{TYNavigator|Scope|Forward_Referencing}}
|[[Scope|previous]] 
 
|[[op_contents|contents]]
 
|[[Forward_Referencing|next]]
 
|}
 

Latest revision as of 08:29, 25 February 2020

български (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.

 ◄   ▲   ►