Scribd Logo
Upload

Welcome to Scribd!

  • 97 views

    Lect 25

    Uploaded by

    Geetika Bhardwaj
    Recursion is a technique that involves defining a concept or procedure in terms of itself. In programming, a recursive procedure is one that calls itself during its execution. There are two main uses of recursion: as a way to define things and as a solution design approach known as "divide and conquer". While recursion can produce elegant solutions, iterative algorithms are often more efficient since recursion involves overhead from function calls and stack usage that iterative approaches do not have. Therefore, recursion works best for algorithms and data structures that naturally support it, and iterative solutions are generally better for large inputs due to lower memory and time costs from recursion.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPTX, PDF, TXT or read online from Scribd

    Lect 25

    Uploaded by

    Geetika Bhardwaj
    97 views28 pages
    Recursion is a technique that involves defining a concept or procedure in terms of itself. In programming, a recursive procedure is one that calls itself during its execution. There are two main uses of recursion: as a way to define things and as a solution design approach known as "divide and conquer". While recursion can produce elegant solutions, iterative algorithms are often more efficient since recursion involves overhead from function calls and stack usage that iterative approaches do not have. Therefore, recursion works best for algorithms and data structures that naturally support it, and iterative solutions are generally better for large inputs due to lower memory and time costs from recursion.

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Recursion is a technique that involves defining a concept or procedure in terms of itself. In programming, a recursive procedure is one that calls itself during its execution. There are two main uses of recursion: as a way to define things and as a solution design approach known as "divide and conquer". While recursion can produce elegant solutions, iterative algorithms are often more efficient since recursion involves overhead from function calls and stack usage that iterative approaches do not have. Therefore, recursion works best for algorithms and data structures that naturally support it, and iterative solutions are generally better for large inputs due to lower memory and time costs from recursion.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    97 views28 pages

    Lect 25

    Uploaded by

    Geetika Bhardwaj
    Recursion is a technique that involves defining a concept or procedure in terms of itself. In programming, a recursive procedure is one that calls itself during its execution. There are two main uses of recursion: as a way to define things and as a solution design approach known as "divide and conquer". While recursion can produce elegant solutions, iterative algorithms are often more efficient since recursion involves overhead from function calls and stack usage that iterative approaches do not have. Therefore, recursion works best for algorithms and data structures that naturally support it, and iterative solutions are generally better for large inputs due to lower memory and time costs from recursion.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    of 28

    Recursion

    Recursion: A way of defining a concept where the text of the definition refers to the concept that is being defined. In programming: A recursive procedure is a procedure which calls itself. Classic example: Here is the non-recursive definition of fhe factorial function: n! = 1 2 3 (n-1) n Here is the recursive definition of a factorial: (here f(n) = n!) Code of recursive procedures, in functional programming languages is almost identical to a recursive definition!

    Recursion
    Recursion is more than just a programming technique. It has two other uses in computer science and software engineering, namely: as a way of describing, defining, or specifying things. as a way of designing solutions to problems (divide and conquer).

    Iterative Definition
    In general, we can define the factorial function in the following way:

    Iterative Definition
    This is an iterative definition of the factorial function. It is iterative because the definition only contains the algorithm parameters and not the algorithm itself. This will be easier to see after defining the recursive implementation.

    Recursive Definition
    We can also define the factorial function in the following way:

    Iterative vs. Recursive


    Iterative factorial(n) = 1 n x (n-1) x (n-2) x Recursive factorial(n) = 1 n x factorial(n-1) x2x1

    Function does NOT calls itself

    if n=0 if n>0

    Function calls itself

    if n=0 if n>0

    Recursion
    To see how the recursion works, let s break down the factorial function to solve factorial(3)

    Breakdown

    Here, we see that we start at the top level, factorial(3), and simplify the problem into 3 x factorial(2). Now, we have a slightly less complicated problem in factorial(2), and we simplify this problem into 2 x factorial(1).

    Breakdown

    We continue this process until we are able to reach a problem that has a known solution. In this case, that known solution is factorial(0) = 1. The functions then return in reverse order to complete the solution.

    Breakdown
    This known solution is called the base case. Every recursive algorithm must have a base case to simplify to. Otherwise, the algorithm would run forever (or until the computer ran out of memory).

    Breakdown
    The other parts of the algorithm, excluding the base case, are known as the general case. For example: 3 x factorial(2) general case 2 x factorial(1) general case etc

    Breakdown
    After looking at both iterative and recursive methods, it appears that the recursive method is much longer and more difficult. If that s the case, then why would we ever use recursion? It turns out that recursive techniques, although more complicated to solve by hand, are very simple and elegant to implement in a computer.

    Iteration vs. Recursion


    Now that we know the difference between an iterative algorithm and a recursive algorithm, we will develop both an iterative and a recursive algorithm to calculate the factorial of a number. We will then compare the 2 algorithms.

    Iterative Algorithm
    factorial(n) { i=1 factN = 1 loop (i <= n) factN = factN * i i=i+1 end loop return factN }

    The iterative solution is very straightforward. We simply loop through all the integers between 1 and n and multiply them together.

    How Recursion Works


    When the function is finished, it needs to return to the function that called it. The calling function then wakes up and continues processing. One important point in this interaction is that, unless changed through call-by- reference, all local data in the calling module must remain unchanged.

    How Recursion Works


    Therefore, when a function is called, some information needs to be saved in order to return the calling module back to its original state (i.e., the state it was in before the call). We need to save information such as the local variables and the spot in the code to return to after the called function is finished.

    How Recursion Works


    To do this we use a stack. Before a function is called, all relevant data is stored in a stackframe. This stackframe is then pushed onto the system stack. After the called function is finished, it simply pops the system stack to return to the original state.

    How Recursion Works


    By using a stack, we can have functions call other functions which can call other functions, etc. Because the stack is a first-in, last-out data structure, as the stackframes are popped, the data comes out in the correct order.

    Limitations of Recursion
    Recursion is a powerful problem-solving technique that often produces very clean solutions to even the most complex problems. Recursive solutions can be easier to understand and to describe than iterative solutions.

    Main disadvantage of programming recursively


    The main disadvantage of programming recursively is that, while it makes it easier to write simple and elegant programs, it also makes it easier to write inefficient ones.
    when we use recursion to solve problems we are interested exclusively with correctness, and not at all with efficiency. Consequently, our simple, elegant recursive algorithms may be inherently inefficient.

    Limitations of Recursion
    By using recursion, you can often write simple, short implementations of your solution. However, just because an algorithm can be implemented in a recursive manner doesn t mean that it should be implemented in a recursive manner.

    Limitations of Recursion
    Recursion works the best when the algorithm and/or data structure that is used naturally supports recursion. One such data structure is the tree (more to come). One such algorithm is the binary search algorithm that we discussed earlier in the course.

    Limitations of Recursion
    Recursive solutions may involve extensive overhead because they use calls. When a call is made, it takes time to build a stackframe and push it onto the system stack. Conversely, when a return is executed, the stackframe must be popped from the stack and the local variables reset to their previous values this also takes time.

    Limitations of Recursion
    In general, recursive algorithms run slower than their iterative counterparts. Also, every time we make a call, we must use some of the memory resources to make room for the stackframe.

    Limitations of Recursion
    Therefore, if the recursion is deep, say, factorial(1000), we may run out of memory. Because of this, it is usually best to develop iterative algorithms when we are working with large numbers.

    You might also like