Scribd
Upload
55 views9 pages

Recursive Definition

Recursive definitions involve defining a concept in terms of smaller instances of itself using a base case and recursive step. This document provides examples of recursively defining functions, sets, sums, unions, and intersections. Specifically, it gives a recursive definition of a function f(n) where f(0)=3 and f(n+1)=2f(n)+3. It also recursively defines the set of all strings over an alphabet using the base case of the empty string and recursively adding letters.

Uploaded by

Eisha
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
55 views9 pages

Recursive Definition

Recursive definitions involve defining a concept in terms of smaller instances of itself using a base case and recursive step. This document provides examples of recursively defining functions, sets, sums, unions, and intersections. Specifically, it gives a recursive definition of a function f(n) where f(0)=3 and f(n+1)=2f(n)+3. It also recursively defines the set of all strings over an alphabet using the base case of the empty string and recursively adding letters.

Uploaded by

Eisha
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 9

RECURSIVE DEFINITION

PRESENTATION BY
=>ESHA SAJID
=> ALI ASHGAR
=> DANYAL ASIF
RECURSION
1. The part of definition which can be expressed in terms of
smaller versions of itself.

Recursively Defined Functions


A function is said to be recursively defined if it contains these steps:
Þ Basic Step: Value of the function at initial points must be
defined . (i.e f(0) should be defined)
Þ Recursive Step: Should give a rule to find the values of function.
like f(1) , f(2) , f(3) etc
FOR EXAMPLE :
=> Suppose that f is defined recursively by
f(0) =3 (base)
f(n+1) =2f(n)+3 (recursion)
Find f(1) , f(2) and f(3);
Solution:
Here f(0)=3 so;
[Putting n=0,1,2 in recursion]
F(1) = 2f(0)+3 = 2(3)+3 =9
F(2) = 2f(1)+3 = 2(9)+3 =21
F(3) = 2f(2)+3 = 2(21)+3 =45
RECURSIVE DEFINITION OF SETS
Consider a finite alphabet ∑={a,b}. The set of all finite strings over ∑, denoted by ∑*
Is defined recursively as follows:

(I) BASE: € is in ∑
Þwhere € is the null string.
ÞRECURSION:
(II) if S belongs to ∑* then:
Þ(a) sa belongs to ∑*
Þ(b) sb belongs to ∑*
(III) Where sa and sb are concatenation of s with a and b respectively.
FOR EXAMPLE
(1) Give derivations showing that abb is in ∑*.

SOLUTION:
Þ € belongs to ∑* by I.
Þ a= €a belongs to ∑* by 1 and II(a)
Þ ab belongs to ∑* by 3 and II(b)
Þ abb belongs to ∑* by 3 and II(b)
RECURSIVE DEFINATION OF SUM
Given numbers a1,a2,……,an , where n is a positive integer , the
summation from i=1 to n of ai, denoted as

Is defined as follows
SETSRECURSIVE DEFINATION
OF UNION OF SETS
Given sets A1,A2,…..,An, where n is a positive number. The union of Ai from i=1 to n ,
denoted

is defined by:
BASE:
RECURSION: ()U An
RECURSIVE DEFINTAION OF
INTERSECTION OF SETS
Given sets A1,A2,…….,An where n is a positive integer, the intersection of Ai
from i=0 to n, denoted as :
is denoted as
BASE:

RECURSION: =()
THANK YOU
THE END

You might also like