Python, Theory

Python. Recursion. Examples of tasks solving




Recursion in Python. Examples of tasks solving

Contents

Search other websites:

1. The concept of recursion. Recursive functions

Recursion is a way to organize a looping process by calling a recursive function. A recursive function is a function that contains code to call itself to organize a looping process. With the help of recursive functions, you can solve some tasks with a minimum amount of code, bypassing the use (declaration) of unnecessary data structures. Recursion can be seen as an alternative to loops and iterations.

  ⇑

2. Examples of solving tasks with recursion
2.1. Function CalcSumNumbers(). Calculate the sum of the elements of a set of numbers

The example implements the recursive function CalcSumNumbers(), which sums the numbers in the input list. In the operation of the function, the incoming list A is divided into 2 parts:

  • the first item of the list A[0];
  • all other elements of the list except the first. These elements are highlighted using the slice A[1:]. By taking the first item out of the list using a slice, you can pass this newly created list to the next recursive function call.
# Recursive function - returns the sum of the numbers in the input set
def CalcSumNumbers(A):
    if A == []:
        # if set is empty, return 0
        return 0
    else:
        # Calculate the sum - add first item of the set
        summ = CalcSumNumbers(A[1:]) # recursive call of the same function

        # Add the first item to the sum
        summ = summ + A[0]

        return summ

# Demonstration of using the CalcSumNumbers() function
# 1. Create a set of numbers
L = [ 2, 3, 8, 11, 4, 6 ]

# 2. Invoke function
summ = CalcSumNumbers(L)

# 3. Print the sum
print("summ = ", summ)

The result of the program

summ = 34

  ⇑

2.2. Function CalcSumNegativeNumbers(). Calculate the number of negative numbers in a set

According to the previous example (p. 4.1), the CalcSumNegativeNumbers() function is implemented, which calculates the number of negative numbers in a list (set). Again, the first element and all other elements are selected from the input list.

# Recursive function - returns the number of negative numbers in a list
def CalcSumNegativeNumbers(A):
    if A == []:
        # if set is empty, return 0
        return 0
    else:
        # Calculate the count, go to further processing
        # without first item
        count = CalcSumNegativeNumbers(A[1:]) # recursive call of the same function

        # Increase by 1, provided that the current number is negative
        if A[0]<0:
            count = count + 1

        return count

# Demonstration of using the CalcSumNumbers() function
# 1. Create a set of numbers
L = [ -2, 3, 8, -11, -4, 6 ]

# 2. Call the function
n = CalcSumNegativeNumbers(L)

# 3. Print the sum
print("n = ", n)

Program result

n = 3

  ⇑

2.3. Function CalcSumNumbers(). Calculating the sum of numbers with support for nested lists

If you want the recursive function to process nested lists, then in the body of the function you need to implement a loop for traversing the list items. Then this element needs to be checked if it is a list by pattern

if not isinstance(t, list):
    ...

here t is the element that is checked using the isinstance() function.

# Recursive function - returns the sum of numbers, processes nested lists
def CalcSumNumbers(A):
    summ = 0

    # here you need to implement a traversal in a loop
    for t in A:
        # The item t is processed
        if not isinstance(t, list): # check if t is a list
            summ = summ + t # if t is not a list, then add it to the sum
        else:
            # get sum from following recursive calls
            summ = summ + CalcSumNumbers(t)
    return summ

# Demonstration of using the CalcSumNumbers() function
# 1. Create a set of numbers
L = [ -2, 3, 8, 11, [-4, 6, [ 2, [-5, 4] ] ] ]

# 2. Call the function
summ = CalcSumNumbers(L)

# 3. Print the sum
print("summ = ", summ)

The result of the program

summ = 23

  ⇑

2.4. Function GetFibonacciList(). Get the Fibonacci series

The Fibonacci series contains numbers in which the following number is defined as the sum of the two previous numbers:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...

The following recursive function generates a Fibonacci series in the form of a list for a given maximum value in the list.

# Recursive function - returns the Fibonacci series as a list.
# Parameter n is the maximum value in the list.
def GetFibonacciList(n, L):
    # Check if the length of the list is correct
    count = len(L)
    if len(L)<2:
        return []

    # Get last numbers in list L
    num1 = L[count-2]
    num2 = L[count-1]

    # The formula for calculating the next number
    if (num1+num2) < n:
        L = L + [num1+num2]
        return GetFibonacciList(n, L) # invoke the recursive function
    else:
        return L # if the end is reached, then the usual exit

# Invoke the GetFibonacciList() function
LL = GetFibonacciList(100, [0, 1])
print("LL = ", LL)

The result of the program

LL = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]

  ⇑

2.5. Function ReverseNumber(). Reversing the number

The example shows the ReverseNumber() function of representing a number in reverse order. For example, for the number 12345, the result is 54321.

The function receives an integer number as an input parameter. The function returns an integer reversed number.

# Recursion. Reversing the number

import math

# Recursive function
def ReverseNumber(num):
    # 1. Checking, is the number correct
    if num<0:
        return -1

    # 2. Checking, is the number 0
    if num==0:
        return 0

    # 3. If the number is correct (num>0), then process it
    # 3.1. Determine the order of a number (the number of digits in a number)
    n_digit = 0 # order of number
    num2 = num  # the copy of num

    while num2>0:
        n_digit = n_digit+1
        num2 = num2//10

    # 3.2. Get the last digit from number
    t = num%10 # 123456 => 6

    # 3.3. Multiply the last digit by 10^n_digit
    res = t * int(math.pow(10, n_digit-1))

    # 3.4. Return sum with recursive function call
    return res + ReverseNumber(num//10)

# Demonstration of using the function
num = 1234000567
rnum = ReverseNumber(num) # rnum =   7650004321
print("rnum = ", rnum)

The result of the program

rnum = 7650004321

  ⇑

2.6. Function Power(x, y). Raising the number x to the power of y

The recursive function Power(x, y) returns the result of raising a real number x to an integer power of y. It is preliminarily assumed that the value of y>0.

# Recursion. Raising the number x to the power of y

# Recursively function
def Power(x, y):
    if y>0:
        return x * Power(x, y-1)
    else:
        return 1

# Demonstration of using the Power() function
x = 3
y = 4
res = Power(x, y)
print("res = ", res)

The result of the program

res = 16

  ⇑

2.7. Function GetMaxList(). Determining the maximum list item

The example implements the GetMaxList() function, which calculates the maximum item in the list. The whole work of the function is divided into 2 parts:

  • performing actions if there are two or more numbers in the list;
  • performing actions if the list ends, that is, the last element is considered.

Each recursive function call treats the list as two parts:

  • the first element of the list (element with index 0);
  • the elements following the first in the list (elements with indices 1, 2, etc.).

 

# Recursive function. Determine the maximum list item
def GetMaxList(L):
    if len(L)>1:
        # Get the most out of the following recursive calls
        Max = GetMaxList(L[1:])

        # Compare maximum with the first element of the list
        if L[0]<Max:
            return Max
        else:
            return L[0]

    if len(L)==1: # the last item in the list
        return L[0] # return this item

# Demonstration of using the Power() function
L = [ 500, 2300, 800, 114, 36]
res = GetMaxList(L)
print("res = ", res)

The result of the program

res = 2300

  ⇑

2.8. Function Convert_10_to_2(). Converting number from decimal to binary

In this example, for the purpose of comparison, 2 functions are implemented that convert an integer from the decimal number system to its analogue in the binary number system:

  • Convert_10_to_2_R() – it is a recursive number conversion function;
  • Convert_10_to_2() – not recursive function.

To ensure the solution of the problem, in the non-recursive version of Convert_10_to_2(), an additional variable k is introduced, which determines the order of the resulting binary number. In order to preserve this order of k in the recursive version of the Convert_10_to_2_R() function, you need to pass it to this function as the second parameter.

 

import math

# Recursive function. Converting a number from the 10th number system to binary.
# The function returns the result as a number: 13 => 1101.
# Parameters:
# - n - the number in the decimal system;
# - k - the current order (number of digits) of the number in the binary system.
def Convert_10_to_2_R(n, k):
    if n>0:
        t = n%2
        return Convert_10_to_2_R(n//2, k+1) + int(t*math.pow(10,k))
    else:
        return 0

# Non recursive convertion function
def Convert_10_to_2(n):
    summ = 0 # the sum of numbers: 5 => 100 + 0 + 1 => 101
    k = 0 # the order of number in the binary system

    while n>0:
        t = n%2
        summ = summ + int(t*math.pow(10,k))
        k = k+1
        n = n//2

    return summ

# Demonstration of using functions
res1 = Convert_10_to_2_R(126, 0) # Invoke the recursive function
res2 = Convert_10_to_2(126) # Invoke the non-recursive function
print("res1 = " , res1)
print("res2 = " , res2)

The result of the program

res1 = 1111110
res2 = 1111110

  ⇑

Related topics

  ⇑