Recursion & Testcase

1.Recursion:

a).Recursion means “defining something in terms of itself” usually at some smaller scale, perhaps multiple times, to achieve your objective.

i.e. functions can call themselves to solve smaller subproblems. 

e.g. Fibonacci numbers

fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2)  for n >= 2

def fib(n):
    if n <= 1:
        return n
    t = fib(n-1) + fib(n-2)
    return t 

b). ! Nested-lists:

# some recursive functions on nested lists

def nested_depth(L):
    """
    Return if L is non-list, or 1 + maximum of depths of elements list L.
    Not defined for infinitely nested lists.

    >>> nested_depth(3)
    0
    >>> nested_depth([1, 2, 3])
    1
    >>> nested_depth([1, [2, 3], 4])
    2
    """

    return (1 + max([nested_depth(x) for x in L] + [0])
            if isinstance(L, list) else 0)

def rec_max(L):
    """
    Return the maximum number in possibly nested list of numbers.

    >>> rec_max([17, 21, 0])
    21
    >>> rec_max([17, [21, 24], 0])
    24
    """

    return max([rec_max(x) if isinstance(x, list) else x for x in L])


if __name__ == '__main__':
    import doctest
    doctest.testmod() 

2.Testcase: 

When choosing test cases, consider the following factors:

• Size
  For collections (strings, lists, tuples, dictionaries) test with:
  • empty collection
  • a collection with 1 item
  • smallest interesting case
  • collection with several items
• Dichotomies
  Consider your situation:
  For example:
  • vowels/non-vowels
  • even/odd
  • positive/negative
  • empty/full
  • etc.
• Boundaries
  If a function behaves differently for a value near a particular threshold (i.e. an if statement checking when a value is 3; 3 is a threshold), test at the that threshold.
• Order
  If a function behaves differently when the values are in a different order, identify and test each of those orders.

There is often overlap between the categories, so one test case may fall into more than 1 category.

 - import unittest

 - if __name__ == '__main__':
     unittest.main(exit=False)

 

18.7. Glossary

base case

A branch of the conditional statement in a recursive function that does not give rise to further recursive calls.

infinite recursion

A function that calls itself recursively without ever reaching any base case. Eventually, infinite recursion causes a runtime error.

recursion

The process of calling a function that is already executing.

recursive call

The statement that calls an already executing function. Recursion can also be indirect — function f can call g which calls h, and h could make a call back to f.

recursive definition

A definition which defines something in terms of itself. To be useful it must include base cases which are not recursive. In this way it differs from a circular definition. Recursive definitions often provide an elegant way to express complex data structures, like a directory that can contain other directories, or a menu that can contain other menus.