Recursion

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

Recursion

Uploaded by

Copyright:

Available Formats

Recursion

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Recursion

Uploaded by

Copyright:

Available Formats

RECURSION

 We have seen that repetition can be achieved by writing

 A natural way to calculate factorial is to write a

 STEP 2: [otherwise recursive call]

 Input: An array A and integers i and n

 Output: The sum of the n integers in A starting at index i

 return Binary Sum(A, i,⌈n/2⌉) + Binary Sum(A, i+⌈n/2⌉,⌊n/2⌋)

You might also like