Recursive Definitions

A definition in which the item being defined appears as part of the definition is called a recursive definition. At first this seems like nonsense -- how can we define something in terms of itself? This works because there are two parts to a recursive definition:

1. A basis, where some simple cases of the item being defined are explicitly given
2. An inductive or recursive step, where new cases of the item beding defined are given in terms of previous cases.

Part 1 gives us a place to start by providing some simple, concrete cases; part 2 allows us to construct new cases from these simple ones and then to construct still other cases from these new ones, and so forth.

Recursion is an important idea that can be used to define sequences of objects, more general collections of objects, and operations on objects. Even algorithms can be recursive.

From a practitioner's perspective, recursive procedures are simple to write, but they are extremely memory-intensive, and it can be difficult to predict how much memory will be required.

Recursively Defined Sequences

A sequence S (an infinite sequence) is a list of objects that are enumerated in some order; there is a first such object, then a second, and so on. S(k) denotes the \(k_{th}\) object in the sequence. The list goes on forever, so a sequence therefore consists of

S(1), S(2), ..., S(k), ...
Subscript notation is often used to denote the elements in a sequence, as in
\( S_1, S_2, ..., S_k, ... \)
The letter S is just a "dummy variable", so a sequence could also be denoted by
\( a_1, a_2, ..., a_k, ...\) or \(w_1, w_2,...,w_k,...\) and so forth.

Example

• Example 1: 

The sequence S is defined recursively by

     1. S(1) = 2
     2. S(n) = 2S(n-1)  for n ≥ 2

By statement 1, S(1), the first object in S, is 2.
By statement 2, S(2), the second object in S is S(2) = 2S(1) = 2*2 = 4.
By statement 2 again, S(3) = 2S(2) = 2*4 = 8.
Continuing in this fashion, we can see that S is the sequence
2, 4, 8, 16, 32, ...
A rule like that of statement 2 in Example 1, which defines a sequence value in terms of one or more earlier values, is called a recurrence relation.

Suppose we want to write a computer program to evaluate S(n) for some positive integer n. We can use two approaches: recursive algorithm or iterative algorithm.

Recursive Defined Algorithm Following is a version of the recursive algorithm, written as a pseudocode function.

         S(positive integer n)
	     if n = 1 then
                return 2
             else
                return 2*S(n-1)
      	     end if
         end function S

Figure1: Recursive Function Call in Stack

Here in recursive algorithm, if \(n\) is 1 trillion there will be 1 trillion functions on the stack -- potential stack overflow. Can we be more dfficient? We can use loops.

Iterative Algorithm Following is a version of the iterative algorithm, written as a pseudocode function.

         S(positive integer n)
		 if n = 1 then
           	    return 2
         	 else
                    i = 2
                    CurerntValue = 2
                    while i <= n do
                        CurrentValue = 2*CurrentValue
                        i = i + 1
                    end while
	            return CurrentValue
                 end if
         end function S

Example

• Example 2: 

The Fibonacci sequence of numbers, introduced in the thirteenth century by
an Italian merchant and mathematician, is defiend recursively by:

     1. F(1) = 1
     2. F(2) = 1
     3. F(n) = F(n-2) + F(n-1) for n > 2

By statement 1, F(1), the first object in F, is 1.
By statement 2, F(2), the second object in F, is 1.
By statement 3, F(3) = F(1) + F(2) = 1 + 1 = 2.
By statement 3 again, F(4) = F(2) + F(3) = 1 + 2 = 3.
Continuing in this fashion, we can see that F is the sequence
1, 1, 2, 3, 5, 8, 13, ...

Suppose we want to write a computer program to evaluate F(n) for some positive integer n. We can use two approaches: recursive algorithm or iterative algorithm.

Recursive Defined Algorithm Following is a version of the recursive algorithm, written as a pseudocode function.

         F(positive integer n)
	     if n = 1 or n = 2 then
                return 1
             else
                return F(n-2) + F(n-1)
      	     end if
         end function F

Here in recursive algorithm, if \(n\) is 1 trillion there will be 1 trillion functions on the stack -- potential stack overflow. Can we be more dfficient? We can use loops.

Iterative Algorithm Following is a version of the iterative algorithm, written as a pseudocode function.

         F(positive integer n)
		 if n = 1 or n = 2 then
           	    return 1
         	 else
                    i = 3
                    F1 = 1
		    F2 = 1
                    while i <= n do
                        Fn = F1 + F2;
                        F1 = F2;
                        F2 = Fn;
                        i = i + 1;
                    end while
	            return Fn
                 end if
         end function F

Practice

(1) Please write a python program to evaluate T(n) for some positive integer n. Please write both recursive algorithm and iterative algorithm.

T(1) = 1 for n = 1
T(n) = T(n-1) + 3 for n > 1

(2) Please write a python program to evaluate S(n) for some positive integer n. Please write both recursive algorithm and iterative algorithm.

S(1) = 2 for n = 1
S(n) = S(n-1)² for n > 1

Reference

saylor academy