Difference between revisions of "Recursion"

From Lazarus wiki
Line 6: Line 6:
  
 
The summation function, designated by an uppercase Sigma in mathematics, is a popular example of recursion:
 
The summation function, designated by an uppercase Sigma in mathematics, is a popular example of recursion:
 
+
<delphi>
<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>
+
function Summation (num : integer) : integer;
<font color="#006699"><strong>begin</strong></font>
+
begin
  <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>
+
  if num = 1 then
    Summation <font color="#000000"><strong>:=</strong></font> <font color="#ff0000">1</font>
+
    Summation := 1
  <font color="#006699"><strong>else</strong></font>
+
  else
    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
+
    Summation := Summation(num-1) + num
<font color="#006699"><strong>end</strong></font><font color="#000000"><strong>;</strong></font>
+
end;
 +
</delphi>
  
 
Suppose you call <tt>Summation</tt> for <tt>3</tt>.
 
Suppose you call <tt>Summation</tt> for <tt>3</tt>.
a := Summation(3);
+
<delphi>
 +
a := Summation(3);
 +
</delphi>
  
 
* <tt>Summation(3)</tt> becomes <tt>Summation(2) + 3</tt>.
 
* <tt>Summation(3)</tt> becomes <tt>Summation(2) + 3</tt>.

Revision as of 17:44, 5 January 2010

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. It keeps calling itself until some limit is reached.

The summation function, designated by an uppercase Sigma in mathematics, is a popular example of recursion: <delphi> function Summation (num : integer) : integer; begin

 if num = 1 then
   Summation := 1
 else
   Summation := Summation(num-1) + num

end; </delphi>

Suppose you call Summation for 3. <delphi> a := Summation(3); </delphi>

  • 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 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 if num = 1. If you don't build in a base condition, the recursion will either not take place at all, or become infinite.

previous contents next