IT1II20-Lab 11 Recursion Solved

(a)         What    do   the following      two programs       print?

(b)        What    do   functions      orange  and guave do         when     called    with       positive       integer  as    input     argument?       (answer in    plain      language)

(c)         http://www.pythontutor.com/visualize.html#mode

Open     file  t1.py             and copy      both       programs            into Python  Vizualizer.       Make     sure               you understand all       the functions      that        are  running (at       the same     time)             as    you step       through the execution     of    the program.

 

Task 2: 

(a)          What     does        the  following        program       print?

(b)         Write     one sentence         that describes       abstractly       (in    plain        English)  what       the  function mulberry        does        when       called      with positive  integer   as    input       argument.

(c)           

 
 
 

What     would     happen   if      we   made             mulberry(-3) call  in     the  main,       instead   of     mulberry        (5)? (d) http://www.pythontutor.com/visualize.html#mode

Open      file   t1.py                and copy        code       below              into Python    Vizualizer.      Make       sure         you  understand    how the  program is       running           and what       it      is      doing      as       you  step through  its    execution       of     the       program.

(e)  What       is      the  maximum       number  of       mulberry        functions        running  at     any       one time,       i.e.   what       is      the  maximum       number  mulberry        functions        on    the       stack       at     any  one time?

-   What   is      the  answer   for   general   n?    

-   Make   the  call  mulberry(1000)    in     Python     shell        instead   mulberry(4)   of     and     observe  what       happened?     Why        did     that happen?

Task 3: 

(a)         What    does      the following      program       print?

(b)        Write    one sentence      that        describes       abstractly     (in   plain      English) what       the function       cantaloupe  does       when     called    with       positive       integer  as    input     argument.

(c)         

 
 
 

http://www.pythontutor.com/visualize.html#mode

Open     file  t1.py             and copy      code       below           into Python  Vizualizer.    Make       sure               you understand how       the       program       is     running        and what      it       is     doing     as    you step       through the       execution     of    the program.

(d)        What    is     the maximum    number of       cantaloupe  functions      running at       any one time,      

i.e.  what      is     the maximum    number       cantaloupe  functions      on   the stack      at       any one time? What is     the answer  for       general n?

Task 4: 

(a)         What    does      the following      program       print?

(b)        Write    one sentence      that        describes       abstractly     (in   plain      English) what       the function       almond does             given     a     list  of    numbers      lst as       input     argument?

(c)         http://www.pythontutor.com/visualize.html#mode

Open     file  t1.py             and copy      code       below           into Python  Vizualizer.    Make       sure               you understand how       the       program       is     running        and what      it       is     doing     as    you step       through the       execution     of    the program.  


Task 5: 

(a)         What    does      the following      program       print?

(b)        Write    one sentence      that        describes       abstractly     (in   plain      English) what       the function               fig   does             given     a     list  of    numbers      lst as       input     argument     and high=len(lst)-1.   

(c)         http://www.pythontutor.com/visualize.html#mode

Open     file  t1.py             and copy      code       below           into Python  Vizualizer.    Make       sure               you understand how       the       program       is     running        and what      it       is     doing     as    you step       through the       execution     of    the program.

 

Task 6: 

(a)         What    does      the following      program       print?

(b)        Write    one sentence      that        describes       abstractly     (in   plain      English) what       the function               almond does             (given    strings   s      and ch as      input       and assuming             ch contains  only       one character)

(c)         http://www.pythontutor.com/visualize.html#mode

Open     file  t1.py             and copy      code       below           into Python  Vizualizer.    Make       sure               you understand how       the       program       is     running        and what      it       is     doing     as    you step       through the       execution     of    the program.

 

Recursion:   Paper  Study   
• Open     file     sum_prod.py

It  contains    contains 2   functions     that   both   compute     the     sum:   1+2+3     …+n.  One   computes    it   in  the   ‘usual’    way   using   python’s loops (this   is   called,    iterative solution),   and    the     other in  a   recursive way  (i.e.    using   function calls   that   solve a   problem on the     smaller   problem instance)

Similarly  sum_prod.py   contains 2   function that   both  compute     the   product  1*2*3…*n (thus   they   compute     

n!,   i.e.     n   factorial)     in   iterative and    recursive   way   (as we     have  seen   in  class)

Study  with   TAs    and  understand well   all these 4  solutions.         

Recursion: Programming Exercise  1
•                Write  a   recursive function  (do     not     use    python’s  loops),    called m, that  computes    the     following  series,    given positive  integer   i:   

 

•                In   the     “main”   write a  loop   that   tests  your  function m by  displaying  values     m(i) for  i    =   1,  2,  .    .    .    ,    10,     as  follows

m(1)= 0.3333333333333333 m(2)= 0.7333333333333334 m(3)= 1.161904761904762 m(4)= 1.6063492063492064 m(5)= 2.060894660894661 m(6)= 2.5224331224331227 m(7)= 2.9890997890997895 m(8)= 3.459688024393907 m(9)= 3.933372234920223 m(10)= 4.409562711110699

Recursion: Programming Exercise  2
•                Write a   recursive function,     called count_digits,   that counts    the     number  of digits in  a   given positive integer   n.

•                Test    your   function:

 

Recursion: Programming Exercise  3
•                 A       string     is     a     palindrome if      it  reads     the same     from      the left  and from      the right.     For example,  word     “kayak” is     a     palindrome, so  is     a     name     “Anna”, so   is     a  word     “a”. Word    “uncle” is     not a  palindrome.

•                 Write       a     recursive      function,  called    is_palindrome,          that  returns  True       if     the input     string  is     a     palindrome and otherwise  returns  False.     Test       your  function.

•                 Notice:    a     word     of    length   n is a          palindrom    if     1st and   nth letter  are  the same,    

AND       2nd and  (n-1)st are     the same,    and        so   on   …    until       we  get  to    the        “middle”      

 

Idea/Strategy
Checking  if   a   string is   a  palindrome can    be divided  into    two    subproblems:

1.            Check if   the     1st and    the last    character    in  the string are     the     same 

2.            Ignore     the     two    end characters   and    check if the     rest    of  

the     substring     is   a palindrome.

Notice that   the     2nd subproblem is   the     same as  the     original  problem but  smaller   in  size.

Useful string methods:  lower(),  and    string slicing

Recursion: Programming Exercise  4
•                 Refine     your       function  is_palindrome,          and call  the  modified      version, is_palindrome_v2,  such       that        it     ignores  all  characters   but the characters   that  correspond  to    the letters   of  English  alphabet.     You may       find  Python’s       string     method .isalpha()  useful.   

•                 Test  your       function       with       the  following      at    least:

 

Recursion:   Programming   Exercise 5: GCD
The       greatest       common      divisor       (GCD)    of    two integers (at   least      one of       which    is     not zero),     is     the largest       positive integer  that        divides  the       numbers      without a     remainder.  For       example,      the GCD       of    12   and 8     is       4.

The       following      technique    is       known   as    Euclid’s Algorithm    because it       appears in    Euclid’s Elements      (Book    7,       ca.  300 BC). It     may       be   the oldest       nontrivial     algorithm.

The       process is     based    on   the       observation that,      if     r is  the       remainder   when     a is  divided  by   b,       then       the common      divisors of    a and b are      the same     as    the common       divisors of    b and     r.     Thus      we  can       use the equation gcd(a,b)     =     gcd(b,r)

to   successively reduce  the problem       of       computing   a     GCD       to    the problem       of    computing   the GCD       of    smaller       and smaller  pairs      of    integers.       For       example,      gcd(36,  20)  =     gcd(20,  16)       =     gcd(16,  4)    =     gcd(4,    0)    =     4     

implies  that        the GCD       of    36   and 20   is       4.    It     can be   shown   that        for  any       two starting numbers,     this repeated       reduction     eventually    produces      a       pair where   the second  number is     0.       Then      the GCD       is     the other       number in    the pair.       

Write    a     recursive      function       called       gcd that        takes     two integer       parameters a and     b (you    can assume       a=b)     and that        uses       Euclid’s       algorithm     to    compute      and return       the greatest       common      divisor   of       the two numbers.             Test       your       function.

Difficult question:  GCD
What   is   the depth  of  the recursion (i.e.     the maximum number    of  gcd methods   on the stack/memory)   of your    gcd      function   if    you called  it    with    gcd(36,     20)?    You can      find     this      out by  drawing the diagrams  as  we did in   class    and or  running    your    function   and the gcd(36,     20) in   Python Visualizer.

Here    is   a    difficult     question   and food    for thought:   What  is   the maximum depth  of  the recursion  of your    gcd      method    for general     a and     b    (where      a=b)?