Notebook

Note: Click on "Kernel" > "Restart Kernel and Clear All Outputs" in JupyterLab before reading this notebook to reset its output. If you cannot run this file on your machine, you may want to open it in the cloud .

Chapter 4: Recursion & Looping¶

While controlling the flow of execution with an if statement is a must-have building block in any programming language, it alone does not allow us to run a block of code repetitively, and we need to be able to do precisely that to write useful software.

The for statement shown in some examples before might be the missing piece in the puzzle. However, we can live without it and postpone its official introduction until the second half of this chapter.

Instead, we dive into the big idea of iteration by studying the concept of recursion first. This order is opposite to many other introductory books that only treat the latter as a nice-to-have artifact, if at all. Yet, understanding recursion sharpens one's mind and contributes to seeing problems from a different angle.

Recursion¶

A popular joke among programmers by an unknown author goes like this (cf., discussion):

"In order to understand recursion, you must first understand recursion."

A function that calls itself is recursive, and the process of executing such a function is called recursion.

Recursive functions contain some form of a conditional check (e.g., if statement) to identify a base case that ends the recursion when reached. Otherwise, the function would keep calling itself forever.

The meaning of the word recursive is similar to circular. However, a truly circular definition is not very helpful, and we think of a recursive function as kind of a "circular function with a way out at the end."

Trivial Example: Countdown¶

A rather trivial toy example illustrates the important aspects concretely: If called with any positive integer as its n argument, countdown() just prints that number and calls itself with the new n being the old n minus 1. This continues until countdown() is called with n=0. Then, the flow of execution hits the base case, and the function calls stop.

In [1]:

def countdown(n):
    """Print a countdown until the party starts.

    Args:
        n (int): seconds until the party begins
    """
    if n == 0:
        print("Happy New Year!")
    else:
        print(n)
        countdown(n - 1)

In [2]:

countdown(3)

3
2
1
Happy New Year!

As trivial as this seems, a lot of complexity is hidden in this implementation. In particular, the order in which objects are created and de-referenced in memory might not be apparent right away as PythonTutor shows: Each time countdown() is called, Python creates a new frame in the part of the memory where it manages all the names. This way, Python isolates all the different n variables from each other. As new frames are created until we reach the base case, after which the frames are destroyed in the reversed order, this is called a stack of frames in computer science terminology. In simple words, a stack is a last-in-first-out (LIFO) task queue. Each frame has a single parent frame, namely the one whose recursive function call created it.

Recursion in Mathematics¶

Recursion plays a vital role in mathematics as well, and we likely know about it from some introductory course, for example, in combinatorics .

Easy Example: Factorial

The factorial function, denoted with the $!$ symbol, is defined as follows for all non-negative integers:

$0! = 1$

$n! = n*(n-1)!$

Whenever we find a recursive way of formulating an idea, we can immediately translate it into Python in a naive way (i.e., we create a correct program that may not be an efficient implementation yet).

Below is a first version of factorial(): The return statement does not have to be a function's last code line, and we may indeed have several return statements as well.

In [3]:

def factorial(n):
    """Calculate the factorial of a number.

    Args:
        n (int): number to calculate the factorial for

    Returns:
        factorial (int)
    """
    if n == 0:
        return 1
    else:
        recurse = factorial(n - 1)
        result = n * recurse
        return result

When we read such code, it is often easier not to follow every function call (i.e., factorial(n - 1) here) in one's mind but assume we receive a return value as specified in the documentation. Some call this approach a leap of faith. We practice this already whenever we call built-in functions (e.g., print() or len() ) where we would have to read C code in many cases.

To visualize all the computational steps of the exemplary factorial(3), we use PythonTutor : The recursion again creates a stack of frames in memory. In contrast to the previous trivial example, each frame leaves a return value in memory after it is destroyed. This return value is then assigned to the recurse variable within the parent frame and used to compute result.

In [4]:

factorial(3)

Out[4]:

In [5]:

factorial(10)

Out[5]:

A Pythonista would formulate factorial() in a more concise way using the so-called early exit pattern: No else-clause is needed as reaching a return statement ends a function call immediately. Furthermore, we do not need the temporary variables recurse and result.

As PythonTutor shows, this implementation is more efficient as it only requires 18 computational steps instead of 24 to calculate factorial(3), an improvement of 25 percent!

In [6]:

def factorial(n):
    """Calculate the factorial of a number.

    Args:
        n (int): number to calculate the factorial for

    Returns:
        factorial (int)
    """
    if n == 0:
        return 1
    return n * factorial(n - 1)

In [7]:

factorial(3)

Out[7]:

In [8]:

factorial(10)

Out[8]:

Note that the math module in the standard library provides a factorial() function as well, and we should, therefore, never implement it ourselves in a real codebase.

In [9]:

import math

In [10]:

help(math.factorial)

Help on built-in function factorial in module math:

factorial(n, /)
    Find n!.

    Raise a ValueError if x is negative or non-integral.

In [11]:

math.factorial(3)

Out[11]:

In [12]:

math.factorial(10)

Out[12]:

"Involved" Example: Euclid's Algorithm

As famous philosopher Euclid already shows in his "Elements" (ca. 300 BC), the greatest common divisor of two integers, i.e., the largest number that divides both integers without a remainder, can be efficiently computed with the following code. This example illustrates that a recursive solution to a problem is not always easy to understand.

In [13]:

def gcd(a, b):
    """Calculate the greatest common divisor of two numbers.

    Args:
        a (int): first number
        b (int): second number

    Returns:
        gcd (int)
    """
    if b == 0:
        return a 
    return gcd(b, a % b)

In [14]:

gcd(12, 4)

Out[14]:

Euclid's algorithm is stunningly fast, even for large numbers. Its speed comes from the use of the modulo operator %. However, this is not true for recursion in general, which may result in slow programs if not applied correctly.

In [15]:

gcd(112233445566778899, 987654321)

Out[15]:

As expected, for two prime numbers the greatest common divisor is of course $1$ .

In [16]:

gcd(7, 7919)

Out[16]:

The math module in the standard library provides a gcd() function as well, and, therefore, we should again never implement it on our own.

In [17]:

help(math.gcd)

Help on built-in function gcd in module math:

gcd(*integers)
    Greatest Common Divisor.

In [18]:

math.gcd(12, 4)

Out[18]:

In [19]:

math.gcd(112233445566778899, 987654321)

Out[19]:

In [20]:

math.gcd(7, 7919)

Out[20]:

"Easy at first Glance" Example: Fibonacci Numbers

The Fibonacci numbers are an infinite sequence of non-negative integers that are calculated such that every number is the sum of its two predecessors where the first two numbers of the sequence are defined to be $0$ and $1$ . For example, the first 13 numbers are:

$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144$

Let's write a function fibonacci() that calculates the $i$ th Fibonacci number where $0$ is the $0$ th number. Looking at the numbers in a backward fashion (i.e., from right to left), we realize that the return value for fibonacci(i) can be reduced to the sum of the return values for fibonacci(i - 1) and fibonacci(i - 2) disregarding the two base cases.

In [21]:

def fibonacci(i):
    """Calculate the ith Fibonacci number.

    Args:
        i (int): index of the Fibonacci number to calculate

    Returns:
        ith_fibonacci (int)
    """
    if i == 0:
        return 0
    elif i == 1:
        return 1
    return fibonacci(i - 1) + fibonacci(i - 2)

In [22]:

fibonacci(12)  # = 13th number

Out[22]:

Efficiency of Algorithms¶

This implementation is highly inefficient as small Fibonacci numbers already take a very long time to compute. The reason for this is exponential growth in the number of function calls. As PythonTutor shows, fibonacci() is called again and again with the same i arguments.

To understand this in detail, we have to study algorithms and data structures (e.g., with this book), a discipline within computer science, and dive into the analysis of time complexity of algorithms .

Luckily, in the Fibonacci case, the inefficiency can be resolved with a caching (i.e., "reuse") strategy from the field of dynamic programming , namely memoization . We do so in Chapter 9 , after introducing the dict data type.

Let's measure the average run times for fibonacci() and varying i arguments with the %%timeit cell magic that comes with Jupyter.

In [23]:

%%timeit -n 100
fibonacci(12)

38.9 µs ± 1.48 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [24]:

%%timeit -n 100
fibonacci(24)

12.2 ms ± 77.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [25]:

%%timeit -n 1 -r 1
fibonacci(36)

3.89 s ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)

In [26]:

%%timeit -n 1 -r 1
fibonacci(37)

6.28 s ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)

Infinite Recursion¶

If a recursion does not reach its base case, it theoretically runs forever. Luckily, Python detects that and saves the computer from crashing by raising a RecursionError.

The simplest possible infinite recursion is generated like so.

In [27]:

def run_forever():
    """Also a pointless function should have a docstring."""
    run_forever()

In [28]:

run_forever()

---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
Cell In[28], line 1
----> 1 run_forever()

Cell In[27], line 3, in run_forever()
      1 def run_forever():
      2     """Also a pointless function should have a docstring."""
----> 3     run_forever()

Cell In[27], line 3, in run_forever()
      1 def run_forever():
      2     """Also a pointless function should have a docstring."""
----> 3     run_forever()

    [... skipping similar frames: run_forever at line 3 (2974 times)]

Cell In[27], line 3, in run_forever()
      1 def run_forever():
      2     """Also a pointless function should have a docstring."""
----> 3     run_forever()

RecursionError: maximum recursion depth exceeded

However, even the trivial countdown() function from above is not immune to infinite recursion. Let's call it with 3.1 instead of 3. What goes wrong here?

In [29]:

countdown(3.1)

3.1
2.1
1.1
0.10000000000000009
-0.8999999999999999
-1.9
-2.9
-3.9
-4.9
-5.9
-6.9
-7.9
-8.9
-9.9
-10.9
-11.9
-12.9
-13.9
-14.9
-15.9
-16.9
-17.9
-18.9
-19.9
-20.9
-21.9
-22.9
-23.9
-24.9
-25.9
-26.9
-27.9
-28.9
-29.9
-30.9
-31.9
-32.9
-33.9
-34.9
-35.9
-36.9
-37.9
-38.9
-39.9
-40.9
-41.9
-42.9
-43.9
-44.9
-45.9
-46.9
-47.9
-48.9
-49.9
-50.9
-51.9
-52.9
-53.9
-54.9
-55.9
-56.9
-57.9
-58.9
-59.9
-60.9
-61.9
-62.9
-63.9
-64.9
-65.9
-66.9
-67.9
-68.9
-69.9
-70.9
-71.9
-72.9
-73.9
-74.9
-75.9
-76.9
-77.9
-78.9
-79.9
-80.9
-81.9
-82.9
-83.9
-84.9
-85.9
-86.9
-87.9
-88.9
-89.9
-90.9
-91.9
-92.9
-93.9
-94.9
-95.9
-96.9
-97.9
-98.9
-99.9
-100.9
-101.9
-102.9
-103.9
-104.9
-105.9
-106.9
-107.9
-108.9
-109.9
-110.9
-111.9
-112.9
-113.9
-114.9
-115.9
-116.9
-117.9
-118.9
-119.9
-120.9
-121.9
-122.9
-123.9
-124.9
-125.9
-126.9
-127.9
-128.9
-129.9
-130.9
-131.9
-132.9
-133.9
-134.9
-135.9
-136.9
-137.9
-138.9
-139.9
-140.9
-141.9
-142.9
-143.9
-144.9
-145.9
-146.9
-147.9
-148.9
-149.9
-150.9
-151.9
-152.9
-153.9
-154.9
-155.9
-156.9
-157.9
-158.9
-159.9
-160.9
-161.9
-162.9
-163.9
-164.9
-165.9
-166.9
-167.9
-168.9
-169.9
-170.9
-171.9
-172.9
-173.9
-174.9
-175.9
-176.9
-177.9
-178.9
-179.9
-180.9
-181.9
-182.9
-183.9
-184.9
-185.9
-186.9
-187.9
-188.9
-189.9
-190.9
-191.9
-192.9
-193.9
-194.9
-195.9
-196.9
-197.9
-198.9
-199.9
-200.9
-201.9
-202.9
-203.9
-204.9
-205.9
-206.9
-207.9
-208.9
-209.9
-210.9
-211.9
-212.9
-213.9
-214.9
-215.9
-216.9
-217.9
-218.9
-219.9
-220.9
-221.9
-222.9
-223.9
-224.9
-225.9
-226.9
-227.9
-228.9
-229.9
-230.9
-231.9
-232.9
-233.9
-234.9
-235.9
-236.9
-237.9
-238.9
-239.9
-240.9
-241.9
-242.9
-243.9
-244.9
-245.9
-246.9
-247.9
-248.9
-249.9
-250.9
-251.9
-252.9
-253.9
-254.9
-255.9
-256.9
-257.9
-258.9
-259.9
-260.9
-261.9
-262.9
-263.9
-264.9
-265.9
-266.9
-267.9
-268.9
-269.9
-270.9
-271.9
-272.9
-273.9
-274.9
-275.9
-276.9
-277.9
-278.9
-279.9
-280.9
-281.9
-282.9
-283.9
-284.9
-285.9
-286.9
-287.9
-288.9
-289.9
-290.9
-291.9
-292.9
-293.9
-294.9
-295.9
-296.9
-297.9
-298.9
-299.9
-300.9
-301.9
-302.9
-303.9
-304.9
-305.9
-306.9
-307.9
-308.9
-309.9
-310.9
-311.9
-312.9
-313.9
-314.9
-315.9
-316.9
-317.9
-318.9
-319.9
-320.9
-321.9
-322.9
-323.9
-324.9
-325.9
-326.9
-327.9
-328.9
-329.9
-330.9
-331.9
-332.9
-333.9
-334.9
-335.9
-336.9
-337.9
-338.9
-339.9
-340.9
-341.9
-342.9
-343.9
-344.9
-345.9
-346.9
-347.9
-348.9
-349.9
-350.9
-351.9
-352.9
-353.9
-354.9
-355.9
-356.9
-357.9
-358.9
-359.9
-360.9
-361.9
-362.9
-363.9
-364.9
-365.9
-366.9
-367.9
-368.9
-369.9
-370.9
-371.9
-372.9
-373.9
-374.9
-375.9
-376.9
-377.9
-378.9
-379.9
-380.9
-381.9
-382.9
-383.9
-384.9
-385.9
-386.9
-387.9
-388.9
-389.9
-390.9
-391.9
-392.9
-393.9
-394.9
-395.9
-396.9
-397.9
-398.9
-399.9
-400.9
-401.9
-402.9
-403.9
-404.9
-405.9
-406.9
-407.9
-408.9
-409.9
-410.9
-411.9
-412.9
-413.9
-414.9
-415.9
-416.9
-417.9
-418.9
-419.9
-420.9
-421.9
-422.9
-423.9
-424.9
-425.9
-426.9
-427.9
-428.9
-429.9
-430.9
-431.9
-432.9
-433.9
-434.9
-435.9
-436.9
-437.9
-438.9
-439.9
-440.9
-441.9
-442.9
-443.9
-444.9
-445.9
-446.9
-447.9
-448.9
-449.9
-450.9
-451.9
-452.9
-453.9
-454.9
-455.9
-456.9
-457.9
-458.9
-459.9
-460.9
-461.9
-462.9
-463.9
-464.9
-465.9
-466.9
-467.9
-468.9
-469.9
-470.9
-471.9
-472.9
-473.9
-474.9
-475.9
-476.9
-477.9
-478.9
-479.9
-480.9
-481.9
-482.9
-483.9
-484.9
-485.9
-486.9
-487.9
-488.9
-489.9
-490.9
-491.9
-492.9
-493.9
-494.9
-495.9
-496.9
-497.9
-498.9
-499.9
-500.9
-501.9
-502.9
-503.9
-504.9
-505.9
-506.9
-507.9
-508.9
-509.9
-510.9
-511.9
-512.9
-513.9
-514.9
-515.9
-516.9
-517.9
-518.9
-519.9
-520.9
-521.9
-522.9
-523.9
-524.9
-525.9
-526.9
-527.9
-528.9
-529.9
-530.9
-531.9
-532.9
-533.9
-534.9
-535.9
-536.9
-537.9
-538.9
-539.9
-540.9
-541.9
-542.9
-543.9
-544.9
-545.9
-546.9
-547.9
-548.9
-549.9
-550.9
-551.9
-552.9
-553.9
-554.9
-555.9
-556.9
-557.9
-558.9
-559.9
-560.9
-561.9
-562.9
-563.9
-564.9
-565.9
-566.9
-567.9
-568.9
-569.9
-570.9
-571.9
-572.9
-573.9
-574.9
-575.9
-576.9
-577.9
-578.9
-579.9
-580.9
-581.9
-582.9
-583.9
-584.9
-585.9
-586.9
-587.9
-588.9
-589.9
-590.9
-591.9
-592.9
-593.9
-594.9
-595.9
-596.9
-597.9
-598.9
-599.9
-600.9
-601.9
-602.9
-603.9
-604.9
-605.9
-606.9
-607.9
-608.9
-609.9
-610.9
-611.9
-612.9
-613.9
-614.9
-615.9
-616.9
-617.9
-618.9
-619.9
-620.9
-621.9
-622.9
-623.9
-624.9
-625.9
-626.9
-627.9
-628.9
-629.9
-630.9
-631.9
-632.9
-633.9
-634.9
-635.9
-636.9
-637.9
-638.9
-639.9
-640.9
-641.9
-642.9
-643.9
-644.9
-645.9
-646.9
-647.9
-648.9
-649.9
-650.9
-651.9
-652.9
-653.9
-654.9
-655.9
-656.9
-657.9
-658.9
-659.9
-660.9
-661.9
-662.9
-663.9
-664.9
-665.9
-666.9
-667.9
-668.9
-669.9
-670.9
-671.9
-672.9
-673.9
-674.9
-675.9
-676.9
-677.9
-678.9
-679.9
-680.9
-681.9
-682.9
-683.9
-684.9
-685.9
-686.9
-687.9
-688.9
-689.9
-690.9
-691.9
-692.9
-693.9
-694.9
-695.9
-696.9
-697.9
-698.9
-699.9
-700.9
-701.9
-702.9
-703.9
-704.9
-705.9
-706.9
-707.9
-708.9
-709.9
-710.9
-711.9
-712.9
-713.9
-714.9
-715.9
-716.9
-717.9
-718.9
-719.9
-720.9
-721.9
-722.9
-723.9
-724.9
-725.9
-726.9
-727.9
-728.9
-729.9
-730.9
-731.9
-732.9
-733.9
-734.9
-735.9
-736.9
-737.9
-738.9
-739.9
-740.9
-741.9
-742.9
-743.9
-744.9
-745.9
-746.9
-747.9
-748.9
-749.9
-750.9
-751.9
-752.9
-753.9
-754.9
-755.9
-756.9
-757.9
-758.9
-759.9
-760.9
-761.9
-762.9
-763.9
-764.9
-765.9
-766.9
-767.9
-768.9
-769.9
-770.9
-771.9
-772.9
-773.9
-774.9
-775.9
-776.9
-777.9
-778.9
-779.9
-780.9
-781.9
-782.9
-783.9
-784.9
-785.9
-786.9
-787.9
-788.9
-789.9
-790.9
-791.9
-792.9
-793.9
-794.9
-795.9
-796.9
-797.9
-798.9
-799.9
-800.9
-801.9
-802.9
-803.9
-804.9
-805.9
-806.9
-807.9
-808.9
-809.9
-810.9
-811.9
-812.9
-813.9
-814.9
-815.9
-816.9
-817.9
-818.9
-819.9
-820.9
-821.9
-822.9
-823.9
-824.9
-825.9
-826.9
-827.9
-828.9
-829.9
-830.9
-831.9
-832.9
-833.9
-834.9
-835.9
-836.9
-837.9
-838.9
-839.9
-840.9
-841.9
-842.9
-843.9
-844.9
-845.9
-846.9
-847.9
-848.9
-849.9
-850.9
-851.9
-852.9
-853.9
-854.9
-855.9
-856.9
-857.9
-858.9
-859.9
-860.9
-861.9
-862.9
-863.9
-864.9
-865.9
-866.9
-867.9
-868.9
-869.9
-870.9
-871.9
-872.9
-873.9
-874.9
-875.9
-876.9
-877.9
-878.9
-879.9
-880.9
-881.9
-882.9
-883.9
-884.9
-885.9
-886.9
-887.9
-888.9
-889.9
-890.9
-891.9
-892.9
-893.9
-894.9
-895.9
-896.9
-897.9
-898.9
-899.9
-900.9
-901.9
-902.9
-903.9
-904.9
-905.9
-906.9
-907.9
-908.9
-909.9
-910.9
-911.9
-912.9
-913.9
-914.9
-915.9
-916.9
-917.9
-918.9
-919.9
-920.9
-921.9
-922.9
-923.9
-924.9
-925.9
-926.9
-927.9
-928.9
-929.9
-930.9
-931.9
-932.9
-933.9
-934.9
-935.9
-936.9
-937.9
-938.9
-939.9
-940.9
-941.9
-942.9
-943.9
-944.9
-945.9
-946.9
-947.9
-948.9
-949.9
-950.9
-951.9
-952.9
-953.9
-954.9
-955.9
-956.9
-957.9
-958.9
-959.9
-960.9
-961.9
-962.9
-963.9
-964.9
-965.9
-966.9
-967.9
-968.9
-969.9
-970.9
-971.9
-972.9
-973.9
-974.9
-975.9
-976.9
-977.9
-978.9
-979.9
-980.9
-981.9
-982.9
-983.9
-984.9
-985.9
-986.9
-987.9
-988.9
-989.9
-990.9
-991.9
-992.9
-993.9
-994.9
-995.9
-996.9
-997.9
-998.9
-999.9
-1000.9
-1001.9
-1002.9
-1003.9
-1004.9
-1005.9
-1006.9
-1007.9
-1008.9
-1009.9
-1010.9
-1011.9
-1012.9
-1013.9
-1014.9
-1015.9
-1016.9
-1017.9
-1018.9
-1019.9
-1020.9
-1021.9
-1022.9
-1023.9
-1024.9
-1025.9
-1026.9
-1027.9
-1028.9
-1029.9
-1030.9
-1031.9
-1032.9
-1033.9
-1034.9
-1035.9
-1036.9
-1037.9
-1038.9
-1039.9
-1040.9
-1041.9
-1042.9
-1043.9
-1044.9
-1045.9
-1046.9
-1047.9
-1048.9
-1049.9
-1050.9
-1051.9
-1052.9
-1053.9
-1054.9
-1055.9
-1056.9
-1057.9
-1058.9
-1059.9
-1060.9
-1061.9
-1062.9
-1063.9
-1064.9
-1065.9
-1066.9
-1067.9
-1068.9
-1069.9
-1070.9
-1071.9
-1072.9
-1073.9
-1074.9
-1075.9
-1076.9
-1077.9
-1078.9
-1079.9
-1080.9
-1081.9
-1082.9
-1083.9
-1084.9
-1085.9
-1086.9
-1087.9
-1088.9
-1089.9
-1090.9
-1091.9
-1092.9
-1093.9
-1094.9
-1095.9
-1096.9
-1097.9
-1098.9
-1099.9
-1100.9
-1101.9
-1102.9
-1103.9
-1104.9
-1105.9
-1106.9
-1107.9
-1108.9
-1109.9
-1110.9
-1111.9
-1112.9
-1113.9
-1114.9
-1115.9
-1116.9
-1117.9
-1118.9
-1119.9
-1120.9
-1121.9
-1122.9
-1123.9
-1124.9
-1125.9
-1126.9
-1127.9
-1128.9
-1129.9
-1130.9
-1131.9
-1132.9
-1133.9
-1134.9
-1135.9
-1136.9
-1137.9
-1138.9
-1139.9
-1140.9
-1141.9
-1142.9
-1143.9
-1144.9
-1145.9
-1146.9
-1147.9
-1148.9
-1149.9
-1150.9
-1151.9
-1152.9
-1153.9
-1154.9
-1155.9
-1156.9
-1157.9
-1158.9
-1159.9
-1160.9
-1161.9
-1162.9
-1163.9
-1164.9
-1165.9
-1166.9
-1167.9
-1168.9
-1169.9
-1170.9
-1171.9
-1172.9
-1173.9
-1174.9
-1175.9
-1176.9
-1177.9
-1178.9
-1179.9
-1180.9
-1181.9
-1182.9
-1183.9
-1184.9
-1185.9
-1186.9
-1187.9
-1188.9
-1189.9
-1190.9
-1191.9
-1192.9
-1193.9
-1194.9
-1195.9
-1196.9
-1197.9
-1198.9
-1199.9
-1200.9
-1201.9
-1202.9
-1203.9
-1204.9
-1205.9
-1206.9
-1207.9
-1208.9
-1209.9
-1210.9
-1211.9
-1212.9
-1213.9
-1214.9
-1215.9
-1216.9
-1217.9
-1218.9
-1219.9
-1220.9
-1221.9
-1222.9
-1223.9
-1224.9
-1225.9
-1226.9
-1227.9
-1228.9
-1229.9
-1230.9
-1231.9
-1232.9
-1233.9
-1234.9
-1235.9
-1236.9
-1237.9
-1238.9
-1239.9
-1240.9
-1241.9
-1242.9
-1243.9
-1244.9
-1245.9
-1246.9
-1247.9
-1248.9
-1249.9
-1250.9
-1251.9
-1252.9
-1253.9
-1254.9
-1255.9
-1256.9
-1257.9
-1258.9
-1259.9
-1260.9
-1261.9
-1262.9
-1263.9
-1264.9
-1265.9
-1266.9
-1267.9
-1268.9
-1269.9
-1270.9
-1271.9
-1272.9
-1273.9
-1274.9
-1275.9
-1276.9
-1277.9
-1278.9
-1279.9
-1280.9
-1281.9
-1282.9
-1283.9
-1284.9
-1285.9
-1286.9
-1287.9
-1288.9
-1289.9
-1290.9
-1291.9
-1292.9
-1293.9
-1294.9
-1295.9
-1296.9
-1297.9
-1298.9
-1299.9
-1300.9
-1301.9
-1302.9
-1303.9
-1304.9
-1305.9
-1306.9
-1307.9
-1308.9
-1309.9
-1310.9
-1311.9
-1312.9
-1313.9
-1314.9
-1315.9
-1316.9
-1317.9
-1318.9
-1319.9
-1320.9
-1321.9
-1322.9
-1323.9
-1324.9
-1325.9
-1326.9
-1327.9
-1328.9
-1329.9
-1330.9
-1331.9
-1332.9
-1333.9
-1334.9
-1335.9
-1336.9
-1337.9
-1338.9
-1339.9
-1340.9
-1341.9
-1342.9
-1343.9
-1344.9
-1345.9
-1346.9
-1347.9
-1348.9
-1349.9
-1350.9
-1351.9
-1352.9
-1353.9
-1354.9
-1355.9
-1356.9
-1357.9
-1358.9
-1359.9
-1360.9
-1361.9
-1362.9
-1363.9
-1364.9
-1365.9
-1366.9
-1367.9
-1368.9
-1369.9
-1370.9
-1371.9
-1372.9
-1373.9
-1374.9
-1375.9
-1376.9
-1377.9
-1378.9
-1379.9
-1380.9
-1381.9
-1382.9
-1383.9
-1384.9
-1385.9
-1386.9
-1387.9
-1388.9
-1389.9
-1390.9
-1391.9
-1392.9
-1393.9
-1394.9
-1395.9
-1396.9
-1397.9
-1398.9
-1399.9
-1400.9
-1401.9
-1402.9
-1403.9
-1404.9
-1405.9
-1406.9
-1407.9
-1408.9
-1409.9
-1410.9
-1411.9
-1412.9
-1413.9
-1414.9
-1415.9
-1416.9
-1417.9
-1418.9
-1419.9
-1420.9
-1421.9
-1422.9
-1423.9
-1424.9
-1425.9
-1426.9
-1427.9
-1428.9
-1429.9
-1430.9
-1431.9
-1432.9
-1433.9
-1434.9
-1435.9
-1436.9
-1437.9
-1438.9
-1439.9
-1440.9
-1441.9
-1442.9
-1443.9
-1444.9
-1445.9
-1446.9
-1447.9
-1448.9
-1449.9
-1450.9
-1451.9
-1452.9
-1453.9
-1454.9
-1455.9
-1456.9
-1457.9
-1458.9
-1459.9
-1460.9
-1461.9
-1462.9
-1463.9
-1464.9
-1465.9
-1466.9
-1467.9
-1468.9
-1469.9
-1470.9
-1471.9
-1472.9
-1473.9
-1474.9
-1475.9
-1476.9
-1477.9
-1478.9
-1479.9
-1480.9
-1481.9
-1482.9
-1483.9
-1484.9
-1485.9
-1486.9
-1487.9
-1488.9
-1489.9
-1490.9
-1491.9
-1492.9
-1493.9
-1494.9
-1495.9
-1496.9
-1497.9
-1498.9
-1499.9
-1500.9
-1501.9
-1502.9
-1503.9
-1504.9
-1505.9
-1506.9
-1507.9
-1508.9
-1509.9
-1510.9
-1511.9
-1512.9
-1513.9
-1514.9
-1515.9
-1516.9
-1517.9
-1518.9
-1519.9
-1520.9
-1521.9
-1522.9
-1523.9
-1524.9
-1525.9
-1526.9
-1527.9
-1528.9
-1529.9
-1530.9
-1531.9
-1532.9
-1533.9
-1534.9
-1535.9
-1536.9
-1537.9
-1538.9
-1539.9
-1540.9
-1541.9
-1542.9
-1543.9
-1544.9
-1545.9
-1546.9
-1547.9
-1548.9
-1549.9
-1550.9
-1551.9
-1552.9
-1553.9
-1554.9
-1555.9
-1556.9
-1557.9
-1558.9
-1559.9
-1560.9
-1561.9
-1562.9
-1563.9
-1564.9
-1565.9
-1566.9
-1567.9
-1568.9
-1569.9
-1570.9
-1571.9
-1572.9
-1573.9
-1574.9
-1575.9
-1576.9
-1577.9
-1578.9
-1579.9
-1580.9
-1581.9
-1582.9
-1583.9
-1584.9
-1585.9
-1586.9
-1587.9
-1588.9
-1589.9
-1590.9
-1591.9
-1592.9
-1593.9
-1594.9
-1595.9
-1596.9
-1597.9
-1598.9
-1599.9
-1600.9
-1601.9
-1602.9
-1603.9
-1604.9
-1605.9
-1606.9
-1607.9
-1608.9
-1609.9
-1610.9
-1611.9
-1612.9
-1613.9
-1614.9
-1615.9
-1616.9
-1617.9
-1618.9
-1619.9
-1620.9
-1621.9
-1622.9
-1623.9
-1624.9
-1625.9
-1626.9
-1627.9
-1628.9
-1629.9
-1630.9
-1631.9
-1632.9
-1633.9
-1634.9
-1635.9
-1636.9
-1637.9
-1638.9
-1639.9
-1640.9
-1641.9
-1642.9
-1643.9
-1644.9
-1645.9
-1646.9
-1647.9
-1648.9
-1649.9
-1650.9
-1651.9
-1652.9
-1653.9
-1654.9
-1655.9
-1656.9
-1657.9
-1658.9
-1659.9
-1660.9
-1661.9
-1662.9
-1663.9
-1664.9
-1665.9
-1666.9
-1667.9
-1668.9
-1669.9
-1670.9
-1671.9
-1672.9
-1673.9
-1674.9
-1675.9
-1676.9
-1677.9
-1678.9
-1679.9
-1680.9
-1681.9
-1682.9
-1683.9
-1684.9
-1685.9
-1686.9
-1687.9
-1688.9
-1689.9
-1690.9
-1691.9
-1692.9
-1693.9
-1694.9
-1695.9
-1696.9
-1697.9
-1698.9
-1699.9
-1700.9
-1701.9
-1702.9
-1703.9
-1704.9
-1705.9
-1706.9
-1707.9
-1708.9
-1709.9
-1710.9
-1711.9
-1712.9
-1713.9
-1714.9
-1715.9
-1716.9
-1717.9
-1718.9
-1719.9
-1720.9
-1721.9
-1722.9
-1723.9
-1724.9
-1725.9
-1726.9
-1727.9
-1728.9
-1729.9
-1730.9
-1731.9
-1732.9
-1733.9
-1734.9
-1735.9
-1736.9
-1737.9
-1738.9
-1739.9
-1740.9
-1741.9
-1742.9
-1743.9
-1744.9
-1745.9
-1746.9
-1747.9
-1748.9
-1749.9
-1750.9
-1751.9
-1752.9
-1753.9
-1754.9
-1755.9
-1756.9
-1757.9
-1758.9
-1759.9
-1760.9
-1761.9
-1762.9
-1763.9
-1764.9
-1765.9
-1766.9
-1767.9
-1768.9
-1769.9
-1770.9
-1771.9
-1772.9
-1773.9
-1774.9
-1775.9
-1776.9
-1777.9
-1778.9
-1779.9
-1780.9
-1781.9
-1782.9
-1783.9
-1784.9
-1785.9
-1786.9
-1787.9
-1788.9
-1789.9
-1790.9
-1791.9
-1792.9
-1793.9
-1794.9
-1795.9
-1796.9
-1797.9
-1798.9
-1799.9
-1800.9
-1801.9
-1802.9
-1803.9
-1804.9
-1805.9
-1806.9
-1807.9
-1808.9
-1809.9
-1810.9
-1811.9
-1812.9
-1813.9
-1814.9
-1815.9
-1816.9
-1817.9
-1818.9
-1819.9
-1820.9
-1821.9
-1822.9
-1823.9
-1824.9
-1825.9
-1826.9
-1827.9
-1828.9
-1829.9
-1830.9
-1831.9
-1832.9
-1833.9
-1834.9
-1835.9
-1836.9
-1837.9
-1838.9
-1839.9
-1840.9
-1841.9
-1842.9
-1843.9
-1844.9
-1845.9
-1846.9
-1847.9
-1848.9
-1849.9
-1850.9
-1851.9
-1852.9
-1853.9
-1854.9
-1855.9
-1856.9
-1857.9
-1858.9
-1859.9
-1860.9
-1861.9
-1862.9
-1863.9
-1864.9
-1865.9
-1866.9
-1867.9
-1868.9
-1869.9
-1870.9
-1871.9
-1872.9
-1873.9
-1874.9
-1875.9
-1876.9
-1877.9
-1878.9
-1879.9
-1880.9
-1881.9
-1882.9
-1883.9
-1884.9
-1885.9
-1886.9
-1887.9
-1888.9
-1889.9
-1890.9
-1891.9
-1892.9
-1893.9
-1894.9
-1895.9
-1896.9
-1897.9
-1898.9
-1899.9
-1900.9
-1901.9
-1902.9
-1903.9
-1904.9
-1905.9
-1906.9
-1907.9
-1908.9
-1909.9
-1910.9
-1911.9
-1912.9
-1913.9
-1914.9
-1915.9
-1916.9
-1917.9
-1918.9
-1919.9
-1920.9
-1921.9
-1922.9
-1923.9
-1924.9
-1925.9
-1926.9
-1927.9
-1928.9
-1929.9
-1930.9
-1931.9
-1932.9
-1933.9
-1934.9
-1935.9
-1936.9
-1937.9
-1938.9
-1939.9
-1940.9
-1941.9
-1942.9
-1943.9
-1944.9
-1945.9
-1946.9
-1947.9
-1948.9
-1949.9
-1950.9
-1951.9
-1952.9
-1953.9
-1954.9
-1955.9
-1956.9
-1957.9
-1958.9
-1959.9
-1960.9
-1961.9
-1962.9
-1963.9
-1964.9
-1965.9
-1966.9
-1967.9
-1968.9
-1969.9
-1970.9
-1971.9
-1972.9
-1973.9
-1974.9
-1975.9
-1976.9
-1977.9
-1978.9
-1979.9
-1980.9
-1981.9
-1982.9
-1983.9
-1984.9
-1985.9
-1986.9
-1987.9
-1988.9
-1989.9
-1990.9
-1991.9
-1992.9
-1993.9
-1994.9
-1995.9
-1996.9
-1997.9
-1998.9
-1999.9
-2000.9
-2001.9
-2002.9
-2003.9
-2004.9
-2005.9
-2006.9
-2007.9
-2008.9
-2009.9
-2010.9
-2011.9
-2012.9
-2013.9
-2014.9
-2015.9
-2016.9
-2017.9
-2018.9
-2019.9
-2020.9
-2021.9
-2022.9
-2023.9
-2024.9
-2025.9
-2026.9
-2027.9
-2028.9
-2029.9
-2030.9
-2031.9
-2032.9
-2033.9
-2034.9
-2035.9
-2036.9
-2037.9
-2038.9
-2039.9
-2040.9
-2041.9
-2042.9
-2043.9
-2044.9
-2045.9
-2046.9
-2047.9
-2048.9
-2049.9
-2050.9
-2051.9
-2052.9
-2053.9
-2054.9
-2055.9
-2056.9
-2057.9
-2058.9
-2059.9
-2060.9
-2061.9
-2062.9
-2063.9
-2064.9
-2065.9
-2066.9
-2067.9
-2068.9
-2069.9
-2070.9
-2071.9
-2072.9
-2073.9
-2074.9
-2075.9
-2076.9
-2077.9
-2078.9
-2079.9
-2080.9
-2081.9
-2082.9
-2083.9
-2084.9
-2085.9
-2086.9
-2087.9
-2088.9
-2089.9
-2090.9
-2091.9
-2092.9
-2093.9
-2094.9
-2095.9
-2096.9
-2097.9
-2098.9
-2099.9
-2100.9
-2101.9
-2102.9
-2103.9
-2104.9
-2105.9
-2106.9
-2107.9
-2108.9
-2109.9
-2110.9
-2111.9
-2112.9
-2113.9
-2114.9
-2115.9
-2116.9
-2117.9
-2118.9
-2119.9
-2120.9
-2121.9
-2122.9
-2123.9
-2124.9
-2125.9
-2126.9
-2127.9
-2128.9
-2129.9
-2130.9
-2131.9
-2132.9
-2133.9
-2134.9
-2135.9
-2136.9
-2137.9
-2138.9
-2139.9
-2140.9
-2141.9
-2142.9
-2143.9
-2144.9
-2145.9
-2146.9
-2147.9
-2148.9
-2149.9
-2150.9
-2151.9
-2152.9
-2153.9
-2154.9
-2155.9
-2156.9
-2157.9
-2158.9
-2159.9
-2160.9
-2161.9
-2162.9
-2163.9
-2164.9
-2165.9
-2166.9
-2167.9
-2168.9
-2169.9
-2170.9
-2171.9
-2172.9
-2173.9
-2174.9
-2175.9
-2176.9
-2177.9
-2178.9
-2179.9
-2180.9
-2181.9
-2182.9
-2183.9
-2184.9
-2185.9
-2186.9
-2187.9
-2188.9
-2189.9
-2190.9
-2191.9
-2192.9
-2193.9
-2194.9
-2195.9
-2196.9
-2197.9
-2198.9
-2199.9
-2200.9
-2201.9
-2202.9
-2203.9
-2204.9
-2205.9
-2206.9
-2207.9
-2208.9
-2209.9
-2210.9
-2211.9
-2212.9
-2213.9
-2214.9
-2215.9
-2216.9
-2217.9
-2218.9
-2219.9
-2220.9
-2221.9
-2222.9
-2223.9
-2224.9
-2225.9
-2226.9
-2227.9
-2228.9
-2229.9
-2230.9
-2231.9
-2232.9
-2233.9
-2234.9
-2235.9
-2236.9
-2237.9
-2238.9
-2239.9
-2240.9
-2241.9
-2242.9
-2243.9
-2244.9
-2245.9
-2246.9
-2247.9
-2248.9
-2249.9
-2250.9
-2251.9
-2252.9
-2253.9
-2254.9
-2255.9
-2256.9
-2257.9
-2258.9
-2259.9
-2260.9
-2261.9
-2262.9
-2263.9
-2264.9
-2265.9
-2266.9
-2267.9
-2268.9
-2269.9
-2270.9
-2271.9
-2272.9
-2273.9
-2274.9
-2275.9
-2276.9
-2277.9
-2278.9
-2279.9
-2280.9
-2281.9
-2282.9
-2283.9
-2284.9
-2285.9
-2286.9
-2287.9
-2288.9
-2289.9
-2290.9
-2291.9
-2292.9
-2293.9
-2294.9
-2295.9
-2296.9
-2297.9
-2298.9
-2299.9
-2300.9
-2301.9
-2302.9
-2303.9
-2304.9
-2305.9
-2306.9
-2307.9
-2308.9
-2309.9
-2310.9
-2311.9
-2312.9
-2313.9
-2314.9
-2315.9
-2316.9
-2317.9
-2318.9
-2319.9
-2320.9
-2321.9
-2322.9
-2323.9
-2324.9
-2325.9
-2326.9
-2327.9
-2328.9
-2329.9
-2330.9
-2331.9
-2332.9
-2333.9
-2334.9
-2335.9
-2336.9
-2337.9
-2338.9
-2339.9
-2340.9
-2341.9
-2342.9
-2343.9
-2344.9
-2345.9
-2346.9
-2347.9
-2348.9
-2349.9
-2350.9
-2351.9
-2352.9
-2353.9
-2354.9
-2355.9
-2356.9
-2357.9
-2358.9
-2359.9
-2360.9
-2361.9
-2362.9
-2363.9
-2364.9
-2365.9
-2366.9
-2367.9
-2368.9
-2369.9
-2370.9
-2371.9
-2372.9
-2373.9
-2374.9
-2375.9
-2376.9
-2377.9
-2378.9
-2379.9
-2380.9
-2381.9
-2382.9
-2383.9
-2384.9
-2385.9
-2386.9
-2387.9
-2388.9
-2389.9
-2390.9
-2391.9
-2392.9
-2393.9
-2394.9
-2395.9
-2396.9
-2397.9
-2398.9
-2399.9
-2400.9
-2401.9
-2402.9
-2403.9
-2404.9
-2405.9
-2406.9
-2407.9
-2408.9
-2409.9
-2410.9
-2411.9
-2412.9
-2413.9
-2414.9
-2415.9
-2416.9
-2417.9
-2418.9
-2419.9
-2420.9
-2421.9
-2422.9
-2423.9
-2424.9
-2425.9
-2426.9
-2427.9
-2428.9
-2429.9
-2430.9
-2431.9
-2432.9
-2433.9
-2434.9
-2435.9
-2436.9
-2437.9
-2438.9
-2439.9
-2440.9
-2441.9
-2442.9
-2443.9
-2444.9
-2445.9
-2446.9
-2447.9
-2448.9
-2449.9
-2450.9
-2451.9
-2452.9
-2453.9
-2454.9
-2455.9
-2456.9
-2457.9
-2458.9
-2459.9
-2460.9
-2461.9
-2462.9
-2463.9
-2464.9
-2465.9
-2466.9
-2467.9
-2468.9
-2469.9
-2470.9
-2471.9
-2472.9
-2473.9
-2474.9
-2475.9
-2476.9
-2477.9
-2478.9
-2479.9
-2480.9
-2481.9
-2482.9
-2483.9
-2484.9
-2485.9
-2486.9
-2487.9
-2488.9
-2489.9
-2490.9
-2491.9
-2492.9
-2493.9
-2494.9
-2495.9
-2496.9
-2497.9
-2498.9
-2499.9
-2500.9
-2501.9
-2502.9
-2503.9
-2504.9
-2505.9
-2506.9
-2507.9
-2508.9
-2509.9
-2510.9
-2511.9
-2512.9
-2513.9
-2514.9
-2515.9
-2516.9
-2517.9
-2518.9
-2519.9
-2520.9
-2521.9
-2522.9
-2523.9
-2524.9
-2525.9
-2526.9
-2527.9
-2528.9
-2529.9
-2530.9
-2531.9
-2532.9
-2533.9
-2534.9
-2535.9
-2536.9
-2537.9
-2538.9
-2539.9
-2540.9
-2541.9
-2542.9
-2543.9
-2544.9
-2545.9
-2546.9
-2547.9
-2548.9
-2549.9
-2550.9
-2551.9
-2552.9
-2553.9
-2554.9
-2555.9
-2556.9
-2557.9
-2558.9
-2559.9
-2560.9
-2561.9
-2562.9
-2563.9
-2564.9
-2565.9
-2566.9
-2567.9
-2568.9
-2569.9
-2570.9
-2571.9
-2572.9
-2573.9
-2574.9
-2575.9
-2576.9
-2577.9
-2578.9
-2579.9
-2580.9
-2581.9
-2582.9
-2583.9
-2584.9
-2585.9
-2586.9
-2587.9
-2588.9
-2589.9
-2590.9
-2591.9
-2592.9
-2593.9
-2594.9
-2595.9
-2596.9
-2597.9
-2598.9
-2599.9
-2600.9
-2601.9
-2602.9
-2603.9
-2604.9
-2605.9
-2606.9
-2607.9
-2608.9
-2609.9
-2610.9
-2611.9
-2612.9
-2613.9
-2614.9
-2615.9
-2616.9
-2617.9
-2618.9
-2619.9
-2620.9
-2621.9
-2622.9
-2623.9
-2624.9
-2625.9
-2626.9
-2627.9
-2628.9
-2629.9
-2630.9
-2631.9
-2632.9
-2633.9
-2634.9
-2635.9
-2636.9
-2637.9
-2638.9
-2639.9
-2640.9
-2641.9
-2642.9
-2643.9
-2644.9
-2645.9
-2646.9
-2647.9
-2648.9
-2649.9
-2650.9
-2651.9
-2652.9
-2653.9
-2654.9
-2655.9
-2656.9
-2657.9
-2658.9
-2659.9
-2660.9
-2661.9
-2662.9
-2663.9
-2664.9
-2665.9
-2666.9
-2667.9
-2668.9
-2669.9
-2670.9
-2671.9
-2672.9
-2673.9
-2674.9
-2675.9
-2676.9
-2677.9
-2678.9
-2679.9
-2680.9
-2681.9
-2682.9
-2683.9
-2684.9
-2685.9
-2686.9
-2687.9
-2688.9
-2689.9
-2690.9
-2691.9
-2692.9
-2693.9
-2694.9
-2695.9
-2696.9
-2697.9
-2698.9
-2699.9
-2700.9
-2701.9
-2702.9
-2703.9
-2704.9
-2705.9
-2706.9
-2707.9
-2708.9
-2709.9
-2710.9
-2711.9
-2712.9
-2713.9
-2714.9
-2715.9
-2716.9
-2717.9
-2718.9
-2719.9
-2720.9
-2721.9
-2722.9
-2723.9
-2724.9
-2725.9
-2726.9
-2727.9
-2728.9
-2729.9
-2730.9
-2731.9
-2732.9
-2733.9
-2734.9
-2735.9
-2736.9
-2737.9
-2738.9
-2739.9
-2740.9
-2741.9
-2742.9
-2743.9
-2744.9
-2745.9
-2746.9
-2747.9
-2748.9
-2749.9
-2750.9
-2751.9
-2752.9
-2753.9
-2754.9
-2755.9
-2756.9
-2757.9
-2758.9
-2759.9
-2760.9
-2761.9
-2762.9
-2763.9
-2764.9
-2765.9
-2766.9
-2767.9
-2768.9
-2769.9
-2770.9
-2771.9
-2772.9
-2773.9
-2774.9
-2775.9
-2776.9
-2777.9
-2778.9
-2779.9
-2780.9
-2781.9
-2782.9
-2783.9
-2784.9
-2785.9
-2786.9
-2787.9
-2788.9
-2789.9
-2790.9
-2791.9
-2792.9
-2793.9
-2794.9
-2795.9
-2796.9
-2797.9
-2798.9
-2799.9
-2800.9
-2801.9
-2802.9
-2803.9
-2804.9
-2805.9
-2806.9
-2807.9
-2808.9
-2809.9
-2810.9
-2811.9
-2812.9
-2813.9
-2814.9
-2815.9
-2816.9
-2817.9
-2818.9
-2819.9
-2820.9
-2821.9
-2822.9
-2823.9
-2824.9
-2825.9
-2826.9
-2827.9
-2828.9
-2829.9
-2830.9
-2831.9
-2832.9
-2833.9
-2834.9
-2835.9
-2836.9
-2837.9
-2838.9
-2839.9
-2840.9
-2841.9
-2842.9
-2843.9
-2844.9
-2845.9
-2846.9
-2847.9
-2848.9
-2849.9
-2850.9
-2851.9
-2852.9
-2853.9
-2854.9
-2855.9
-2856.9
-2857.9
-2858.9
-2859.9
-2860.9
-2861.9
-2862.9
-2863.9
-2864.9
-2865.9
-2866.9
-2867.9
-2868.9
-2869.9
-2870.9
-2871.9
-2872.9
-2873.9
-2874.9
-2875.9
-2876.9
-2877.9
-2878.9
-2879.9
-2880.9
-2881.9
-2882.9
-2883.9
-2884.9
-2885.9
-2886.9
-2887.9
-2888.9
-2889.9
-2890.9
-2891.9
-2892.9
-2893.9
-2894.9
-2895.9
-2896.9
-2897.9
-2898.9
-2899.9
-2900.9
-2901.9
-2902.9
-2903.9
-2904.9
-2905.9
-2906.9
-2907.9
-2908.9
-2909.9
-2910.9
-2911.9
-2912.9
-2913.9
-2914.9
-2915.9
-2916.9
-2917.9
-2918.9
-2919.9
-2920.9
-2921.9
-2922.9
-2923.9
-2924.9
-2925.9
-2926.9
-2927.9
-2928.9
-2929.9
-2930.9
-2931.9
-2932.9
-2933.9
-2934.9
-2935.9
-2936.9
-2937.9
-2938.9
-2939.9
-2940.9
-2941.9
-2942.9
-2943.9
-2944.9
-2945.9
-2946.9
-2947.9
-2948.9
-2949.9
-2950.9
-2951.9
-2952.9
-2953.9
-2954.9
-2955.9
-2956.9
-2957.9
-2958.9
-2959.9
-2960.9
-2961.9
-2962.9
-2963.9
-2964.9
-2965.9
-2966.9
-2967.9
-2968.9
-2969.9
-2970.9

---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
Cell In[29], line 1
----> 1 countdown(3.1)

Cell In[1], line 11, in countdown(n)
      9 else:
     10     print(n)
---> 11     countdown(n - 1)

Cell In[1], line 11, in countdown(n)
      9 else:
     10     print(n)
---> 11     countdown(n - 1)

    [... skipping similar frames: countdown at line 11 (2972 times)]

Cell In[1], line 11, in countdown(n)
      9 else:
     10     print(n)
---> 11     countdown(n - 1)

Cell In[1], line 10, in countdown(n)
      8     print("Happy New Year!")
      9 else:
---> 10     print(n)
     11     countdown(n - 1)

File ~/Repositories/intro-to-python/.venv/lib/python3.12/site-packages/ipykernel/iostream.py:664, in OutStream.write(self, string)
    655 def write(self, string: str) -> Optional[int]:  # type:ignore[override]
    656     """Write to current stream after encoding if necessary
    657 
    658     Returns
   (...)
    662 
    663     """
--> 664     parent = self.parent_header
    666     if not isinstance(string, str):
    667         msg = f"write() argument must be str, not {type(string)}"  # type:ignore[unreachable]

RecursionError: maximum recursion depth exceeded

In the same way, a RecursionError occurs if we call factorial() with 3.1 instead of 3.

In [30]:

factorial(3.1)

---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
Cell In[30], line 1
----> 1 factorial(3.1)

Cell In[6], line 12, in factorial(n)
     10 if n == 0:
     11     return 1
---> 12 return n * factorial(n - 1)

Cell In[6], line 12, in factorial(n)
     10 if n == 0:
     11     return 1
---> 12 return n * factorial(n - 1)

    [... skipping similar frames: factorial at line 12 (2974 times)]

Cell In[6], line 12, in factorial(n)
     10 if n == 0:
     11     return 1
---> 12 return n * factorial(n - 1)

RecursionError: maximum recursion depth exceeded

The infinite recursions could easily be avoided by replacing n == 0 with n <= 0 in both functions and thereby generalizing them. However, even then, calling either countdown() or factorial() with a non-integer number is still semantically wrong.

Errors as above are a symptom of missing type checking: By design, Python allows us to pass in not only integers but objects of any type as arguments to the countdown() and factorial() functions. As long as the arguments "behave" like integers, we do not encounter any runtime errors. This is the case here as the two example functions only use the - and * operators internally, and, in the context of arithmetic, a float object behaves like an int object. So, the functions keep calling themselves until Python decides with a built-in heuristic that the recursion is likely not going to end and aborts the computations with a RecursionError. Strictly speaking, a RecursionError is, of course, a runtime error as well.

Duck Typing¶

The missing type checking is 100% intentional and considered a feature of rather than a bug in Python!

Pythonistas use the "technical" term duck typing to express the idea of two objects of different types behaving in the same way in a given context. The colloquial saying goes, "If it walks like a duck and it quacks like a duck, it must be a duck."

For example, we could call factorial() with the float object 3.0, and the recursion works out fine. So, because the 3.0 "walks" and "quacks" like a 3, it "must be" a 3.

In [31]:

factorial(3.0)

Out[31]:

6.0

In [32]:

factorial(3)

Out[32]:

We see similar behavior when we mix objects of types int and float with arithmetic operators. For example, 1 + 2.0 works because Python implicitly views the 1 as a 1.0 at runtime and then knows how to do floating-point arithmetic: Here, the int "walks" and "quacks" like a float.

In [33]:

1 + 2.0

Out[33]:

3.0

In [34]:

1.0 + 2.0

Out[34]:

3.0

The important lesson is that we must expect our functions to be called with objects of any type at runtime, as opposed to the one type we had in mind when defining the function.

Duck typing is possible because Python is a dynamically typed language. On the contrary, in statically typed languages like C, we must declare (i.e., "specify") the data type of every parameter in a function definition. Then, a RecursionError as for countdown(3.1) or factorial(3.1) above could not occur. For example, if we declared the countdown() and factorial() functions to only accept int objects, calling the functions with a float argument would immediately fail syntactically. As a downside, we would then lose the ability to call factorial() with 3.0, which is semantically correct nevertheless.

So, there is no black or white answer as to which of the two language designs is better. Yet, most professional programmers have strong opinions concerning duck typing, reaching from "love" to "hate." This is another example of how programming is a subjective art rather than "objective" science. Python's design is probably more appealing to beginners who intuitively regard 3 and 3.0 as interchangeable.

Type Checking & Input Validation¶

We use the built-in isinstance() function to make sure factorial() is called with an int object as the argument. We further validate the input by verifying that the integer is non-negative.

Meanwhile, we also see how we manually raise exceptions with the raise statement (cf., reference ), another way of controlling the flow of execution.

The first two branches in the revised factorial() function act as guardians ensuring that the code does not produce unexpected runtime errors: Errors may be expected when mentioned in the docstring.

So, in essence, we are doing two things here: Besides checking the type, we also enforce domain-specific (i.e., mathematical here) rules concerning the non-negativity of n.

In [35]:

def factorial(n):
    """Calculate the factorial of a number.

    Args:
        n (int): number to calculate the factorial for; must be positive

    Returns:
        factorial (int)

    Raises:
        TypeError: if n is not an integer
        ValueError: if n is negative
    """
    if not isinstance(n, int):
        raise TypeError("Factorial is only defined for integers")
    elif n < 0:
        raise ValueError("Factorial is not defined for negative integers")
    elif n == 0:
        return 1
    return n * factorial(n - 1)

The revised factorial() function works like the old one.

In [36]:

factorial(0)

Out[36]:

In [37]:

factorial(3)

Out[37]:

Instead of running into a situation of infinite recursion, we now receive specific error messages.

In [38]:

factorial(3.1)

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[38], line 1
----> 1 factorial(3.1)

Cell In[35], line 15, in factorial(n)
      2 """Calculate the factorial of a number.
      3 
      4 Args:
   (...)
     12     ValueError: if n is negative
     13 """
     14 if not isinstance(n, int):
---> 15     raise TypeError("Factorial is only defined for integers")
     16 elif n < 0:
     17     raise ValueError("Factorial is not defined for negative integers")

TypeError: Factorial is only defined for integers

In [39]:

factorial(-42)

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
Cell In[39], line 1
----> 1 factorial(-42)

Cell In[35], line 17, in factorial(n)
     15     raise TypeError("Factorial is only defined for integers")
     16 elif n < 0:
---> 17     raise ValueError("Factorial is not defined for negative integers")
     18 elif n == 0:
     19     return 1

ValueError: Factorial is not defined for negative integers

Forcing n to be an int is a very puritan way of handling the issues discussed above. So, we can not call factorial() with, for example, 3.0.

In [40]:

factorial(3.0)

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[40], line 1
----> 1 factorial(3.0)

Cell In[35], line 15, in factorial(n)
      2 """Calculate the factorial of a number.
      3 
      4 Args:
   (...)
     12     ValueError: if n is negative
     13 """
     14 if not isinstance(n, int):
---> 15     raise TypeError("Factorial is only defined for integers")
     16 elif n < 0:
     17     raise ValueError("Factorial is not defined for negative integers")

TypeError: Factorial is only defined for integers

Type Casting¶

A similar way to prevent an infinite recursion is to cast the type of the n argument with the built-in int() constructor.

In [41]:

def factorial(n):
    """Calculate the factorial of a number.

    Args:
        n (int): number to calculate the factorial for; must be positive

    Returns:
        factorial (int)

    Raises:
        TypeError: if n cannot be cast as an integer
        ValueError: if n is negative
    """
    n = int(n)
    if n < 0:
        raise ValueError("Factorial is not defined for negative integers")
    elif n == 0:
        return 1
    return n * factorial(n - 1)

The not so strict type casting implements duck typing for factorial() as, for example, 3.0 "walks" and "quacks" like a 3.

In [42]:

factorial(3)

Out[42]:

In [43]:

factorial(3.0)

Out[43]:

However, if we now call factorial() with a non-integer float object like 3.1, no error is raised. This is a potential source for semantic errors as the function runs for invalid input.

In [44]:

factorial(3.1)

Out[44]:

We could adjust the type casting logic such that a TypeError is raised for n arguments with non-zero decimals.

In [45]:

def factorial(n):
    """Calculate the factorial of a number.

    Args:
        n (int): number to calculate the factorial for; must be positive

    Returns:
        factorial (int)

    Raises:
        TypeError: if n cannot be cast as an integer
        ValueError: if n is negative
    """
    if n != int(n):
        raise TypeError("n is not integer-like; it has non-zero decimals")
    n = int(n)

    if n < 0:
        raise ValueError("Factorial is not defined for negative integers")
    elif n == 0:
        return 1
    return n * factorial(n - 1)

In [46]:

factorial(3.0)

Out[46]:

In [47]:

factorial(3.1)

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[47], line 1
----> 1 factorial(3.1)

Cell In[45], line 15, in factorial(n)
      2 """Calculate the factorial of a number.
      3 
      4 Args:
   (...)
     12     ValueError: if n is negative
     13 """
     14 if n != int(n):
---> 15     raise TypeError("n is not integer-like; it has non-zero decimals")
     16 n = int(n)
     18 if n < 0:

TypeError: n is not integer-like; it has non-zero decimals

However, using built-in constructors for type casting leads to another subtle inconsistency. As constructors are designed to take any object as their argument, they do not raise a TypeError when called with invalid input but a ValueError instead. So, if we, for example, called factorial() with "text" as the n argument, we see the ValueError raised by int() in a situation where a TypeError would be more appropriate.

In [48]:

factorial("text")

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
Cell In[48], line 1
----> 1 factorial("text")

Cell In[45], line 14, in factorial(n)
      1 def factorial(n):
      2     """Calculate the factorial of a number.
      3 
      4     Args:
   (...)
     12         ValueError: if n is negative
     13     """
---> 14     if n != int(n):
     15         raise TypeError("n is not integer-like; it has non-zero decimals")
     16     n = int(n)

ValueError: invalid literal for int() with base 10: 'text'

We could, of course, use a try statement to suppress the exceptions raised by int() and replace them with a custom TypeError. However, now the implementation as a whole is more about type checking than about the actual logic solving the problem. We took this example to the extreme on purpose. In practice, we rarely see such code!

In [49]:

def factorial(n):
    """Calculate the factorial of a number.

    Args:
        n (int): number to calculate the factorial for; must be positive

    Returns:
        factorial (int)

    Raises:
        TypeError: if n cannot be cast as an integer
        ValueError: if n is negative
    """
    try:
        casted_n = int(n)
    except ValueError:
        raise TypeError("n cannot be casted as an integer") from None
    else:
        if n != casted_n:
            raise TypeError("n is not integer-like; it has non-zero decimals")
        n = casted_n

    if n < 0:
        raise ValueError("Factorial is not defined for negative integers")
    elif n == 0:
        return 1
    return n * factorial(n - 1)

In [50]:

factorial("text")

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[50], line 1
----> 1 factorial("text")

Cell In[49], line 17, in factorial(n)
     15     casted_n = int(n)
     16 except ValueError:
---> 17     raise TypeError("n cannot be casted as an integer") from None
     18 else:
     19     if n != casted_n:

TypeError: n cannot be casted as an integer

In [51]:

factorial(3.1)

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[51], line 1
----> 1 factorial(3.1)

Cell In[49], line 20, in factorial(n)
     18 else:
     19     if n != casted_n:
---> 20         raise TypeError("n is not integer-like; it has non-zero decimals")
     21     n = casted_n
     23 if n < 0:

TypeError: n is not integer-like; it has non-zero decimals

Which way we choose for hardening the factorial() function depends on the concrete circumstances. If we are the main caller of the function ourselves, we may choose to not do any of the approaches at all. After all, we should be able to call our own function in the correct way. The lesson is that just because Python has no static typing, this does not mean that we cannot do this "manually." Yet, the idea behind a dynamically typed language is to not deal with the types too much at all.

Theory of Computation¶

With everything officially introduced so far, Python would be what is called Turing complete . That means that anything that could be formulated as an algorithm could be expressed with all the language features we have seen. Note that, in particular, we have not yet formally introduced the for and while statements!