Recursion: Difference between revisions

Revision as of 19:48, 28 May 2002

Revision as of 16:25, 16 June 2002

Line 7:

:0! = 1

:''n''! = ''n'' *· (''n''-1)!   for any [[natural number]] ''n'' > 0

Therefore, givenGiven this definition, we work out 3! as follows:

3! = 3 *· (3-1)!

= 3 *· 2!

= 3 *· 2 *· (2-1)!

= 3 *· 2 *· 1!

= 3 *· 2 *· 1 *· (1 - 1)!

= 3 *· 2 *· 1 *· 1

= 6

Line 23:

In [[set theory]] there is a theorem guaranteeing that such functions exist.

'''The recursion theorem.''' Given a set ''X'', an element ''a'' of ''X'' and a function ''f'':''X''->''X'', then there is a unique function ''F'':'''N'''->''X'' such that

:''F''(0) = ''a'', and

:''F''(''n''+1) = ''f''(''F''(''n''))   for any natural number ''n'' > 0.

''[A proof of the recursion theorem from set theory is needed]''

Line 41:

:if a proposition can be obtained from true propositions by means of inference rules, it is true.

''[It needs to be pointed out that determining whether a certain object is in a recursively defigneddefined set is not an algorithmic task]''

Here is another, perhaps simpler way to understand recursive processes: