Class 11 Recursion

University:
Augusta University
Course:
CYB101 | Introduction to Defensive Cyber Operations
Academic year:

2024
Views:

0

Pages:

32
Author:

Supriya Kaur

Recursion What is recursion? • Sometimes, the best way to solve a problem • • is by solving a smaller version of the exact same problem. Recursion is a technique that solves a problem by solving a smaller problem of the same type A function which calls itself directly or indirectly again and again as long as the given condition is not satisfied. Recursion • What is the difference between a normal function • • • and recursion ? A normal function is called by the main() but the recursive function is called by itself as long as the given condition is not satisfied. What kind of problem do we need recursive solution? When a large problem is broken down into smaller and smaller problems until we reach a problem that is small enough to be solved. Recursion • Recursion is defined anything in terms of itself. Recursion • Types of Recursion: Recursive functions are of two types. 1. Direct recursion(Preemptive) 2. Indirect recursion(non-preemptive) Direct recursion int abc() { …. …. abc(); } Recursion Recursion Important points: 1.There must be a terminating condition . This condition is called base case for the problem. Ex. The factorial of a number can be defined as number multiplied by its predecessors continuously until the processor become 1. 2.There must be an if condition in the recursive routine. This if clause specifies the terminating condition. 3.Each time a recursive call is made, a new memory space is allocated to each local variables used in the recursion. 4. There must be a depreciate value. Problems defined recursively • There are many problems whose solution can be defined recursively Example: n factorial n!= n!= 1 if n = 0 (n-1)!*n if n > 0 1 if n = 0 1*2*3*…*(n-1)*n if n > 0 (recursive solution) (closed form solution) Recursion Coding the factorial function • Recursive implementation int Factorial(int n) { if (n==0) // base case return 1; else return n * Factorial(n-1); } Recursion vs. iteration • Iteration can be used in place of recursion – An iterative algorithm uses a looping construct – A recursive algorithm uses a branching structure • Recursive solutions are often less efficient, in • terms of both time and space, than iterative solutions Recursion can simplify the solution of a problem, often resulting in shorter, more easily understood source code How do I write a recursive function? • Determine the size factor • Determine the base case(s) (the one for which you know the answer) • Determine the general case(s) (the one where the problem is expressed as a smaller version of itself) • Verify the algorithm Three-Question Verification Method 1. The Base-Case Question: Is there a nonrecursive way out of the function, and does the routine work correctly for this "base" case? 2. The Smaller-Caller Question: Does each recursive call to the function involve a smaller case of the original problem, leading inescapably to the base case? 3. The General-Case Question: Assuming that the recursive call(s) work correctly, does the whole function work correctly? Factorial of a given number #include void main() { int n; int fact(int); clrscr(); printf("\nEnter a number :"); scanf("%d",&n); printf("\nThe factorial of %d is : %d", n,fact(n)); getch(); } int fact( int p) { int x; if(p==0) return(1); else x=p*fact(p-1); return(x); } Working procedure WAP to find out GCD of two numbers x or y if x=y gcd(x,y)= gcd(x, y-x) if y>x gcd(x-y, y) if x>y code #include #include int recgcd(int,int); void main() { int a,b,gcd; printf("Input any two numbers:"); scanf("%d %d",&a,&b); gcd=recgcd(a,b); printf("Gcd of %d and %d=%d",a,b,gcd); getch(); } int recgcd(int a, int b) { if(a==b) return(a); else { if(a>b) return(recgcd(a-b,b)); else return(recgcd(a,b-a)); } } Parameter Recursion Iteration Definition Recursion involves a recursive function which Iteration involves the usage of loops through which calls itself repeatedly until a base condition is not a set of statements are executed repeatedly until the reached. condition is not false. Termination condition Here termination condition is a base case defined Termination condition is the condition specified in within the recursive function. the definition of the loop. Infinite Case If base case is never reached it leads to infinite recursion leading to memory crash. Memory Usage Recursion uses stack area to store the current state Iteration uses the permanent storage area only for of the function,due to which memory usage is the variables involved in its code block, hence high. memory usage is less. Code Size Code size is comparitively smaller. Performance Since stack are is used to store and restore the Since iteration does not have to keep re-initializing state of recursive function after every function call its component variables and neither has to store , performance is comparitively slow. function states, the performance is fast. Memory Runout There is a possibility of running out of memory, since for each function call stack area gets used. Overhead Recursive functions involve extensive overhead, There is no overhead in Iteration. as for each function call the current state, parameters etc have to be pushed and popped out from stack. Applications Factorial , Fibonacci Series etc. If condition is never false, it leads to infinite iteration with computers CPU cycle being used repeatedly. Code size is comparitively larger. There is no possibility of running out of memory as stack area is not used. Finding average of a data series, creating multiplication table etc. Scope of Variables in C • In C language, each variable has a storage class • • which decides scope and lifetime of that variable. All variables defined in a C program are allocated some physical location in memory where the variable’s value is stored. Memory and CPU registers are examples of storage locations where a variable’s value can be stored. The scope of a variable determines over what region of the program a variable is actually available for use. CPU REGISTERS TO STORE DATA VALUES Memory Layout to store data Scope of Variables in C Storage classes provide the following information: 1.Where the variable would be stored. 2.What will be the initial value of the variable; i.e., the default value for the variable. 3.What is the scope of the variable; i.e., if the variable is accessible globally or is local to a function. 4.What is the life of the variable; i.e., how long would the variable exist in memory. • The scope determines over what region of a program in which a variable is available for use. • The lifetime refers to the period during which a variable retains a given value during execution of the program. It is also referred to as longevity. • • Scope of a Variable The scope of a variable may be either local scope or Global scope. Local scope means the scope of a variable is restricted with the function in which that variable is declared. A local variable is not accessible outside that scope. Scope of a Variable • Global scope refers, the variable declared outside the functions including main(). Global variable can be shared by all compound modules. Scope of a Variable • Life time of • • • a variable refers for what period a variable retains a given value during program. Lifetime of a variable is the time difference between when a variable is created and when it is destroyed. There are two types of storage space provided to the variable. One is inside the RAM and the other is in the cpu registers. The default value of a variable can be either garbage or zero. Scope of Variables in C There are four storage class specifiers in C language, they are: Auto Register extern static Automatic variable : auto data_type variable_1, variable_2,..., variable_n; • Automatic variables are declared inside a block/function in which they are to be utilized. • These variables are created when a function is called and destroyed automatically when a function is terminated, hence the name automatic variable. • Auto variables are therefore local to the function in which they are declared. Automatic variable Adv: 1. Same auto variable name can be used in different block. 2. The memory is economically used. 3. Auto variables are inherent protection because of local scope. Register variable • The main memory is slower than cpu registers. • CPU also has a small storage area called registers • • • • which are used for quick storage and retrieval. Whenever some of the variables are repeated again and again they can be assigned as register variable for better performance. Since register has no address, so we can’t use & operator on a register variable. Array, function , structure variables can’t be declared as register variable. All register variables are by default local. Register variable declaration •Long int, float or double variables can’t be declared as register variable, bcz the size is longer than cpu register. •If declared then it will be automatically converted into memory variable. auto int I=10; void main() { printf(“%d”,i); } // ? ? ? •Formal variable(only char, int) can be declared as register variables. STATIC VARIABLE • • • • A variable can be declared as a static variable by using the keyword static. static variables are initialized only once and they remain in existence till the end of the program. A static variable can either be local (to a function) or global. Static variable are always initialized by 0. Throughout the program the value of a static variable is remain unchanged. void main() { static int var=5; printf(“%d”, var--); If (var) main(); } • External Storage class When the size of the program become veri large then it has to be divided into number of functional parts and each part is stored in a separate file. The global variable declared in one file can be accessed in other file by declaring external file.