Python Code: Recursive function

Python A recursive function is a method of defining a function in which the function directly or indirectly calls itself.

When describing a recursive function, it is always necessary to ensure that for all valid argument values, the recursive function call will terminate, meaning that the recursion will be finite.

The number of nested function calls is called the depth of recursion. Let's describe the standard algorithm for describing a recursive function. A structurally recursive function at the top level is always a branching structure, consisting of two or more alternatives, of which:

• at least one is terminal (recursion termination);

• at least one is recursive (i.e., it calls itself with other arguments).

For example, let's describe a recursive subroutine for computing Fibonacci numbers. In the program, we will denote this function as Fib(n).

# def recursive_func(args):
#     if terminal_case:           # Terminal branch
#         ...
#         return trivial_value    # Trivial value
#   else:                         # Recursive branch
#     ...
#                                 # Function call with different arguments
#     return expr(recursive_func(new_args))


def Fib(n):
    if n == 0 or n == 1: 
        return 1 
    else: 
        return Fib(n - 1) + Fib(n - 2) 

n = int(input("n = "))
print("Fib(%d) = %d" % (n, Fib(n)))

				

Python Code:

Constant time execution means that the execution time of the program does not depend on the size of the input data. For example, accessing an element of a list by index has constant time execution because this time does not change with the increase in the size of the list.

Logarithmic time execution means that the execution time of the program grows logarithmically with the increase in the size of the input data. For example, binary search in a sorted list has logarithmic time execution.

Linear time execution means that the execution time of the program grows linearly with the increase in the size of the input data. For example, iterating through all elements in a list has linear time execution.

Polynomial time execution means that the execution time of the program grows as a polynomial function of the size of the input data. For example, sorting a list using the merge sort algorithm has polynomial time execution.

Exponential time execution means that the execution time of the program grows as an exponential function of the size of the input data. For example, a recursive algorithm for computing Fibonacci numbers has exponential time execution.

The average program execution time is the expected time for the program to complete, assuming a uniform distribution of input data or actions. It can be calculated by averaging the execution time of the program for various possible input data or execution scenarios.

Let's find the number of operations of the algorithm that computes the sum of components of a given vector of size 𝑛: 𝑎 = (𝑎1,… , 𝑎𝑛).

def sum_vector(a, n):
    result = a[0]
    i = 1
    while i < n:
        result += a[i]
        i+=1
    return result