Scribd Logo
Upload

Welcome to Scribd!

  • 8 views

    CS-212L-Data Structures and Algorithms

    Uploaded by

    Suhaib Awan

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd

    CS-212L-Data Structures and Algorithms

    Uploaded by

    Suhaib Awan
    8 views5 pages

    Original Title

    Lab Recusion

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    8 views5 pages

    CS-212L-Data Structures and Algorithms

    Uploaded by

    Suhaib Awan

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    of 5

    CS-212L-Data Structures and Algorithms

    Data Structures and Algorithms CS Lab Manual

    Academic Year: 2020

    Semester 3

    Course Code: CS-212L

    Course Title: Data structures and Algorithms


    CS-212L-Data Structures and Algorithms
    Data Structures and Algorithms CS Lab Manual

    Type of Lab: Open Ended Weightage:


    CLO 1: CLO’s.

    State the Rubric Cognitive/Understanding CLO1 Rubric


    A

    Rubric A: Cognitive Domain


    Evaluation Method: GA shall evaluate the students for
    Question according to following rubrics.
    CLO 0 1 2 3 4
    CLO1 Mention
    Milestones
    with
    respect to
    rubrics
    CS-212L-Data Structures and Algorithms
    Data Structures and Algorithms CS Lab Manual

    Lab 2
    Recursion

    Objectives: To get familiar with recursion concept in Data


    structure and algorithms

    Processing steps:
    Step 1: what is recursion?
    Computer programming languages allow a module or function to
    call itself. This technique is known as recursion. In recursion, a
    function α either calls itself directly or calls a function β that in
    turn calls the original function α. The function α is called
    recursive function.

    Step 2: Why we studied recursion?


     Do while run in program until the job is meet, so recursion is
    also used as placement of it.
     It allow to get deeper and deeper until the base condition is
    meet

    Step 3: How the recursion is implemented?


    As, we see the Fibonacci  series we can see :
    def fib(n):
    if n==0:
    return 1
    elif n==1:
    return 1
    else:
    return fib(n-1) + fib(n-2)
    CS-212L-Data Structures and Algorithms
    Data Structures and Algorithms CS Lab Manual

    it is implemented in stack as :
    fib(5)= fib(4) + fib(3)
    = fib(3) + fib(2) + fib(2) + fib(1)
    = fib(2) + fib(1) + fib(1) + fib(0) + fib(1) + fib(0) + 1
    = fib(1) + fib(0) + 1 + 1 + 1 + 1 + 1 + 1
    = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1= 8

    Step 4: Termination

    Let’s spend some time and talk about the terminating


    cases. These are critical as without these cases, the function
    would just keep calling itself indefinitely and get stuck in an
    endless loop. So the first step of writing any recursive function is
    specifying the conditions at which it can exit (terminate).
    n the case of Fibonacci, we know that that the first two values in
    the sequence are 1 and 1. That is, fib(0) = 1 and fib(1) = 1. So
    anytime we get an input of 0 or 1, then we can just return a 1
    and call it a day. And if our input is greater than 1, then we need
    to work towards our terminating cases (of 0 or 1) by Incepting
    towards them via a sequence of recursive function calls like we
    did above.

    Step 5: practical use:


    Its more practically used in traversing the tree where we
    know how much we should go deep.
    root
    |\
    |\
    b1 b2
    more slightly deeper as:
    CS-212L-Data Structures and Algorithms
    Data Structures and Algorithms CS Lab Manual

    root ____________
    |\\
    |\\
    b1 ____ b2 b3
    |\\|\
    l1 l2 l3 l1 l2

    Class activity

    REFRENCES:

    You might also like