Difference between revisions of "Basic Pascal Tutorial/Chapter 4/Recursion"

From Free Pascal wiki
Jump to navigationJump to search
m (Kai Burghardt moved page Recursion to Basic Pascal Tutorial/Chapter 4/Recursion: tidy up main name space: create subpage hierarchy for basic Pascal tutorial [cf. [[Special: PermaLink/149778#Cluttering of...)
m (bypass language bar/categorization template redirect [cf. discussion])
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
{{Recursion}}
+
{{Basic Pascal Tutorial/Chapter 4/Recursion}}
{{TYNavigator|Scope|Forward_Referencing}}
+
{{TYNavigator|Chapter 4/Scope|Chapter 4/Forward Referencing}}
  
 
4E - Recursion (author: Tao Yue, state: unchanged)
 
4E - Recursion (author: Tao Yue, state: unchanged)
Line 36: Line 36:
 
In the example above, the base condition was <tt>if num = 1</tt>.  
 
In the example above, the base condition was <tt>if num = 1</tt>.  
  
{{TYNavigator|Scope|Forward_Referencing}}
+
{{TYNavigator|Chapter 4/Scope|Chapter 4/Forward Referencing}}

Latest revision as of 15:20, 20 August 2022

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

 ◄   ▲   ►