Lesson 14: Function in Python: Recursive Function and Memoization

This lesson is the final part of the function study in Python, and the remaining topics from the Python function are discussed in this lesson.

✔ Level: Medium

Headlines

Lesson 14: Function in Python: Recursive Function and Memoization

recursive function
Function Attributes
Built-in Functions
Documentation Strings

recursive function

From Lesson 9 we are introduced to the for and while control commands, which were our only tools for repeating part of the code. We are now introduced to the implementation of new methods of repetition.

Simply put, a recursive function is a function that calls itself from inside its body. Implementing a recursive function is a method used to solve some problems, and we should know that recursive functions are not a specific syntax or command in Python, but a problem-solving method that uses a function in the Python programming language (e.g. Many other languages) can be implemented.

For example, in the example code below, we calculate the factorial value of five recursively:

>>> def factorial(n):
...     if n <= 1:
...         return 1
...     else:
...         return n * factorial(n - 1)
...
>>>

>>> factorial(5)
120
>>>

Generally, problems that can be solved from the sequence of doing the same task can be implemented recursively. The steps to execute the sample code above are as follows:

factorial(5)
|--> 5 * factorial(4)
         |--> 4 * factorial(3)
                  |--> 3 * factorial(2)
                           |--> 2 * factorial(1)
                                    |--> 1

120 = 5 * (4 * (3 * (2 * 1)))

Explanation: When factorial (5) is called (n == 5), the condition 1 => n is rejected and the else section is executed. In this step, another instance of the function with argument 4 is called and the factorial (5) execution waits for the end of the factorial (4) execution and receives the result. Similarly, several instances of a function are executed, waiting to receive the result from the next instance. Finally, the condition 1 => n is established and the factorial (1) instance returns its result to factorial (2). In the same way, the results are returned to reach the first executed instance, ie factorial (5), and the execution desired by the user is completed.

Sequence management of a function (recursive method) in memory is done using the Stack data structure [Wikipedia].
Each recursive function consists of two important parts:

• A phrase containing a self-calling function
• A condition for choosing between redial and end

Attention

Implementing a recursive method may seem exciting, but it should not be forgotten that it consumes a lot of memory, it will take time, it is often difficult to understand the execution process, and debugging will not be easy!

Use a decorator

When using decorator on recursive functions, note that this decorator will be applied to all called instances of the function, and that only one instance of the decorator is created, and all instance instances of the function are sent to the same instance:

>>> def logger(func):
...     print('Decorator is created!')
...     def func_wrapper(number):
...         print(f'New factorial call with parameter: 
{number}')
...         result = func(number)
...         print (f'factorial({number}) ==> {result}')
...         return result
...     return func_wrapper
...

>>> @logger
... def factorial(n):
...     if n <= 1:
...         return 1
...     else:
...         return n * factorial(n - 1)
...
>>>

>>> factorial(5)
Decorator is created!
New factorial call with parameter: 5
New factorial call with parameter: 4
New factorial call with parameter: 3
New factorial call with parameter: 2
New factorial call with parameter: 1
factorial(1) ==> 1
factorial(2) ==> 2
factorial(3) ==> 6
factorial(4) ==> 24
factorial(5) ==> 120
120
>>>

Be sure to pay attention to the sample output of the above code !.

Adjusting the recursive depth

In the Python programming language, there is an adjustable limit to the depth of implementation of recursive functions (the number of instances called from the function and in the stack). The getrecursionlimit () function of the sys module returns this value [Python Documents]. This value is 1000 by default, which can be changed using the setrecursionlimit (limit) function of the sys module [Python Documents]:

>>> import sys

>>> sys.getrecursionlimit()
1000

>>> sys.setrecursionlimit(50)

>>> sys.getrecursionlimit()
50

A RecursionError exception will be reported by exceeding the depth limit of the return functions:

>>> factorial(9)
362880

>>> sys.setrecursionlimit(10)

>>> factorial(9)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 5, in factorial
  File "<stdin>", line 5, in factorial
  File "<stdin>", line 5, in factorial
  [Previous line repeated 5 more times]
  File "<stdin>", line 2, in factorial
RecursionError: maximum recursion depth exceeded in 
comparison

tip

In addition to this limitation, there is another more serious limitation, and that is the amount of space provided by the operating system for the stack. By passing this amount of space, the program encounters a runtime error (RuntimeError).

Recursive Generator function

Implementing the Generator and Coroutine functions can also be considered a recursive method, in which case the results may be slightly contrary to your expectations. The following code sample receives a nested list object and prints each member in each list:

>>> def flatten(lists):
...     for sub in lists:
...         if isinstance(sub,list):
...             flatten(sub)
...         else:
...             print(sub)
...

>>> items = [[1,2,3],[4,5,[5,6]],[7,8,9]]

>>> flatten(items)
1
2
3
4
5
5
6
7
8
9
>>>

Now to convert the flatten function to a Generator, it is enough to use yield instead of print:

>>> def genflatten(lists):
...     for sub in lists:
...         if isinstance(sub,list):
...             genflatten(sub)
...         else:
...             yield sub
...

>>> items = [[1,2,3],[4,5,[5,6]],[7,8,9]]

>>> genflatten(items)
<generator object genflatten at 0x7eff06d40150>

>>> list(genflatten(items))
[]

Nothing happened! And the output is an empty list. Remember from the previous lesson, calling the genflatten function (which is actually a Generator function) only creates a Generator object, and we must also prepare for the output processing of a Generator object at the point where the function calls itself. Now with the above code modification:

>>> def genflatten(lists):
...     for sub in lists:
...         if isinstance(sub,list):
...             for item in genflatten(sub):
...                 yield item
...         else:
...             yield sub
...

>>> items = [[1,2,3],[4,5,[5,6]],[7,8,9]]

>>> genflatten(items)
<generator object genflatten at 0x7f6cee349258>

>>> list(genflatten(items))
[1, 2, 3, 4, 5, 5, 6, 7, 8, 9]

Memoization

Memoization is a technique for storing results to prevent duplication of calculations [Wikipedia]. This technique can be implemented in the Python programming language using a decorator.

To illustrate this point, let’s look at another recursive example. Calculate the Fibonacci value [Wikipedia] of a specific number:

>>> def fibonacci(n):
...     if n <= 1:
...         return n
...     else:
...         return fibonacci(n-1) + fibonacci(n-2)
...

>>> for number in range(10):
...    print(fibonacci(number))
...
0
1
1
2
3
5
8
13
21
34

In this example we did not go beyond the number 9 because the calculation for larger numbers like 50 will be really time consuming and this is an opportunity for us to test the efficiency of the Memoization technique. Now we optimize our Fibonacci return function using the Memoization technique and a Decorator:

>>> def memoize_fibonacci(func):
...     memory = {}
...     def func_wrapper(number):
...         if number not in memory:
...             memory[number] = func(number)
...         return memory[number]
...     return func_wrapper
...

>>> @memoize_fibonacci
... def fibonacci(n):
...     if n <= 1:
...         return n
...     else:
...         return fibonacci(n-1) + fibonacci(n-2)
...
>>>

Now calculate the value of 50 if not, the Fibonacci value for the number 500 ((500) Fibonacci). You will see the difference in runtime yourself!

 With the help of Decorator in this example (memoize_fibonacci), the results of calling each instance of the function are stored somewhere (memory dictionary object) and before retrying a new instance of the function, it is checked whether this value has already been calculated or not. If there is an answer, the function is ignored again and the pre-existing value is returned as a result. Therefore, it is obvious that the execution speed will increase by preventing the creation of samples of new functions and duplicate calculations.

Function Attributes

We have seen from previous lessons that objects in Python contain a set of default attributes depending on their type; For example, the __name__ attribute, which contains the function name [Python Documents].

In addition, functions in Python can also receive user-desired attributes, so that a series of additional information can be attached to the functions [PEP 232]. Note the example code below:

>>> def foo():
...     pass
...

>>> foo.is_done = True
>>>

>>> if foo.is_done:
...     print('DONE!')
...
DONE!
>>>

As can be seen, an Attribute can be added to the function using the following syntax:

function_name.attribute_name = attribute_value

You can also use the ready-made function setattr (object, name, value [Python Documents]) for this purpose. This function receives three arguments: the object to which you want to add an attribute (here the function), the name (of the string type) – string) and the desired Attribute value:

>>> setattr(foo, 'name', 'Saeid')

>>> setattr(foo, 'age', 32)
>>>

>>> foo.name
'Saeid'

>>> foo.age
32

These attributes are stored in a dictionary object that are accessible using the __dict__ attribute [Python Documents]:

>>> foo.__dict__
{'is_done': True, 'name': 'Saeid', 'age': 32}

To get the value of a specific attribute you can also use the ready-made function getattr object, name [, default] [Python Documents]. This function has two mandatory parameters (object and name) and an optional parameter (default). The object (function here) does not have the desired attribute, the default value (if sent) will be returned:

>>> getattr(foo, 'is_done')
True

>>> getattr(foo, 'is_publish', False)
False

>>> getattr(foo, 'is_publish')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'function' object has no attribute 
'is_publish'

>>> foo.is_publish
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'function' object has no attribute 
'is_publish'

An AttributeError exception will be reported if you try to get an attribute that is not defined for the function. Of course, as mentioned, this will not happen if you use the getattr function and set the default parameter. To prevent this exception, you can also check the existence of an attribute using the hasattr (object, name) function before using it [Python Documents]:

>>> if hasattr(foo, 'is_publish'):
...     print(foo.is_publish)
... else:
...     print(f"{foo.__name__!r} has no attribute 
'is_publish'")
...
'foo' has no attribute 'is_publish'
>>>

You can also use the delattr (object, name) function to delete an attribute [Python Documents]:

>>> delattr(foo, 'age')
>>>

>>> foo.age
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'function' object has no attribute 'age'

Or from the del command

>>> del foo.is_done
>>>

>>> foo.is_done
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'function' object has no attribute 
'is_done'
>>>

Attention

At the end of this section, it should be noted that when defining an attribute for its functions and using a decorator, as described in the previous lesson, do not forget to use @ functools.wraps [Lesson 13].

Built-in Functions

The Python interpreter provides programmers with a number of functional functions without the need to import a specific module. These functions are called Built-in Functions. A complete list of these functions is available in the Python documentation with descriptions. You have become familiar with some of them during the previous lessons and even this lesson, in this section we will examine some other cases.

eval

This function returns one (and only one) Python expression in the form of a string object to receive, execute, and return [Python documents].

>>> eval('3*4 + 7.2')
19.2

>>> import math

>>> x = 2

>>> eval('math.sin(3.5+x) + 7.2')
6.494459674429608

According to the definition in the Python documents eval object [, globals], local, this function also includes two parameters, globals and locals, to which arguments are optional. Both are of the dictionary type, which is Scope or The global and local domains provide the code to be executed (function parameter 1):

>>> globals_env = {'x': 7, 'y': 10, 'birds': ['Parrot', 
'Swallow', 'Albatross']}

>>> locals_env = {}

>>> a = eval("3 * x + 4 * y", globals_env, locals_env)

>>> a
61

exec

This function is the same as eval, except that it can receive and execute multiple Python statements or commands in a single string object. Exec output is always None [Python documents].

>>> exec('import math; x=2; print
(math.sin(3.5+x) + 7.2)')
6.494459674429608

>>> exec("for i in range(5): print(i)")
0
1
2
3
4

Attention

exec in Python version 2x is not defined as a function and is used as a command [Python Documents]:

>>> exec 'import math; x=2; print
(math.sin(3.5+x) + 7.2)'
6.49445967443

This function, like eval, includes two parameters, globals and locals:

exec(object[, globals[, locals]])

>>> exec("for b in birds: print(b)", 
globals_env, locals_env)
Parrot
Swallow
Albatross

Of course, in 2x versions, the syntax exec code [in globals], locals is followed:

>>> exec "for b in birds: print b" in globals_env, 
locals_env
Parrot
Swallow
Albatross

compile

Each time a string object containing Python code is passed to the eval and exec functions, the Python interpreter first compiles the code into the bytecode and then executes it, repeating this overload. This overhead can be avoided once the computer is reused.

The compile function is for this purpose [Python Documents]. The definition of this function is as follows:

compile(source, filename, mode, flags=0, 
dont_inherit=False, 
optimize=-1)

• source: is the code that we want to computerize and eventually execute, which can be an object of type str (str), bytes (bytes) or AST [Python documents].
• filename: The name of the file from which the code should be read; If the code you want is not read from the file, put a name of your choice or set it to a blank string.
• mode: Specifies the type of code. It can be one of the exec, eval or single values. We examined the execution conditions of the two functions eval (containing only one expression) and exec (one or more expressions and commands), and single is also used when the code in question contains only one command.
• flags, dont_inheritmode: These two parameters are optional and you can skip them at this point. The two are used to determine which of the Future statements is effective in compiling the code [Python Documents].
• optimize: Adjusts the level of code optimization for the compiler, and sending arrogant to it is also optional – Further reading: [PEP 488].

Note the sample codes below:

>>> # compile() with string source

>>> code_str = 'x=5\ny=10\nprint("sum =",x+y)'

>>> code = compile(code_str, 'sum_test.py', 'exec')

>>> print(type(code))
<class 'code'>

>>> exec(code)
sum = 15

1
2
3
4
5
6

# File Name: test_code.py
# Directory: /home/saeid/Desktop

x = 10
y = 20
print('Multiplication = ', x * y)

>>> # reading code from a file

>>> file = open('/home/saeid/Desktop/test_code.py', 'r')

>>> code_str = file.read()

>>> file.close()

>>> code = compile(code_str, 'test_code.py', 'exec')

>>> print(type(code))
<class 'code'>

>>> exec(code)
Multiplication =  200

locals, globals

The output of both functions is a dictionary object (dict). The locals () function returns a dictionary containing variables in the local [Python documents] domain, and the globals () function returns a dictionary containing variables in the global [Python documents]:

>>> a = 0

>>> def func():
...     x = 'text'
...     print('-' * 10)
...     print('locals():')
...     print(locals())
...     print('-' * 10)
...     print('globals():')
...     print(globals())
...

>>> func()
----------
locals():
{'x': 'text'}
----------
globals():
{'__name__': '__main__', '__doc__': None, 
'__package__': 
None, '__loader__'
: <class '_frozen_importlib.BuiltinImporter'>, 
'__spec__': 
None, '__annotations__': {}, '__builtins__': 
<module 'builtins' (built-in)>, 'a': 0, 'func': 
<function func at 0x7f2b29f1ec80>}
>>>

Note that at the output module level these two functions are identical:

>>> a = 5

>>> b = 10

>>> def func():
...     pass
...

>>> locals()
{'__name__': '__main__', '__doc__': None, '__package__': 
None, '__loader__': 
<class '_frozen_importlib.BuiltinImporter'>, 
'__spec__': None, '__annotations__': {}, '__builtins__': 
<module 'builtins' (built-in)>, 'a': 5, 'b': 10, 'func': 
<function func at 0x7f1dd0218c80>}

>>> globals()
{'__name__': '__main__', '__doc__': None, '__package__': 
None, '__loader__': 
<class '_frozen_importlib.BuiltinImporter'>, '__spec__': 
None, '__annotations__': {}, '__builtins__': 
<module 'builtins' (built-in)>, 'a': 5, 'b': 10, 'func': 
<function func at 0x7f1dd0218c80>}
>>>

consideration

As stated in Lessons 3 and 4, the entire Python interactive environment is like a module (or script) to the Python interpreter.

Documentation Strings

From the sixth lesson we are familiar with docstring; In this section, we address this issue with a function approach [PEP 257].

tip

Using docstring at the beginning of modules, classes, and functions is a good way in Python to show how these elements relate to and behave.

Note the example code below:

>>> def factorial(n):
...     """Computes n factorial. For example:
...
...     >>> factorial(5)
...     120
...     >>>
...     """
...
...     if n <= 1: return 1
...     else: return n*factorial(n-1)
...
>>>

>>> factorial.__doc__
'Computes n factorial. For example:\n\n 
   
>>> factorial(5)\n    120\n    >>>\n    '

>>> print(factorial.__doc__)
Computes n factorial. For example:

    >>> factorial(5)
    120
    >>>
>>>

>>> help(factorial)

Help on function factorial in module __main__:

factorial(n)
    Computes n factorial. For example:

    >>> factorial(5)
    120
    >>>
(END)

The value of docstring is placed in the attribute __doc__ of the function. This value is also available through the help function in the Python interactive environment.

IDE programs, such as PyCharm, also process docstrings and use the information in them to provide more help to the programmer. For example, the input type of a function or its output value can be described using docstring. For more information and to view sample code you can refer to the PyCharm documentation: PyCharm – Document source code

😊 I hope it was useful