.
 Vyom World.com  . Let's Touch the Sky Together!  
.
. . . . . . .
 Home
VyomWorld.com Home
Free Magazines!
VyomLinks.com Home
JobsAssist.com Home
Vyom Network
Contact Us
 Jobs & Careers
Resume Submitter
Placement Papers
IT Companies Directory
Computer Jobs
Interview Questions
Online Exams
Vyom Career eMag.
 Fun
Screensavers New!
Send FREE SMS!
SMS Jokes
 Source Codes Library
Source Codes Home
ASP Source Codes
C Source Codes
C++ Source Codes
COBOL Source Codes
Java Source Codes
Pascal Source Codes
Submit Source Codes
 GATE
GATE an Overview
GATE Preparation
Study Materal
 GRE
GRE an Overview
GRE Questions
GRE Preparation
GRE Universities
 TOEFL Preparation
TOEFL Resources
 GMAT Preparation
GMAT Resources
 MBA Preparation
MBA Resources
 Networking Concepts
Networking Concepts
 Testing Preparation
Testing Resources
 Webmasters
Free Traffic Builder
Webmaster Articles
Web Hosting
 Tutorials
Hardware Tutorial
1500 Free eBooks New!
 FREE Publications
Vyom Career eMag.
 
.
Get 9,000+ Interview Questions & Answers in an eBook.


  • 9,000+ Interview Questions
  • All Questions Answered
  • 5 FREE Bonuses
  • Free Upgrades

    Get it now!


    Post your Resume to 5800+ Companies

    Reliable Web Hosting

  •  
     
     
    Get 9,000+ Interview Questions with Answers in an eBook


     Home

    Analysis and Design of Algorithms


    Advertisements
    Advertisements

    2.4 Recursion

    Recursion may have the following definitions:

    -The nested repetition of identical algorithm is recursion.

    -It is a technique of defining an object/process by itself.

    -Recursion is a process by which a function calls itself repeatedly until some specified condition has been satisfied.





    2.4.1 When to use recursion

    Recursion can be used for repetitive computations in which each action is stated in terms of previous result. There are two conditions that must be satisfied by any recursive procedure.

      1. Each time a function calls itself it should get nearer to the solution.
      2. There must be a decision criterion for stopping the process.

    In making the decision about whether to write an algorithm in recursive or non-recursive form, it is always advisable to consider a tree structure for the problem. If the structure is simple then use non-recursive form. If the tree appears quite bushy, with little duplication of tasks, then recursion is suitable.

    The recursion algorithm for finding the factorial of a number is given below,

    Algorithm : factorial-recursion

    Input : n, the number whose factorial is to be found.

    Output : f, the factorial of n

    Method : if(n=0)

    f=1

    else

    f=factorial(n-1) * n

    if end

    algorithm ends.

    The general procedure for any recursive algorithm is as follows,

    1. Save the parameters, local variables and return addresses.
    2. If the termination criterion is reached perform final computation and goto step 3 otherwise perform final computations and goto step 1
    3. Restore the most recently saved parameters, local variable and return address and goto the latest return address.

    2.4.2 Iteration v/s Recursion

    Demerits of recursive algorithms

    1. Many programming languages do not support recursion, hence recursive mathematical function is implemented using iterative methods.
    2. Even though mathematical functions can be easily implemented using recursion it is always at the cost of execution time and memory space. For example, the recursion tree for generating 6 numbers in a fibonacci series generation is given in fig 2.5. A fibonacci series is of the form 0,1,1,2,3,5,8,13,…etc, where the third number is the sum of preceding two numbers and so on. It can be noticed from the fig 2.5 that, f(n-2) is computed twice, f(n-3) is computed thrice, f(n-4) is computed 5 times.
    3. A recursive procedure can be called from within or outside itself and to ensure its proper functioning it has to save in some order the return addresses so that, a return to the proper location will result when the return to a calling statement is made.
    4. The recursive programs needs considerably more storage and will take more time.

    Demerits of iterative methods

    1. Mathematical functions such as factorial and fibonacci series generation can be easily implemented using recursion than iteration.
    2. In iterative techniques looping of statement is very much necessary.

    Recursion is a top down approach to problem solving. It divides the problem into pieces or selects out one key step, postponing the rest.

    Iteration is more of a bottom up approach. It begins with what is known and from this constructs the solution step by step. The iterative function obviously uses time that is O(n) where as recursive function has an exponential time complexity.

    It is always true that recursion can be replaced by iteration and stacks. It is also true that stack can be replaced by a recursive program with no stack.

    2.5 Hashing

    Hashing is a practical technique of maintaining a symbol table. A symbol table is a data structure which allows to easily determine whether an arbitrary element is present or not.

    Consider a sequential memory shown in fig 2.6. In hashing technique the address X of a variable x is obtained by computing an arithmetic function (hashing function) f(x). Thus f(x) points to the address where x should be placed in the table. This address is known as the hash address.

    The memory used to store the variable using hashing technique is assumed to be sequential. The memory is known as hash table. The hash table is partitioned into several storing spaces called buckets and each bucket is divided into slots (fig 2.6).

    If there are b buckets in the table, each bucket is capable of holding s variables, where each variable occupies one slot. The function f(x) maps the possible variable onto the integers 0 through b-1. The size of the space from where the variables are drawn is called the identifier space. Let T be the identifier space, n be the number of variables/identifiers in the hash table. Then, the ratio n/T is called the identifier density and a = n/sb is the loading density or loading factor.

    If f(x1)=f(x2), where x1and x2 are any two variables, then x1and x2 are called synonyms. Synonyms are mapped onto the same bucket. If a new identifier is hashed into a already complete bucket, collision occurs.

    A hashing table with single slot is as given below. Let there be 26 buckets with single slot. The identifier to be stored are GA, D, A, G, L, A2, A1, A3, A4, Z, ZA, E. Let f(x) be the function which maps on to a address equal to the position of the first character of the identifier in the set of English alphabet. The hashing table generated is as shown in fig 2.7.

    Time taken to retrieve the identifiers is as follows,

    Search element (x) Search time (t)
    GA 1
    D 1
    A 1
    G 2
    L 1
    A2 2
    A1 3
    A3 5
    A4 6
    Z 1
    ZA 10
    E 6
      ∑t =39

    Average retrieval time =(∑t)/n.

    The average retrieval time entirely depends on the hashing function.

    Exercise 2:

      1. What are the serious short comings of the binary search method and sequential search method.
      2. Know more searching techniques involving hashing functions
      3. Implement the algorithms for searching and calculate the complexities
      4. Write an algorithm for the above method of selection sort and implement the same.
      5. Write the algorithm for merge sort method
      6. Take 5 data set of length 10 and hand simulate for each method given above.
      7. Try to know more sorting techniques and make a comparative study of them.
      8. Write an iterative algorithm to find the factorial of a number
      9. Write a recursive and iterative program for reversing a number
      10. Write recursive and iterative program to find maximum and minimum in a list of numbers.
      11. Write an algorithm to implement the hashing technique and implement the same
      12. Hand simulate all algorithms for a 5 datasets.

    Study Notes Home | Next Section>>




     

    Discussion Center

    Discuss

    Query

    Feedback/ Suggestion

    Yahoo Groups

    Sirfdosti Groups

    Contact Us


    .

    Recently Updated: New Placement Papers added.
    Vyom Network : Web Hosting | Dedicated Server | Free SMS, GRE, GMAT, MBA | Online Exams | Freshers Jobs | Software Downloads | Programming & Source Codes | GRE Preparation | Jobs, Discussions | Software Listing | Free eBooks | Free eBooks | Free Business Info | Interview Questions | Free Tutorials | International Business Information | IAS Preparation | Jokes, Songs, Fun | Free Classifieds | Free Recipes | FAQs | Free Downloads | Bangalore Info | Tech Solutions | Project Outsourcing, Web Hosting | GATE Preparation | MBA Preparation | SAP Info | Excellent Mobiles | Software Testing | Interview Questions | Freshers Jobs | Server Insiders | File Extension Directory

    Copyright ©2003-2017 Vyom Technosoft Pvt. Ltd., All Rights Reserved. Read our Privacy Policy