RECURSION
We have seen that repetition can be achieved by writing
loops, such as for loops
and while loops. Another way to achieve repetition is
through recursion, which
occurs when a function refers to itself in its own definition
A function is said to be recursive if the function definition
refers to it self. For the definition of function not to be
circular, it must have the following two properties
a) There must be certain argument called base values
which are used to terminate the execution of the
function. At these base values the function does not refer
to itself
b) Each time the function does refer to itself the argument
of the function must be closer to a base value
FOR EXAMPLE
A function ‘f’ which is valid for positive
integer that satisfies
F(0)=0
F(x)=2f(x-1)+x2
This give
F(1),F(2)=6,F(3)=21 and so on
‘recursive function’ is called from the ‘main program’.
Therefor the recursive algorithm should be placed as
sub-algorithm or subroutine in the program. A sub-
algorithm is an algorithm that is called from the main
algorithm
RECURSIVE FUNCTION
Many mathematical functions can be define
recursively .some of them are listed below:
Factorial
Fibonacci
Binary search
FACTORIAL
one of the simplest example of a recursive
definition is that of the factorial function:
Factorial(n)=if (n=0)then 1
• Else n*factorial(n-1)
A natural way to calculate factorial is to write a
recursive function which matches these
definition:
Function fact(int n)
{
If(n==0)
Return 1;
Else
Return n*fact(n-1);
}
Note that this function calls itself to evaluate
the next value. Eventually it will reach the
termination condition .however , before it
reaches the termination condition it would have
pushed ‘n’ stack frames onto the program’s run-
time stack
The termination condition is obviously extremely
important when dealing with recursive function .
If it is omitted then the function will continue to
call itself until the program runs out of stack
space usually with moderately unpleasant
result!
If unable to include a correct termination
condition in a recursive function will lead to a
disaster
ALGORITHM: FACTORIAL(NUM)
This algorithm is used for calculating factorial of
a given number . In this algorithm num is used
ton store the given number.
STEP 1: [check for base case]
If num==0 then
Return 1
STEP 2: [otherwise recursive call]
Return num * factorial(num-1)
LINEAR RECURSION
The simplest form of recursion is linear
recursion, where a function is defined
so that it makes at most one recursive call each
time it is invoked. This type of
recursion is useful when we view an algorithmic
problem in terms of a first or last
element plus a remaining set that has the same
structure as the original set.
SUMMING THE ELEMENTS OF AN ARRAY
RECURSIVELY
Suppose, for example, we are given an array, A,
of n integers that we want to sum
together. We can solve this summation problem
using linear recursion by observing
that the sum of all n integers in A is equal to
A[0], if n=1, or the sum of the first n− 1 integers
in A plus the last element in A. In particular, we
can solve this summation
problem using the recursive algorithm described
following:
Algorithm Linear Sum(A,n):
Input: A integer array A and an integer n≥1, such that A has
at least n elements
Output: The sum of the first n integers in A
if n = 1 then
return A[0]
else
return Linear Sum(A,n−1)+A[n−1]
This example also illustrates an important property
that a recursive function
should always possess—the function terminates. We ensure
this by writing a non recursive
statement for the case n=1. In addition, we always perform
the recursive
call on a smaller value of the parameter (n−1) than that
which we are given (n), so
that, at some point (at the “bottom” of the recursion), we will
perform the non recursive
part of the computation (returning A[0]).
TAIL RECURSION
Using recursion can often be a useful tool for
designing algorithms that have elegant,
short definitions. But this usefulness does come
at a modest cost. When we
use a recursive algorithm to solve a problem, we
have to use some of the memory
locations in our computer to keep track of the
state of each active recursive call.
When computer memory is at a premium, then it
is useful in some cases to be able
to derive nonrecursive algorithms from recursive
ones.
BINARY RECURSION
When an algorithm makes two recursive calls, we
say that it uses binary recursion.
These calls can, for example, be used to solve two
similar halves of some problem,
as we did in Section 3.5 for drawing an English
ruler. As another application of
binary recursion, let us revisit the problem of
summing the n elements of an integer
array A. In this case, we can sum the elements in
A by: (i) recursively summing the
elements in the first half of A; (ii) recursively
summing the elements in the second
half of A; and (iii) adding these two values together. We give
the details in the
algorithm following, which we initially call as Binary
Sum(A,0,n).
Algorithm Binary Sum(A, i,n):
Input: An array A and integers i and n
Output: The sum of the n integers in A starting at index i
if n = 1 then
return A[i]
return Binary Sum(A, i,⌈n/2⌉) + Binary Sum(A, i+⌈n/2⌉,⌊n/2⌋)
MULTIPLE RECURSION
Generalizing from binary recursion, we use
multiple recursion when a function
may make multiple recursive calls, with that
number potentially being more than
two. One of the most common applications of this
type of recursion is used when
we want to enumerate various configurations in
order to solve a combinatorial puzzle.
For example, the following are all instances of
summation puzzles.
pot + pan = bib
dog + cat = pig
boy+ girl = baby
To solve such a puzzle, we need to assign a unique
digit (that is, 0,1, . . . ,9) to each
letter in the equation, in order to make the equation
true. Typically, we solve such
a puzzle by using our human observations of the
particular puzzle we are trying
to solve to eliminate configurations (that is, possible
partial assignments of digits
to letters) until we can work though the feasible
configurations left, testing for the
correctness of each one
