4. Recursion - Data Structures using C++ by Varsha Patil

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil  Understand the power of recursion & learn its working  Identify the base case and the general case of a recursively defined problem  Compare iterative and recursive solutions  Learn to write, implement, test, and debug recursive functions 2

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 3  Function may call itself  Function may call other Function and the other  Function in turn again may call the calling Function  Such Functions are called as recursive Functions.

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil  Adjacent Nodes  Directed and Undirected Graph  Parallel Edges and Multigraph  Weighted Graph  Null Graph and Isolated Vertex 5

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil  Depending on the characterization, the recursive functions are categorized as direct, indirect, linear, tree, and tail recursions 6

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil  Depending on the characterization, the recursive functions are categorized as direct, indirect, linear, tree, and tail recursions  The function calls itself  Function calls the other function which in turn calls the caller function  Function call is part of the same processing instruction which makes a recursive function call 7

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil  A binary-recursive function calls itself twice  Fibonacci numbers computation, quick sort and merge sort are examples of binary recursion 8

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil  The most general form of recursion is n-ary recursion where n is not a constant but some parameter of a function  Functions of this kind are useful in generating combinatorial objects such as permutations 9

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil  Recursion when function calls itself  Recursion is said to be direct when functions calls itself directly and is said to be indirect when it calls other function that in turn calls it  The function factorial we studied is an example of direct recursion 10 Direct Recursion

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil  Function is said to be indirectly recursive if it calls another function which in turn calls it  The algorithm given below is an example of indirect recursion 11 In-Direct Recursion

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil  A recursive function is said to be tail recursive if there are no pending operations to be performed on return from a recursive call  Tail recursion is also used to return the value of the last recursive call as the value of the function  Tail recursion is advantageous as the amount of information which must be stored during computation is independent of the number of recursive calls 12 Tail Recursion

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil  Depending on the way in which recursion grows is classified as linear or tree  A recursive function is said to be linearly recursive when no pending operation involves another recursive call  For example the factorial functions  The simplest form of recursion is linear recursion  It occurs where an action has a simple repetitive structure consisting of some basic step followed by the action again  Factorial function is example of linear recursion 13 Linear Recursion

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil  In recursive function, if there is another recursive call in the set of operations to be completed after the recursion is over, then it is called a tree recursion 14 Tree Recursion

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil  At every recursive call, all reference parameters and local variables are pushed onto the stack along with function value and return address  These data are conceptually placed in a stack frame is pushed onto the system stack  A stack frame contains four different elements:  The reference parameters to be processed by the called function  Local variables in the calling function  The return address  The expression that is to receive the return value, if any 15 Execution of Recursive Calls

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil At the end condition, when no more recursive calls are made, the following steps are performed  If the stack is empty then execute a normal return  Otherwise POP the stack frame, that is, take the values of all parameters which are on the top of the stack and assign these values to the corresponding variables  Use the return address to locate the place where the call was made  Execute all the statements from that place (address) where the call was made  Go to step 1 16

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil  Recursion is most of the times viewed by students as a somewhat mystical technique which only is useful for some very special class of problems, such as computing factorials or Fibonacci series  This is not the fact  Practically any function that is written using iterative code can be converted into recursive code  Of course, this does not guarantee that the resulting program will be easy to understand but often the program results in a compact and readable code 17 Writing Recursive Functions

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil  Recursive functions are often simple and elegant and their correctness can be easily seen  Many mathematical functions are defined recursively and their translation into a programming language is often trivially easy  Recursion is natural in Ada, Algol, C, C++, Haskell, Java, Lisp, ML, Modula, Pascal and a great many other programming languages  Used carelessly, recursion can sometimes result in an inefficient function 18 Recursive Functions (cont..)

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil  Recursive functions are closely related to inductive definitions of functions in mathematics  In order to evaluate whether an algorithm is to be written using recursion, we must first try to deduce an inductive definition of the algorithm  Algorithms that are by nature recursive, like the factorial, Fibonacci or Power can be implemented as either iterative or recursive code  However recursive functions are generally smaller and more efficient than their looping equivalents 19 Recursive Functions (cont..)

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil  Moreover, recursion is also useful when the data structure that the algorithm is to operate on is recursively defined  Examples to such data structures are linked list and Trees  Recursive functions are closely related to inductive definitions of functions in mathematics  One more instance when recursion is valuable is when we use ‘divide and conquer’ and ‘backtracking’ as algorithm design paradigm  Divide and conquer is a technique in which given a function to compute on n inputs the divide and conquer strategy suggests splitting the inputs into k distinct subsets, 1 < k £ n yielding k sub problems 20 Recursive Functions (cont..)

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil  Theses sub-problems must be then solved and should be combined to get a solution as a whole  If the sub-problem is still large, divide and conquer is reapplied  The reapplication is expressed better by the recursive function  Recursion is a technique that allows us to break down a problem into one or more sub problems that are similar in form to the original problem  Examples include Binary Search, Merge sort, and Quick sort 21 Recursive Functions (cont..)

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil  The general approach to writing a recursive functions is to:  Write the function header so that you are sure what the function will do and how it will be called  Identify some unit of measure for the size of the problem the function or procedure will work on  Then pretend that task is to write Function that will work on problems of all sizes 22 Writing Recursive Code(cont..)

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil  Use of recursion often makes everything simpler. It is required to find out what data exactly we are recurring on; what is the essential feature of the problem that should change as function acalls itself  In the Towers of Hanoi solution, one recurs on the largest disk to be moved  That is, one has to write a recursive function that takes as a parameter the disk that is the largest disk in the tower that is to be moved  The function should take three parameters indicating from which peg the tower should be moved (source), to which peg it should go (dest), and the other peg, which we can use temporarily(spare) 23 Writing Recursive Code(cont..)

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 24z Let us consider the initial position of the problem as in fig 1 We can break this into three basic steps Fig 1: Problem of Towers of Hanoi

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 25  Finally, we want disks 4 and smaller moved from peg C (spare) to peg B (dest)  We do this recursively using the same function again  At the end we have disks 5 and smaller all on dest (figure 4.5) Fig 4: Step 3

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil HTower(disk, source, dest, spare) IF disk == 0, THEN move disk from source to dest ELSE HTower(disk - 1, source, spare, dest) // Step 1 move disk from source to dest // Step 2 HTower(disk - 1, spare, dest, source) // Step 3 END IF  26

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil A recursive function must have at least one end condition and one recursive case  The test for the end condition has to execute prior to the recursive call  The problem must be broken down in such a way that the recursive call is closer to the base case than the top level call  This condition is actually not quite strong sufficient.  Moving towards the end condition alone is not sufficient; it must also be true that the base case is reached in a finite number of recursive calls  The recursive call must not skip over the base case.  Verify that the non-recursive code of the function is operating correctly 27

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 28  Recursive functions call themselves within their own definition  Recursive functions must have a non recursive terminating condition or an infinite loop will occur  Recursion though easy to code is often, but not always, memory starving

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 29  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  It is hard to say that the non-recursive version is better than the recursive one or vice versa  But often few languages does not support writing recursive code, say FORTRAN or COBOL  The non-recursive version is more efficient as the overhead of parameter passing in most compilers is heavy

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 30  Many programming languages do not support recursion; hence recursive mathematical function is to be implemented using iterative methods  Even though mathematical functions can be easily implemented using recursion it is always at the cost of additional execution time and memory space  A recursive function 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

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 31  Mathematical functions such as factorial and Fibonacci series generation can be easily implemented using recursion than iteration  In iterative techniques looping of statement is very much necessary and needs complex logic  The iterative code may result into lengthy code

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 32  Wherever a data object/process/relation is defined recursively, it is often easy to describe algorithms recursively  If programming language does not support recursion or one needs no recursive code, then one can always translate a recursive code to a non-recursive one  Once a recursive function is written and is verified for its correctness, one can remove recursion for efficiency

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 33 Following are the major areas in which the process of recursion can be applied  Search techniques  Game playing  Expert Systems  Pattern Recognition and Computer Vision  Robotics  Artificial Intelligence

Oxford University Press © 2012Data Structures Using C++ by Dr Varsha Patil 34  Function may call itself. Function may call other Function and the other Function in turn again may call the calling Function. Such Functions are called as recursive Functions  Any correct iterative code can be converted into equivalent recursive code and vice a versa.  The basic concepts and ideas involved with recursion are simple: a function that has to be solved is treated as a big problem and it solves itself by using itself to solve a slightly smaller problem. The recurrence relation is easily converted to recursive code  Working of recursion is fairly straightforward. However, to better understand the working of recursion, and to be able to use it well one requires practice  The best way to obtain this is to write a lot of recursive functions  Recursion can be used for divide conquer based search and sort algorithms to increase the efficiency of these operations. For most of the problems like Towers of Hanoi; recursion presents an incredibly elegant solution that is easy to code and simple to understand

36 Row-major representation  In row-major representation, the elements of Matrix are stored row-wise, i.e., elements of 1st row, 2nd row, 3rd row, and so on till mth row (0,0) (0,1) (0,2) (0,3) (1,0) (1,1) (1,2) (1,3) (2,0) (2,1) (2,2) (2,3) Row1 Row2 Row3 1 2 3 4 5 6 7 8 9 10 11 12

37 Row major arrangement Row 0 Row 1 Row m-1 Row 0 Row 1 Row m-1 Memory Location

38 The address of the element of the ith row and the jth column for matrix of size m x n can be calculated as: Addr(A[i][j]) = Base Address+ Offset = Base Address + (number of rows placed before ith row * size of row) * (Size of Element) + (number of elements placed before in jth element in ith row)* size of element As row indexing starts from 0, i indicate number of rows before the ith row here and similarly for j. For Element Size = 1 the address is Address of A[i][j]= Base + (i * n ) + j

39 In general, Addr[i][j] = ((i–LB1) * (UB2 – LB2 + 1) * size) + ((j– LB2) * size) where number of rows placed before ith row = (i – LB1) where LB1 is the lower bound of the first dimension. Size of row = (number of elements in row) * (size of element)Memory Locations The number of elements in a row = (UB2 – LB2 + 1) where UB2 and LB2 are upper and lower bounds of the second dimension.

40 Column-major representation  In column-major representation m × n elements of two-dimensional array A are stored as one single row of columns. The elements are stored in the memory as a sequence as first the elements of column 1, then elements of column 2 and so on till elements of column n

41 Column-major arrangement col1 col2 Col n-1 Col 0 Col 1 Col 2 Memory Location …

42 The address of A[i][j] is computed as  Addr(A[i][j]) = Base Address+ Offset= Base Address + (number of columns placed before jth column * size of column) * (Size of Element) + (number of elements placed before in ith element in ith row)* size of element For Element_Size = 1 the address is  Address of A[i][j] for column major arrangement = Base + (j * m ) + I In general, for column-major arrangement; address of the element of the jth row and the jth column therefore is  Addr (A[i][j] = ((j – LB2) * (UB1 – LB1 + 1) * size) + ((i –LB1) * size)

43 Example 2.1: Consider an integer array, int A[3][4] in C++. If the base address is 1050, find the address of the element A[2] [3] with row-major and column-major representation of the array. For C++, lower bound of index is 0 and we have m=3, n=4, and Base= 1050. Let us compute address of element A [2][3] using the address computation formula 1. Row-Major Representation: Address of A [2][3] = Base + (i * n ) + j = 1050 + (2 * 4) + 3 = 1061

44 (0,0) (0,1) (0,2) (0,3) (1,0) (1,1) (1,2) (1,3) (2,0) (2,1) (2,2) (2,3) Row1 Row2 Row3 1 2 3 4 5 6 7 8 9 10 11 12

45 2. Column-Major Representation: Address of A [2][3] = Base + (j * m ) + i = 1050 + (3 * 3) + 2 = 1050 + 11 = 1061  Here the address of the element is same because it is the last member of last row and last column.

46 (0,0) (1,0) (2,0) (0,1) (1,1) (2,1) (0,2) (1,2) (2,2) (0,3) (1,3) (2,3) Col 1 Col 2 Col 3 Col 4 1 2 3 4 5 6 7 8 9 10 11 12

49 Row-Major representation of 2D array

50 Three dimensions row-major arrangement (i*m2*m3) elements A[0][m2][m3] A[1][m2][m3] A[i][m2][m3] A[m1-1][m2]

51  The address of A[i][j][k] is computed as Addr of A[i][j][k] = X + i * m2 * m3 + j * m3 + k By generalizing this we get the address of A[i1][i2][i3] … [ in] in n-dimensional array A[m1][m2][m3]. ….[ mn ] Consider the address of A [0][0][0]…..[0] is X then the address of A [i][0][0]….[0] = X + (i1 * m2 * m3 * - - -- - * mn ) and Address of A [i1][i2] …. [0] = X + (i1 * m2 * m3 * - -- - *mn ) + (i2 * m3 * m4 *--- * mn) Continuing in a similar way, address of A[i1][i2][i3]- - - -[ in] will be Address of A[i1][i2][i3]----[ in] = X + (i1 * m2 * m3 * - - -- - * mn) + (i2 * m3 * m4 *--- - - * mn )+(i3 * m4 * m5--- * mn + (i4 * m5 * m6--- - - * mn +…….+ in =

52 ARRAYS USING TEMPLATE The function is defined in similar way replacing int by T as datatype of member of array In all member functions header, Array is replaced by Array <T> :: now Following statements instantiate the template class Array to int and float respectively. So P is array of ints and Q in array of floats. Array <int> P; Array <float> Q; In similar we can also have array of any user defined data type

53 CONCEPT OF ORDERED LIST Ordered list is the most common and frequently used data object Linear elements of an ordered list are related with each other in a particular order or sequence Following are some examples of the ordered list.  1, 3,5,7,9,11,13,15  January, February, March, April, May, June, July, August, September,  October, November, December  Red, Blue, Green, Black, Yellow

54 There are many basic operations that can be performed on the ordered list as follows:  Finding the length of the list  Traverse the list from left to right or from right to left  Access the ith element in the list  Update (Overwrite) the value of the ith position  Insert an element at the ith location  Delete an element at the ith position

56 Single Variable Polynomial  Representation Using Arrays  Array of Structures  Polynomial Evaluation  Polynomial Addition  Multiplication of Two Polynomials

57  Polynomial as an ADT, the basic operations are as follows: Creation of a polynomial Addition of two polynomials Subtraction of two polynomials Multiplication of two polynomials Polynomial evaluation

60  Structure is better than array for Polynomial: Such representation by an array is both time and space efficient when polynomial is not a sparse one such as polynomial P(x) of degree 3 where P(x)= 3x3+x2–2x+5. But when polynomial is sparse such as in worst case a polynomial as A(x)= x99 + 78 for degree of n =100, then only two locations out of 101 would be used. In such cases it is better to store polynomial as pairs of coefficient and exponent. We may go for two different arrays for each or a structure having two members as two arrays for each of coeff. and Exp or an array of structure that consists of two data members coefficient and exponent.

61 Polynomial by using structure  Let us go for structure having two data members coefficient and exponent and its array.

62 AN ARRAY FOR FREQUENCY COUNT We can use array to store the number of times a particular element occurs in any sequence. Such occurrence of particular element is known as frequency count. void Frequency_Count ( int Freq[10 ], int A [ 100]) { int i; for ( i=0;i<10;i++) Freq[i]=0; for ( i=0;i<100;i++) Freq[A[i] ++; }

63 Frequency count of numbers ranging between 0 to 9

64 SPARSE MATRIX In many situations, matrix size is very large but out of it, most of the elements are zeros (not necessarily always zeros). And only a small fraction of the matrix is actually used. A matrix of such type is called a sparse matrix,

66 Sparse matrix and its representation

67 Transpose Of Sparse Matrix Simple Transpose Fast Transpose

68 Time complexity of manual technique is O (mn).

70 Time complexity will be O (n . T) = O (n . mn) = O (mn2) which is worst than the conventional transpose with time complexity O (mn) Simple Sparse matrix transpose

71 Fast Sparse matrix transpose In worst case, i.e. T= m × n (non-zero elements) the magnitude becomes O (n +mn) = O (mn) which is the same as 2-D transpose However the constant factor associated with fast transpose is quite high When T is sufficiently small, compared to its maximum of m . n, fast transpose will work faster

72 It is usually formed from the character set of the programming language The value n is the length of the character string S where n ³ 0  If n = 0 then S is called a null string or empty string String Manipulation Using Array

73 Basically a string is stored as a sequence of characters in one- dimensional character array say A. char A[10] ="STRING" ; Each string is terminated by a special character that is null character ‘0’. This null character indicates the end or termination of each string.

74 There are various operations that can be performed on the string: To find the length of a string To concatenate two strings To copy a string To reverse a string String compare Palindrome check To recognize a sub string.

75 Characteristics of array An array is a finite ordered collection of homogeneous data elements. In array, successive elements of list are stored at a fixed distance apart. Array is defined as set of pairs-( index and value). Array allows random access to any element In array, insertion and deletion of elements in between positions requires data movement. Array provides static allocation, which means space allocation done once during compile time, can not be changed run time.

76 Advantage of Array Data Structure Arrays permit efficient random access in constant time 0(1). Arrays are most appropriate for storing a fixed amount of data and also for high frequency of data retrievals as data can be accessed directly. Wherever there is a direct mapping between the elements and there positions, arrays are the most suitable data structures. Ordered lists such as polynomials are most efficiently handled using arrays. Arrays are useful to form the basis for several more complex data structures, such as heaps, and hash tables and can be used to represent strings, stacks and queues.

77 Disadvantage of Array Data Structure Arrays provide static memory management. Hence during execution the size can neither be grown nor shrunk. Array is inefficient when often data is to inserted or deleted as inserting and deleting an element in array needs a lot of data movement. Hence array is inefficient for the applications, which very often need insert and delete operations in between.

78 Applications of Arrays Although useful in their own right, arrays also form the basis for several more complex data structures, such as heaps, hash tables and can be used to represent strings, stacks and queues. All these applications benefit from the compactness and direct access benefits of arrays. Two-dimensional data when represented as Matrix and matrix operations.

4. Recursion - Data Structures using C++ by Varsha Patil

More Related Content

What's hot

Viewers also liked

Similar to 4. Recursion - Data Structures using C++ by Varsha Patil

More from widespreadpromotion

Recently uploaded

4. Recursion - Data Structures using C++ by Varsha Patil