Python for Computational Problem Solving - Unit 3: Recursion - PDF

PYTHON FOR COMPUTATIONAL PROBLEM SOLVING Prof. Sowmya Shree P, Prof. Sindhu R Pai Department of Computer Science and Engineering  PYTHON FOR COMPUTATIONAL PROBLEM SOLVING Unit - 3: Functions – Recursion Prof. Sowmya Shree P, Prof. Sindhu R Pai Department of Computer Science and Engineering P...

PYTHON FOR COMPUTATIONAL PROBLEM SOLVING Prof. Sowmya Shree P, Prof. Sindhu R Pai Department of Computer Science and Engineering  PYTHON FOR COMPUTATIONAL PROBLEM SOLVING Unit - 3: Functions – Recursion Prof. Sowmya Shree P, Prof. Sindhu R Pai Department of Computer Science and Engineering PYTHON FOR COMPUTATIONAL PROBLEM SOLVING Functions - Recursion Recursion : Function calling itself There are many problems for which the solution can be expressed in terms of the problem itself. Computational problem solving via the use of recursion is a powerful Function A problem-solving approach. ……………………….. Ex: Factorial of n can be expressed as n times factorial of (n – 1) if n > 0 ………………………… and factorial of 0 can be expressed as 1. Call Function A ………………………. Terminating condition Recursive Function Definition 1 PYTHON FOR COMPUTATIONAL PROBLEM SOLVING Functions - Recursion Recursion : Function calling itself Need for Recursion We can reduce the length of our code and make it easier to read and write. Solve complex problems by breaking them down to simpler ones. 2 PYTHON FOR COMPUTATIONAL PROBLEM SOLVING Functions - Recursion Recursion : Function calling itself Criteria for Recursion: 1. Recursive function should have a terminating/stopping condition 2. Each call to recursive function must be towards terminating condition 3 PYTHON FOR COMPUTATIONAL PROBLEM SOLVING Functions - Recursion Recursion : Function calling itself Characteristics of Recursive function: 1. There must be at least one base case whose solution is known without further recursive breakdown. 2. Problems that are not a base case are broken down into subproblems and work towards a base case. 3. There is a way to derive the solution of the original problem from the solutions of the recursively solved subproblems. 4 PYTHON FOR COMPUTATIONAL PROBLEM SOLVING Functions - Recursion Recursion : Example: Computation of factorial of a number factorial(0)=1 factorial(1)=1*1 The complete definition of the factorial function is, factorial(2)=2*1 factorial(3)=3*2*1 1 if n=0 factorial(4)=4*3*2*1 factorial(n)=. n*factorial(n-1) otherwise.. factorial(n)=n*(n-1)*(n-2)*……………….*1 factorial(n)=n * factorial(n-1) 5 PYTHON FOR COMPUTATIONAL PROBLEM SOLVING Functions - Recursion How Recursion Works? Recursion is implemented using stack because activation records are to be stored in LIFO order (last in first out). An activation record of a function call contains arguments, return address and local variables of the function. Stack is a linear data structure in which elements are inserted to the top and deleted from the top. 6 PYTHON FOR COMPUTATIONAL PROBLEM SOLVING Functions - Recursion Implementation of Recursion using Stack Consider the example, Computing factorial of a number using recursion def fact(n): #Recursive Function if n == 0 : #terminating condition res = 1 else: res = n * fact(n - 1) return res Suppose we want to compute fact(3) the above function gets executed in the manner of Stack. 7 PYTHON FOR COMPUTATIONAL PROBLEM SOLVING Functions - Recursion When the function call is made recursively, the activation record for each call will be placed on the top of the stack. Initially, fact(3) is called which recursively calls fact(2), fact(1), fact(0) and activation record gets inserted to top of the stack. 8 PYTHON FOR COMPUTATIONAL PROBLEM SOLVING Functions - Recursion For n=0 i.e. base case(Termination Condition), the function call stops and fact(0) is popped out from the top of the stack. It returns 1, then the recursion backtracks and solve the pending function calls are popped out of the stack and fact(3) is computed. 9 PYTHON FOR COMPUTATIONAL PROBLEM SOLVING Functions - Recursion Stack Memory Allocation In Python, function calls and the references are stored in stack memory. Allocation happens on contiguous blocks of memory – referred as Function call Stack. The size of memory to be allocated is known to the compiler and whenever a function is called, its variables get memory allocated on the stack. Any local memory assignments such as variable initializations inside the particular functions are stored temporarily on the function call stack, where it is deleted once the function returns. This allocation onto a contiguous block of memory is handled by the compiler using predefined routines. 10 PYTHON FOR COMPUTATIONAL PROBLEM SOLVING Functions - Recursion Example 1– Compute factorial of a number def fact(n): #Recursive Function if n == 0 : #terminating condition res = 1 else: res = n * fact(n - 1) return res print(fact(5)) print(fact(0)) Output: 120 1 11 PYTHON FOR COMPUTATIONAL PROBLEM SOLVING Functions - Recursion Example 2 – Compute GCD of two numbers def gcd(m, n): #Recursive Function if m == n : #terminating condition res = m elif m > n : res = gcd(m -n, n) else: res = gcd(m, n - m) return res print(“GCD : ", gcd(65, 91)) Output: GCD : 13 12 PYTHON FOR COMPUTATIONAL PROBLEM SOLVING Functions - Recursion Example 3 – Generate Fibonacci Series upto n_terms def fib(n): #Recursive Function if n