Recursion

Recursion : 

Recursion Fundamentals Of Programming in C 1 Presented By: Saket Kr Pathak M.Sc. NT & M AMITY Institute Of Information Technology

Slide 2: 

Recursion Recursion is said as a mathematical concept which states that an expression such that each term is generated by repeating a particular mathematical operation. Here repeating is the iterative manner to perform same operation. As the approach of the programming language C, it can be performed and are in practice within the definition part of functions. Syntactically language provides the freedom to call function within it’s body defined. Definition of ‘Recursion’ as the logical prospective view states simply the iterative manner to perform any code snippet in C, but we always need a terminating condition to control the going on iterations. In the following sections we will discuss the iterative manner of recursion and the terminating condition in bit expanded form. 2 Fundamentals Of Programming in C

Slide 3: 

Amity Institute Of Information Technology 3 Recursive Functions Recursive functions are not different from the syntactical structure of the general functions that we had discussed in previous sections. They have same return type, function name, parameters enclosed within parenthesis. Declaration: int Think_and_ Play (int, char); We had discussed the syntactical view of the function, where return type is ‘int’, function name is ‘Think_and_Play’ and within the parenthesis we had defined the parameters as of data type integer with another one that is of data type character.

Slide 4: 

Amity Institute Of Information Technology 4 Now let us manipulate the definition of the our function, that we had declared in the previous slide from the general aspect of definition we had practiced till now. Definition: int _iFlag =0, _iTerminate = 0; int Think_and_Play(int _iBat, char _chBall) { if (_iFlag ==0) printf(“This is game cricket going on.”); _iFlag++; if(_iTerminate < 6) { printf(“Hit the Ball with the Bat.”); ++ _iTerminate; Think_and_Play(1, ‘0’); return 1; } }

Slide 5: 

Amity Institute Of Information Technology 5 As in sequence of explanation, this snippet code has few syntactical statements. In the very first the program counter encounters with the Variables of type integer that are global to the function. Then it encounters the return type of the function following with the function name, and the parameters defined. All of these has the considerable part in function definition structure of C language that we had discussed in the previous sections of declaration. As encounter with the right curly braces comes into just next statement, it considers the following structure is for definition. In the definition part, the first if condition is doing its formal responsibility to control the execution of print function where the defined condition will be true i.e. when the value of the variable ‘_iFlag’ is strictly equal to 0.

Slide 6: 

Amity Institute Of Information Technology 6 The next statement is simply incrementing the value stored in the memory location termed as ‘_iFlag’ (the variable name). Then our point of consideration comes into picture in the execution of second ‘if’ structure. Here in this ‘if’ structure program counter will execute the statements defined within ‘if’ body, if and only if the condition gets true. It means whenever the condition defined with the if statements returns ‘Boolean True’ value then the further body will execute. So we can consider the controlling system of the execution of ‘if-body’ is properly controlled through the condition defined there in if statement. Now within the body concerned, we have a print function that supports its definition with two arguments defined as ‘String type’ and another is ‘Variable Length Argument’ (i.e. null in the snippet). Function performs the role successfully and control passes further.

Slide 7: 

Amity Institute Of Information Technology 7 The followed statement says to increment the value stored in the memory location corresponds to the variable name ‘_iTerminate’. Here logically this increasing value of ‘_iTerminate’ and the if condition defined above will cause the terminating condition. At the near end of the body, we have a function call as ‘Think_and_Play(…, …)’. Since here we are calling the same function that is executing, is said as recursion. Therefore, calling of the function from its own body forms a loop like execution pattern and is said as recursion. It is also considered as the alternative programming pattern of looping structure (i.e. of ‘for loop’ and ‘while loop’). The end statement says to return the value to the calling function as ‘return 1’, that declares the successful completion of all other statements defined above.

Slide 8: 

Amity Institute Of Information Technology 8 Discussion Typically, recursion is quite elegant and requires fewer variables to make the same calculation as iterative looping structural programs. It take care of its assigned records by maintaining the stack of arguments and variables for each invocation. It has been calculated in some machines a simple recursive program call with snippet defining one integer argument can be requires 8 32-bit words on the stack. Let us consider a snippet code of fibonacci sequence and calculate it’s efficiency in the following section.

Slide 9: 

Amity Institute Of Information Technology 9 Snippet-Code: int fibonacci (int _iNam) { if (_iNam <= 1) return _iNam; else return (fibonacci(_iNam-1)+fibonacci(_iNam-2)) } Through ‘main()’ call the ‘fibonacci()’ with the index value to next generate recursive value.

Slide 10: 

Amity Institute Of Information Technology 10 Dissection of ‘fibonacci’ Program: int fibonacci (int _iNam) Here in the above statement the function name ‘fibonacci’ has the parameter type defined as ‘integer’ having the return type as ‘integrer’. The right braces comes as the starting point of the snippet code. if (_iNam <= 1) return _iNam; Here in the above two statements the condition followed by ‘if’, is establised as the terminating point if condition gets it satisfied. On the satisfactory mode of ‘if’ statement the value stored in _iNam return back to the calling.

Slide 11: 

Amity Institute Of Information Technology 11 else return (fibonacci(_iNam -1) + fibonacci(_iNam - 2)); In the else part of the consecutive ‘if’ statement the return value is a bit complex. At first the recursion takes place for the first part from left and returns 1 decremented value i.e. ‘-1’ to the previous value, simultaneously it maintains a stack of all the new variables and concern values for each invocation. That will be come in use for the next recursive call. The next recursive call initializes the variable with the decremented value as ‘-2’. At the end when function call completes then the respective sum of the value returns back to the calling statement in ‘main()’. The left braces shows the termination of the code snippet.

Slide 12: 

Amity Institute Of Information Technology 12 As in the following we have the table showing 10 number of function calls in simultaneous recursion.

Slide 13: 

Amity Institute Of Information Technology 13 As in the above table describes, the value passed through the parameter, the value that the function returns and the number of recursive steps a function can perform up to 9 sequential calls. Cons: Recursive programs typically use a large amount of computer memory and the greater the recursion, the more memory used. Recursive programs can be confusing to develop and extremely complicated to debug. Pros: Recursion is a natural fit for some types of problems as ‘Tower of Hanoi’.

Slide 14: 

Amity Institute Of Information Technology 14 Practice ‘Towers of Hanoi’ Problem: The Classical Towers of Hanoi - an initial position of all disks is on post 'A‘.

Slide 15: 

Amity Institute Of Information Technology 15 The target solution of the puzzle is to build the tower on post 'C'. The number of discs can vary, but there are only three towers. The goal is to transfer the discs from one tower another tower. However you can move only one disk at a time and you can never place a bigger disc over a smaller disk.

Slide 16: 

Amity Institute Of Information Technology 16 Algorithm to solve the above problem: Move the top 3 disks from Source to Auxiliary tower, Move the 4th disk from Source to Destination tower, Move the 3 disks from Auxiliary tower to Destination tower. Transfer the top 3 disks from Source to Auxiliary tower can again be thought as a fresh problem and can be solve in the same manner.

Slide 17: 

Amity Institute Of Information Technology 17 Let us do it step by step: At first move the ‘Disc1’ to ‘B’ and ‘Disc2’ to ‘C’ as in following figure:

Slide 18: 

Amity Institute Of Information Technology 18 Move the ‘Disc1’ to the top of the ‘Disc2’ at ‘C’ and ‘Disc3’ at ‘B’. Move the ‘Disc1’ to ‘A’ at the top of ‘Disc4’ and ‘Disc2’ at ‘B’ to the top of ‘Disc3’.

Slide 19: 

Amity Institute Of Information Technology 19 Move the ‘Disc1’ at ‘B’ to the top of ‘Disc2’ and ‘Disc4’ at ‘A’. Move the ‘Disc1’ at ‘C’ to the top of ‘Disc4’ and ‘Disc2’ at ‘A’.

Slide 20: 

Amity Institute Of Information Technology 20 Move the ‘Disc1’ at ‘A’ to the top of ‘Disc2’ and ‘Disc3’ to the top of ‘disc4’ at ‘A’. Move the ‘Disc1’ at ‘B’ and ‘Disc2’ at ‘B’ to the top of ‘Disc3’.

Slide 21: 

Amity Institute Of Information Technology 21 Move the ‘Disc1’ at the top of ‘Disc2’ at ‘C’. Congratulations you got your answer. Code implementation is up to you people as hint use the concept of stack and just follow the steps Above described.