© The Author(s), under exclusive license to APress Media, LLC, part of Springer Nature 2022
M. IndenPython Challengeshttps://doi.org/10.1007/978-1-4842-7398-2_3

3. Recursion

Michael Inden1  
(1)
Zurich, Switzerland
 

In nature and mathematics, you can find the topic self-similarity or recurring structures, such as snowflakes, fractals, and Julia sets, which are interesting graphical formations. In this context, one speaks of recursion, meaning that things repeat or resemble each other. Related to methods, this means that they call themselves. Important therefore is a termination condition in the form of special input values, which leads to the end of the self calls.

3.1 Introduction

Various computations can be described as recursive functions. The goal is to break down a more complex task into several simpler subtasks.

3.1.1 Mathematical Examples

Below you will take a look at the computation of the factorial, summation, and Fibonacci numbers, three introductory examples for recursive definitions.

Example 1: Factorial

Mathematically, the factorial for a positive number n is defined as the product (i. e., the multiplication) of all natural numbers from 1 to n, inclusive. For notation, the exclamation mark is placed after the corresponding number. For example, 5! stands for the factorial of the number 5:

5! = 5 ∗ 4 ∗ 3 ∗ 2 ∗ 1 = 120

This can be generalized as follows:

n! = n ∗ (n − 1) ∗ (n − 2) ∗ ... ∗ 2 ∗ 1

Based on this, the recursive definition is derived:
$$ n!=left{{}_{n.left(n-1 ight)!,kern0.37em forall n>1}^{1,kern3.359999em n=0,n=1} ight. $$

Here, the inverted »A« (∀) denotes for all.

For the first n, you get the following value progression:

n

1

2

3

4

5

6

7

8

n!

1

2

6

24

120

720

5040

40320

Calculation of the factorial in Python Let’s take a quick look at how the recursive calculation formula of the factorial can be transferred into a function of the same kind:
def factorial(n):
    if n < 0:
        raise ValueError("n must be >= 0")
    # recursive termination
    if n == 0 or n == 1:
        return 1
    # recursive descent
    return n * factorial(n - 1)
Figure 3-1 clarifies what this recursive definition generates in terms of calls.
Figure 3-1

Recursive calls to factorial(5)

Python shortcut To demonstrate that Python can be used to write compact source code, I will repeatedly show which shortcuts exist in the following sections. In this case, you can write the calculation in the form of a lambda as a one-liner. The brevity often offers some disadvantages: Here there is no handling of wrong inputs and the whole thing is a little bit less readable. All in all, the distinction between recursive termination and descent is more challenging to recognize. In addition, the mathematical formula is not so clearly evident:
factorial = lambda n: n if n == 1 else n * factorial(n - 1)

Please note that lambdas usually encapsulate only a tiny piece of functionality and thus you should not name them and assign them to a variable. In this book, I sometimes break this PEP-8 rule for a better insight into how things work or to express more clearly what was intended.

There are almost always many ways to Rome and the solution. As a variant, I present the function reduce() from the module functools, which requires an import as shown below. However, no recursion is used and the readability decreases, which can be compensated by a meaningful function name.
import functools
def factorial(n):
    return functools.reduce(lambda n_1, n: n_1 * n, range(1, n + 1))

Example 2: Calculation of the Sum of Numbers Up to n

Mathematically, the sum for a number n is defined as the addition of all natural numbers from 1 ascending up to and including n:
$$ sum limits_1^ni=n+n-1+n-2+dots +2+1 $$
This can be defined recursively as follows:
$$ sum limits_1^ni=left{{}_{n+{sum}_1^{n-1};i,forall n&gt;1}^{1,kern3.239999em n=1} ight. $$
For the first n, you get the following value progression:

n

1

2

3

4

5

6

7

8

sum_of(n)

1

3

6

10

15

21

28

36

Calculation of the sum in Python Again, you convert the recursive calculation formula of the summation into a recursive function:
def sum_of(n):
    if n <= 0:
        raise ValueError("n must be >= 1")
    # recursive termination
    if n == 1:
        return 1
    # recursive descent
    return n + sum_of(n - 1)
Python shortcut For the calculation of sums it is possible to use a lambda, but again without error handling and a bit less readable:
sum_of = lambda n: n if n == 1 else n + sum_of(n - 1)
Likewise, the function reduce() from the module functools can be used, with the disadvantages and possibilities hinted at earlier to compensate:
import functools
def sum_of_with_reduce(n):
    return functools.reduce(lambda n_1, n: n_1 + n, range(1, n + 1))
Optimized calculation of the sum Please keep in mind that the algorithms presented here only served to illustrate the recursive nature or the functionalities from the Python standard library. However, because there is a formula for calculating the sum of the numbers from 1 to n that determines the whole thing performance-optimally in O(1), you should not use the previous variants in practice:
$$ sum limits_1^ni=frac{{left(n+1 ight)}^{ast};n}{2} $$

Example 3: Fibonacci Numbers

Fibonacci numbers are also excellent for recursive definitions, although the formula is already a tiny bit more complex:
$$ fib(n)=left{egin{array}{c}1,kern6.119996em n=1\ {}1,kern5.999996em n=2\ {} fibleft(n-1 ight)+ fibleft(n-2 ight),forall n&gt;2end{array} ight. $$
For the first n, you get the following value progression:

n

1

2

3

4

5

6

7

8

fib(n)

1

1

2

3

5

8

13

21

If the calculation formula is visualized graphically, it quickly becomes obvious how wide the tree of self calls potentially spans. For larger n, the call tree would be much more expansive, as indicated by the dashed arrows (see Figure 3-2). Even with this exemplary invocation, it is evident that various calls are made several times, for example for fib(n − 4) and fib(n − 2), but especially three times for fib(n − 3). This very quickly leads to costly and tedious computations. You will learn how to optimize this later in section 7.1.
Figure 3-2

Fibonacci recursive

HINT: DIFFERENT DEFINITION WITH ZERO AS THE START VALUE

It should furthermore be noted that there is a variation that starts at the value of 0. Then fib(0) = 0 and fib (1) = 1 are the base values and afterwards you get fib (n) = fib(n − 1) + fib(n − 2) according to the recursive definition. This produces the same sequence of numbers as the definition above, only with the value for 0 added.

ATTENTION: RESTRICTED CALL DEPTH

Keep in mind that self calls happen again and again for summing up and computing the Fibonacci numbers. That’s why you can only pass inputs around 990 here. Larger values will result in a RecursionError: maximum recursion depth exceeded. For other recursive functions, there are similar restrictions on the number of self calls. Other programming languages like Java allow significantly more self calls. In Java, over 10,000 self calls are easily possible.

There are several variants in recursion. An advantageous one is called tail-recursive. This is characterized by the fact that the recursive call is the last action in the calculation. Such functions can be processed without the otherwise usual storing of intermediate results on a stack.

3.1.2 Algorithmic Examples

In the introduction, you looked at mathematical examples. But recursion is also very well suited for algorithmic tasks. For example, it is possible to check for an array or list whether the values stored form a palindrome. A palindrome is a word that reads the same from the front and the back, such as OTTO or ABBA. Here it is meant that the elements match pairwise from the front and the back. This applies, for example, to a list with the following values: { 1, 2, 3, 2, 1 }.

Example 1: Palindrome—Recursive Variant

You can easily test for a palindrome property recursively. Let’s look at this as a program after I have briefly described the algorithm.

Algorithm If the array or list has the length 0 or 1, then it is a palindrome by definition. If the length is two and greater, you must check the outer left and outer right elements for a match. After that, a copy of the array or the list is created, shortened by one position at the front and one at the back. Further checking is then performed on the remaining part of the array or the list, as shown in the following code:
def is_palindrome_simple_recursive(values):
    # recursive termination
    if len(values) <= 1:
        return True
    left = 0
    right = len(values) - 1
    if values[left] == values[right]:
        # attention: end is exclusive
        remainder = values[left + 1 : right]
        # recursive descent
        return is_palindrome_simple_recursive(remainder)
    return False

However, the described and implemented approach leads to many copies and extractions of subarrays or sublists. It is affordable to avoid this effort by keeping the idea but modifying the algorithm minimally by using a trick.

Optimized algorithm Rather than using a copy, you still use the original data structure. You include two position markers left and right, which initially span the entire array or list. Now you check if the left and right values referenced by these positions match. If this is the case, the position markers are moved inward by one position on both sides, and the whole procedure is called recursively. This is repeated until the left position pointer reaches or skips the right one.

The implementation changes as follows:
def is_palindrome_recursive_optimized(values):
    return is_palindrome_recursive_in_range(values, 0, len(values) - 1)
def is_palindrome_recursive_in_range(values, left, right):
    # recursive termination
    if left >= right:
        return True
    if values[left] == values[right]:
        # recursive descent
        return is_palindrome_recursive_in_range(values, left + 1, right - 1)
    return False

Perhaps you wonder why I don’t write the process more compactly and even use less return statements. My main concern in presenting algorithms is comprehensibility. Multiple returns are really only a problem if a function is very long and confusing.

HINT: AUXILIARY functions FOR FACILITATING RECURSION

The idea of position pointers in arrays, lists, or strings is a common tool used in solutions to recursion for optimization and avoidance of, say, array copying. To prevent the whole thing becoming inconvenient for callers, it is a good idea to have a high-level function calling a helper function that has additional parameters. This allows you to include certain information in the recursive descent. In this example, these are the left and right limits, so that potentially costly copying can be eliminated. Many subsequent examples will take advantage of the general idea.

Example 1: Palindrome—Iterative Variant

Although a recursive definition of an algorithm is sometimes quite elegant, the recursive descent produces self calls. This potentially creates quite a bit of overhead. Conveniently, any recursive algorithm can be converted into an iterative one. Let’s look at this for the palindrome calculation. You use two position pointers for the iterative conversion—instead of the recursive descent, you use a while loop. This terminates when all elements have been checked or if a mismatch has been detected before.
def is_palindrome_iterative(values):
    left = 0
    right = len(values) - 1
    same_value = True
    while left < right and same_value:
        same_value = values[left] == values[right]
        left += 1
        right -= 1
    return same_value
Again, a note on compactness: This function could be written as follows, omitting the auxiliary variable:
def is_palindrome_iterative_compact(values):
    left = 0
    right = len(values) - 1
    while left < right and values[left] == values[right]:
        left += 1
        right -= 1
    # left >= right or values[left] != values[right]
    return left >= right

The return value is determined by the condition implied by the comment, if left >= right holds, then values is not a palindrome. With this variant, however, you have to think much more about the return. Again, I prefer understandability and maintainability over brevity or performance.

Python shortcut Of course, the whole thing can be achieved much more easily by calling the built-in functionality [::-1]. This produces a string or list (or even an array) with the letters or elements in reverse order. I discuss this feature of Python called slicing later in Chapters 4 and 5. Let’s return to the exercise of checking the palindrome property of a list, which can be written exceptionally compactly with slicing:
def is_palindrome_shorter(values):
    return values == values[::-1]

Also, consider for this variant that in the presumably rare case of enormous amounts of data, an inverse variant of the original list is generated here. Thus, the memory is required twice.

Example 2: Fractal Generation

As mentioned in the beginning, recursion allows you to create graphics as well. In the following, a graphically simple variant is displayed, which is based on the subdivisions of a ruler:
-
==
-
===
-
==
-
This can be implemented with a two times recursive descent as follows:
def fractal_generator(n):
    if n < 1:
        return
    if n == 1:
        print("-")
    else:
        fractal_generator(n - 1)
        print("=" * n)
        fractal_generator(n - 1)
If you use more complex drawing functions instead of ASCII characters, you can use recursion to create exciting and appealing shapes, for example the snowflake in Figure 3-3.
Figure 3-3

Recursive graphic with draw_snowflake( )

This stylized representation of a snowflake can be implemented as follows:
import turtle
def draw_snowflake(turtle, length, depth):
    # recursive termination
    if depth == 0:
        return
    for _ in range(6):
        turtle.right(60)
        turtle.forward(length)
        # recursive descent
        draw_snowflake(turtle, length // 3, depth - 1)
        turtle.back(length)
screen = turtle.Screen()
turtle.speed(10)
draw_snowflake(turtle, 240, 5)
screen.exitonclick()

3.1.3 Steps When Multiplying the Digits of a Number

To conclude the algorithmic examples, I would like to clarify the individual steps and self calls once more. As an artificial example, use the multiplication of the digits of a number, also called cross product, for example for the value 257 ⇒ 2 ∗ 5 ∗ 7 = 10 ∗ 7 = 70. Using modulo, the extraction of the individual digits and their multiplication can be implemented quite simply as follows:
def multiply_all_digits(value):
    remainder = value // 10
    digit_value = value % 10
    print("multiply_all_digits: %-10d | remainder: %d, digit: %d" %
          (value, remainder, digit_value))
    if remainder > 0:
        result = multiply_all_digits(remainder)
        print("-> %d * %d = %d" % (digit_value, result, digit_value * result))
        return digit_value * result
    else:
        print("-> " + str(value))
        return value
Let’s look at the outputs for the two numbers 1234 and 257:
>>> multiply_all_digits(1234)
multiply_all_digits: 1234       | remainder: 123, digit: 4
multiply_all_digits: 123        | remainder: 12, digit: 3
multiply_all_digits: 12         | remainder: 1, digit: 2
multiply_all_digits: 1          | remainder: 0, digit: 1
-> 1
-> 2 * 1 = 2
-> 3 * 2 = 6
-> 4 * 6 = 24
24
>>> multiply_all_digits(257)
multiply_all_digits: 257        | remainder: 25, digit: 7
multiply_all_digits: 25         | remainder: 2, digit: 5
multiply_all_digits: 2          | remainder: 0, digit: 2
-> 2
-> 5 * 2 = 10
-> 7 * 10 = 70
70

It is clearly visible how the recursive calls happen with a continuously shorter sequence of numbers. Finally, the result is constructed or calculated based on the last digit in the other direction.

Python shortcut Again, the whole thing can be accomplished much more easily by calling the functionality reduce() from module functools Still, the point here is to get acquainted with the recursive description of multiplying the digits of a number:
import functools
def multiply_all_digits_shorter(value):
    return functools.reduce(lambda x, y: int(x) * int(y), str(value))

3.1.4 Typical Problems: Endless Calls and RecursionError

Recursion often allows problems to be expressed and implemented in an understandable way. A detail worth knowing is that the self calls lead to them being stored temporarily on the stack. For each function call, a so-called stack frame containing information about the called function and its parameters is stored on the stack. The stack is, however, limited in its size. Thus only a finite number of nested function calls can take place—usually around 990. This was already discussed briefly in a practical tip.

A huge number of recursive calls can result in a RecursionError : maximum recursion depth exceeded. Sometimes the problem occurs because there is no termination condition in the recursion or the condition is formulated incorrectly.
# attention: deliberately wrong for demonstration
def infinite_recursion(value):
    infinite_recursion(value)
def factorial_no_abortion(number):
    return number * factorial_no_abortion(number - 1)
Sometimes the call is also just wrong, simply because no decreased value is passed:
# attention: deliberately wrong for demonstration
def factorial_wrong_call(n):
    if n == 0 or n == 1:
        return 1
    return n * factorial_wrong_call(n)

You may still recognize a direct endless self call fairly well. But this becomes more difficult with an increasing number of lines. With some experience and practice in recursion, even the missing termination condition in the function factorial_no_abortion() may still be quite recognizable. But, in the function factorial_wrong_call() this is not that easy to determine. Here you must know more accurately what was intended.

You should take away two things from the examples:
  1. 1.

    Termination condition: A recursive function must always include at least one termination condition. But even if defined correctly, it is possible that, for example, the disallowed negative value range is not checked. For factorial(n) a call with a negative value would then lead to a RecursionError.

     
  2. 2.

    Complexity reduction : A recursive function must always subdivide the original problem into one or more smaller subproblems. Sometimes, this is already accomplished by reducing the value of a parameter by 1.

     

3.2 Exercises

3.2.1 Exercise 1: Fibonacci (★★✩✩✩)

Exercise 1a: Fibonacci Recursive (★✩✩✩✩)

Write function fib_rec(n) that recursively computes Fibonacci numbers based on the following definition:
$$ fib(n)=left{egin{array}{c}1,kern6.119996em n=1\ {}1,kern5.999996em n=2\ {} fibleft(n-1 ight)+ fibleft(n-2 ight),forall n&gt;2end{array} ight. $$

Example

For example, check the implementation with the following value progression:

Input

1

2

3

4

5

6

7

8

fib(n)

1

1

2

3

5

8

13

21

Exercise 1b: Fibonacci Iterative (★★✩✩✩)

The recursive calculation of Fibonacci numbers is not efficient, and the running time increases enormously from about the fortieth or fiftieth Fibonacci number. Write an iterative version for the calculation.

3.2.2 Exercise 2: Process Digits (★★✩✩✩)

Exercise 2a: Count Digits (★★✩✩✩)

Write recursive function count_digits(value) that finds the number of digits in a positive natural number. We already discussed how to extract digits in the previous chapter in section 2.1.

Exercise 2b: Cross Sum (★★✩✩✩)

Calculate the sum of the digits of a number recursively. Write recursive function calc_sum_of_digits(value) for this purpose.

Examples

Input

Number of digits

Cross sum

1234

4

1 + 2 + 3 + 4 = 10

1234567

7

1 + 2 + 3 + 4 + 5 + 6 + 7 = 28

3.2.3 Exercise 3: GCD (★★✩✩✩)

Exercise 3a: GCD Recursive (★✩✩✩✩)

Write function gcd(a, b) that computes the greatest common divisor (GCD)1. GCD can be expressed mathematically recursively as follows for two natural numbers a and b:
$$ mathit{gcd}left(a,b ight)=left{egin{array}{c}a,kern2.999999em b=0\ {}mathit{gcd}left(b,a\%b ight),b e 0end{array} ight. $$

Examples

Input 1

Input 2

Result

42

7

7

42

28

14

42

14

14

Exercise 3b: GCD Iterative (★★✩✩✩)

Create an iterative version for the GCD calculation.

Exercise 3c: LCM (★✩✩✩✩)

Write function lcm(a, b) that computes the least common multiplier (LCM) . For two natural numbers a and b, you can calculate this based on the GCD using the following formula:
$$ mathit{operatorname{lcm}}left(a,b ight)={a}^{ast }b/mathit{gcd}left(a,b ight); $$

Examples

Input 1

Input 2

Result

2

7

14

7

14

14

42

14

42

3.2.4 Exercise 4: Reverse String (★★✩✩✩)

Write recursive function reverse_string (text) that flips the letters of the text passed in.

Examples

Input

Result

“A”

“A”

“ABC”

“CBA”

“abcdefghi”

“ihgfedcba”

3.2.5 Exercise 5: List Sum (★★✩✩✩)

Write function sum_rec(values) that recursively computes the sum of the values of the given list. No call to the built-in functionality sum() is allowed.

Examples

Input

Result

[1, 2, 3]

6

[1, 2, 3, -7]

-1

3.2.6 Exercise 6: List Min (★★✩✩✩)

Write function min_rec(values) that uses recursion to find the minimum value of the passed list. For an empty list, the value sys.maxsize should be returned. In the implementation, no call to the built-in functionality min() is allowed.

Examples

Input

Result

[7, 2, 1, 9, 7, 1]

1

[11, 2, 33, 44, 55, 6, 7]

2

[1, 2, 3, -7]

-7

3.2.7 Exercise 7: Conversions (★★✩✩✩)

Exercise 7a: Binary (★★✩✩✩)

Write function to_binary(n) that recursively converts the given positive integer into a textual binary representation. No call to int(x, base) may be used.

Examples

Input

Result

5

“101”

7

“111”

22

“10110”

42

“101010”

256

“100000000”

Exercise 7b: Octal and Hexadecimal Numbers (★★✩✩✩)

Write conversions to octal and hexadecimal numbers by implementing the corresponding functions to_octal(n) and to_hex(n). Again, no call to int(x, base) may be used.

Examples

Input

Method

Result

7

octal

“7”

8

octal

“10”

42

octal

“52”

15

hexadecimal

“F”

77

hexadecimal

“4D”

3.2.8 Exercise 8: Exponential Function (★★✩✩✩)

Exercise 8a: Power of Two (★★✩✩✩)

Write recursive function is_power_of_2(n) that evaluates the given positive integer to see if it is a power of two.

Examples

Input

Result

2

True

10

False

16

True

Exercise 8b: Exponentiation Recursive (★★✩✩✩)

Write recursive function power_of(value, exponent) that exponentiates the given positive integer with the positive number specified as second parameter. For example, the call power_of(4, 2) should return the square of 4, so compute 42 = 16. You may not use the built-in functionality pow() or the operator **.

Exercise 8c: Exponentiation Iterative (★★✩✩✩)

Write an iterative version of this exponentiation functionality.

Examples

Input base

Input exponent

Result

2

2

4

2

8

256

4

4

256

3.2.9 Exercise 9: Pascal’s Triangle (★★✩✩✩)

Write function print_pascal(n) that prints Pascal’s triangle. For the value 5, the following output should be generated:
[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]

Starting with the third line, each subsequent line is calculated based on the previous one with the help of an addition, as shown in the last line of the following definition. For each line, these values are flanked by a 1 at the front and at the back. Since this is a two-dimensional structure, the recursive definition is a little more complex.

Tip

For background information and an in-depth explanation, please consult https://en.wikipedia.org/wiki/Pascal's_triangle.

3.2.10 Exercise 10: Number Palindromes (★★★★✩)

A palindrome is a word that reads the same from the front and the back. You can extend this definition to the digits of a number. Write recursive function is_number_palindrome(number) but without converting the number into a string and then using string functionalities like [::-1].

Examples

Input

Result

7

True

13

False

171

True

47742

False

3.2.11 Exercise 11: Permutations (★★★✩✩)

Calculate all permutations of a sequence of letters given as a string; this means all possible combinations of these letters. Implement this calculation in function calc_permutations(text). Consider also the case of duplicate letters, but do not use the standard Python functionality from the itertools module.

Examples

Input

Result

“A”

“A”

“AA”

“AA”

“AB”

“AB”, “BA”

“ABC”

“ABC, “BAC”, “ACB”, “CAB”, “CBA”, “BCA”

“AAC”

“AAC”, “ACA”, “CAA”

3.2.12 Exercise 12: Count Substrings (★★✩✩✩)

Write function count_substrings (text, value_to_find) that counts all occurrences of the given substring. Thereby, when a pattern is found, it should be consumed; in other words, it should not be available for hits again. This is shown n the following table as the last case. Implement the whole thing yourself without resorting to the standard count().

Examples

Input

Search term

Result

“xhixhix”

“x”

3

“xhixhix”

“hi”

2

“mic”

“mic”

1

“haha”

“ho”

0

“xxxxyz”

“xx”

2

3.2.13 Exercise 13: Ruler (★★✩✩✩)

In the introduction, I showed how to draw a simple shape of a ruler as well as a stylized snowflake (see Figure 3-3) using recursion. In this exercise, you want to imitate an English-style ruler. This involves dividing an area of one inch into 1/2 and 1/4 and 1/8. In doing so, the length of the strokes decreases by one each time.

Example

The output should look somewhat like the following:
---- 0
-
--
-
---
-
--
-
---- 1
-
--
-
---
-
--
-
---- 2

3.3 Solutions

3.3.1 Solution 1: Fibonacci (★★✩✩✩)

Solution 1a: Fibonacci Recursive (★✩✩✩✩)

Write function fib_rec(n) that recursively computes Fibonacci numbers based on the following definition:
$$ fib(n)=left{egin{array}{c}1,kern6.119996em n=1\ {}1,kern5.999996em n=2\ {} fibleft(n-1 ight)+ fibleft(n-2 ight),forall n&gt;2end{array} ight. $$

Example

For example, check the implementation with the following value progression:

Input

1

2

3

4

5

6

7

8

fib(n)

1

1

2

3

5

8

13

21

Algorithm The implementation in Python is exactly derived from the mathematical definition:
def fib_rec(n):
    if n <= 0:
        raise ValueError("n must be >= 1")
    # recursive termination
    if n == 1 or n == 2:
        return 1
    # recursive descent
    return fib_rec(n - 1) + fib_rec(n - 2)
Python shortcut To calculate Fibonacci numbers, you can use a lambda and write the whole thing as a one-liner—but without error handling and somewhat less readable. In addition, the recursive termination and descent are more difficult to recognize.
fib = lambda n: n if n < 2 else fib(n - 1) + fib(n - 2)
ATTENTION: OPTIMIZATION

Keep in mind that self calls happen again and again when calculating Fibonacci numbers. Even worse, that is the case for values that have already been calculated before. This is suboptimal. In addition to the iterative variant shown in the following, the technique memoization discussed in section 7.1 can be used for optimization. In Python, decorators are suitable for this purpose, which I briefly introduce in Appendix B.

Solution 1b: Fibonacci Iterative (★★✩✩✩)

The recursive calculation of Fibonacci numbers is not efficient, and the running time increases enormously from about the fortieth to fiftieth Fibonacci number. Write an iterative version for the calculation.

Algorithm Similarly to the recursive version, the iterative implementation checks at first the input for validity and then for the special cases for the invocation with the values 1 or 2. After that, you use two helper variables and a loop that runs from 2 to n. You then calculate the corresponding Fibonacci number from the sum of the two helper variables. After that, the two helper variables are assigned appropriately. This results in the following implementation:
def fib_iterative(n):
    if n <= 0:
        raise ValueError("n must be >= 1")
    if n == 1 or n == 2:
        return 1
    fib_n_2 = 1
    fib_n_1 = 1
    for _ in range(2, n):
        fib_n = fib_n_1 + fib_n_2
        # "shift" by one position
        fib_n_2 = fib_n_1
        fib_n_1 = fib_n
    return fib_n

Verification

For testing, use the following inputs, which show the correct functioning:
def input_and_expected():
    return [(1, 1), (2, 1), (3, 2), (4, 3),
            (5, 5), (6, 8), (7, 13), (8, 21)]
@pytest.mark.parametrize("n, expected", input_and_expected())
def test_fib_rec(n, expected):
    assert fib_rec(n) == expected
@pytest.mark.parametrize("n, expected", input_and_expected())
def test_fib_iterative(n, expected):
    assert fib_iterative(n) == expected

3.3.2 Solution 2: Process Digits (★★✩✩✩)

Solution 2a: Count Digits (★★✩✩✩)

Write recursive function count_digits(value) that finds the number of digits in a positive natural number. You explored how to extract digits in the previous chapter in section 2.1.

Examples

Input

Number of digits

Cross sum

1234

4

1 + 2 + 3 + 4 = 10

1234567

7

1 + 2 + 3 + 4 + 5 + 6 + 7 = 28

Algorithm If the number is less than 10, then return the value 1 because this corresponds to a digit. Otherwise, calculate the remaining value by dividing the number by 10. This invokes the counting method recursively as follows:
def count_digits(value):
    if value < 0:
        raise ValueError("value must be >= 0")
    # recursive termination
    if value < 10:
        return 1
    # recursive descent
    return count_digits(value // 10) + 1
ATTENTION: SANITY CHECKS AT THE BEGINNING OF THE METHOD

To ensure stable programs, it is often a good idea to check the parameters for validity. This can be accomplished in the form of simple if statements, as you have done several times before. In Python, however, this can be achieved more elegantly with the help of decorators, which I briefly introduce in Appendix B.

Python shortcut Of course, there are different variants to solve this task non-recursively and in a more performant way. With list comprehension, every digit is converted into a 1. They are summed up using the built-in sum() function. However, this tends to be a fancy, artificial solution. It is much clearer and more understandable to convert the number into a string and then call the built-in function len() to count the digits:
def count_digits_shorter(value):
    return sum([1 for _ in str(value)])
def count_digits_tricky(value):
    return len(str(value))

Solution 2b: Cross Sum (★★✩✩✩)

Calculate the sum of the digits of a number recursively. Write recursive function calc_sum_of_digits(value) for this purpose.

Algorithm Based on the solution for the first subtask, you only vary the returned value for the digit as well as the addition and the self call as follows:
def calc_sum_of_digits(value):
    if value < 0:
        raise ValueError("value must be >= 0")
    # recursive termination
    if value < 10:
        return value
    remainder = value // 10
    last_digit = value % 10
    # recursive descent
    return calc_sum_of_digits(remainder) + last_digit
Python shortcut The built-in function divmod() is useful here:
def calc_sum_of_digits(value):
    if value < 0:
        raise ValueError("value must be >= 0")
    # recursive termination
    if value < 10:
        return value
    remainder, last_digit = divmod(value, 10)
    # recursive descent
    return calc_sum_of_digits(remainder) + last_digit
To sum the digits, you again use list comprehension, which converts each digit into a numerical value. The sum is calculated with the built-in function sum():
def calc_sum_of_digits_shorter(value):
    return sum([int(ch) for ch in str(value)])

However, this assignment is not about brevity, but about getting to know the recursive description of the calculation of the sum of the digits.

Verification

For testing, use the following inputs, which show the correct operation:
@pytest.mark.parametrize("number, expected", [(1234, 4), (1234567, 7)])
def test_count_digits(number, expected):
    assert count_digits(number) == expected
@pytest.mark.parametrize("number, expected", [(1234, 10), (1234567, 28)])
def test_calc_sum_of_digits(number, expected):
    assert calc_sum_of_digits(number) == expected

3.3.3 Solution 3: GCD (★★✩✩✩)

Solution 3a: GCD Recursive (★✩✩✩✩)

Write function gcd(a, b) that computes the greatest common divisor (GCD)2. GCD can be expressed mathematically recursively as follows for two natural numbers a and b:
$$ mathit{gcd}left(a,b ight)=left{{}_{mathit{gcd}left(b,a\%b ight),kern0.36em b e 0}^{a,kern3.839998em b=0} ight. $$

Examples

Input 1

Input 2

Result

42

7

7

42

28

14

42

14

14

Algorithm The calculation of the GCD can be coded in Python fairly directly from the mathematical definition:
def gcd(a, b):
    # recursive termination
    if b == 0:
        return a
    # recursive descent
    return gcd(b, a % b)
Python shortcut Of course, this task can be achieved in a much more straightforward way by calling the built-in functionality gcd() from the module math. However, this assignment is about getting to know the recursive calculation of the GCD.
>>> import math
>>> math.gcd(42, 7)
7
>>> math.gcd(42, 14)
14

Solution 3b: GCD Iterative (★★✩✩✩)

Create an iterative version for the GCD calculation.

Algorithm The self call is transformed into a loop that is executed until the condition of the recursive termination is met. The trick is to reassign the variables as specified by the recursive definition.
def gcd_iterative(a, b):
    while b != 0:
        remainder = a % b
        a = b
        b = remainder
    # here applies b == 0
    return a

Verification

For testing, use the following inputs, which show the correct operation:
@pytest.mark.parametrize("a, b, expected",
                         [(42, 7, 7), (42, 28, 14), (42, 14, 14)])
def test_gcd(a, b, expected):
    assert gcd(a, b) == expected
@pytest.mark.parametrize("a, b, expected",
                         [(42, 7, 7), (42, 28, 14), (42, 14, 14)])
def test_gcd_iterative(a, b, expected):
    assert gcd_iterative(a, b) == expected

Solution 3c: LCM (★✩✩✩✩)

Write function lcm(a, b) that computes the least common multiplier (LCM) . For two natural numbers a and b, you can calculate this based on the GCD using the following formula:

lcm(a, b) = a ∗ b / gcd(a, b);

Examples

Input 1

Input 2

Result

2

7

14

7

14

14

42

14

42

Algorithm The calculation of the LCM can also be directly implemented from the mathematical definition, as long as you have already completed the functionality for the GCD:
def lcm(a, b):
    return a * b // gcd(a, b)
Python shortcut Of course, this task can be achieved in a much more straightforward way by calling the built-in functionality lcm() from the module math:
>>> import math
>>> math.lcm(2, 7)
14

Verification

For testing, use the following inputs, which show the correct operation:
@pytest.mark.parametrize("a, b, expected",
                         [(2, 7, 14), (7, 14, 14), (42, 14, 42)])
def test_lcm(a, b, expected):
    assert lcm(a, b) == expected
HINT: CALCULATE LCM WITHOUT USING GCD
Without the calculation of the GCD, you proceeds as follows. You determine both the maximum and the minimum of the two numbers. Starting from the larger number, this is increased by itself until the smaller number divides the resulting number perfectly (i.e., without a remainder).
def lcm_iterative(a, b):
    larger = max(a, b)
    smaller = min(a, b)
    value = larger
    while value % smaller != 0:
        value += larger
    return value

3.3.4 Solution 4: Reverse String (★★✩✩✩)

Write recursive function reverse_string(text) that flips the letters of the text passed in.

Examples

Input

Result

“A”

“A”

“ABC”

“CBA”

“abcdefghi”

“ihgfedcba”

Algorithm Extract the first character until you have a string of length 1 and then concatenate the whole in reverse order:
def reverse_string(text):
    # recursive termination
    if len(text) <= 1:
        return text
    first_char = text[0]
    remaining = text[1:]
    # recursive descent
    return reverse_string(remaining) + first_char
Python shortcut This can be achieved much easier by the following calls:
reversed_text = text[::-1]
reversed_text = "".join(reversed(text))

However, this task is about getting to know recursion.

Verification

For testing, use the following inputs, which show the correct operation:
@pytest.mark.parametrize("input, expected",
                         [("A", "A"), ("ABC", "CBA"),
                          ("abcdefghi", "ihgfedcba")])
def test_reverse_string(input, expected):
    assert reverse_string(input) == expected

3.3.5 Solution 5: List Sum (★★✩✩✩)

Write function sum_rec(values) that recursively computes the sum of the values of the given list. No call to the built-in functionality sum() is allowed.

Examples

Input

Result

[1, 2, 3]

6

[1, 2, 3, -7]

-1

Algorithm Compute the partial sum with the recursive definition as long as

sum(values(0)) = values[0]

sum(values(0 ... n))      = values[0] + sum(values(1 ... n))

until only a single element is left. As mentioned in the introduction, a helper function is useful, containing the actual processing and logic. Here the current value in the list is added to the recursively determined result:
def sum_rec(values):
    return sum_helper(values, 0)
def sum_helper(values, pos):
    # recursive termination
    if pos >= len(values):
        return 0
    # recursive descent
    return values[pos] + sum_helper(values, pos + 1)

Alternative algorithm Alternatively, it is also possible to let the pos counter run from length - 1 to 0, so the recursion reverses to the following:

sum(values(0 ... n)) = sum(values(0 ... n − 1)) + values[n]

This can be implemented in the form of functions sum_tail(values) and sum_tail_helper(values, pos) as follows:
def sum_tail(values):
    return sum_tail_helper(values, len(values) - 1)
def sum_tail_helper(values, pos):
    # recursive termination
    if pos < 0:
        return 0
    # recursive descent
    return sum_tail_helper(values, pos - 1) + values[pos]
Python shortcut Of course, the whole thing can be achieved in a much more straightforward way by calling the built-in functionality sum(). However, this assignment is about getting to know the recursive description of the sum calculation.
result = sum(values)
Likewise, the function reduce() from the module functools can be used—but this is less understandable and less readable:
import functools
def sum_lambda(values):
    return functools.reduce(lambda x, y: x + y, values)

Verification

The following inputs show the correct operation:
@pytest.mark.parametrize("values, expected",
                         [([1], 1), ( [1, 2, 3], 6), ([1, 2, 3, -7], -1)])
def test_sum_rec(values, expected):
    assert sum_rec(values) == expected
@pytest.mark.parametrize("values, expected",
                         [([1], 1), ( [1, 2, 3], 6), ([1, 2, 3, -7], -1)])
def test_sum_tail(values, expected):
    assert sum_tail(values) == expected
@pytest.mark.parametrize("values, expected",
                         [([1], 1), ( [1, 2, 3], 6), ([1, 2, 3, -7], -1)])
def test_sum_lambda(values, expected):
    assert sum_lambda(values) == expected

3.3.6 Solution 6: List Min (★★✩✩✩)

Write function min_rec(values) that uses recursion to find the minimum value of the passed list. For an empty list, the value sys.maxsize should be returned. In the implementation, no call to the built-in functionality min() is allowed.

Examples

Input

Result

[7, 2, 1, 9, 7, 1]

1

[11, 2, 33, 44, 55, 6, 7]

2

[1, 2, 3, -7]

-7

Algorithm Check the list starting from the first element and compare it with an initial minimum set to sys.maxsize. If the current element is smaller, it becomes the new minimum. Repeat this check for the list shortened by one position until the position has reached the end of the list.
def min_rec(values):
    return min_helper(values, 0, sys.maxsize)
def min_helper(values, pos, min_value):
    # recursive termination
    if pos >= len(values):
        return min_value
    value = values[pos]
    if value < min_value:
        min_value = value
    # recursive descent
    return min_helper(values, pos + 1, min_value)
Python shortcut An invocation of the built-in functionality min() would be much simpler. However, this task is about the recursive determination of the minimum.
result = min(values)

Verification

For testing, use the following inputs, which show the correct functionality:
@pytest.mark.parametrize("values, expected",
                         [([7, 2, 1, 9, 7, 1 ], 1), ([1, 2, 3, -7], -7),
                          ([11, 2, 33, 44, 55, 6, 7], 2), ([], sys.maxsize)])
def test_min_rec(values, expected):
    assert min_rec(values) == expected

3.3.7 Solution 7: Conversions (★★✩✩✩)

Solution 7a: Binary (★★✩✩✩)

Write function to_binary(n) that recursively converts the given positive integer into a textual binary representation. No call to int(x, base) may be used.

Examples

Input

Result

5

“101”

7

“111”

22

“10110”

42

“101010”

256

“100000000”

Algorithm The conversion is based on the already known extraction of the last digit and the determination of remainder, as was introduced in section 2.1. To convert a decimal number into a binary number, check whether the number passed can be represented by a single digit in the binary system (i. e., whether it is smaller than 2). Otherwise, the last digit is extracted first using the modulo operator and also the remainder. For this, you call the function recursively and then concatenate the string representation of the last digit. This results in the following sequence for the value 22:

Invocation

Process

Result

to_binary(22)

to_binary(22/2) + str(22%2) => to_binary(11) + “0”

“10110”

to_binary(11)

to_binary(11/2) + str(11%2) => to_binary(5) + “1”

“1011”

to_binary(5)

to_binary(5/2) + str(5%2) => to_binary(2) + “1”

“101”

to_binary(2)

to_binary(2/2) + str(2%2) => to_binary(1) + “0”

“10”

to_binary(1)

str(1) => “1”

“1”

Now let’s implement the whole thing in Python as follows:
def to_binary(n):
    if n < 0:
        raise ValueError("n must be >= 0")
    # recursive termination: check for digit in binary system
    if n <= 1:
        return str(n)
    remainder, last_digit = divmod(n, 2)
    # recursive descent
    return to_binary(remainder) + str(last_digit)

Solution 7b: Octal and Hexadecimal Numbers (★★✩✩✩)

Write conversions to octal and hexadecimal numbers by implementing the corresponding functions to_octal(n) and to_hex(n). Again, no call to int(x, base) may be used.

Examples

Input

Method

Result

7

Octal

“7”

8

Octal

“10”

42

Octal

“52”

15

Hexadecimal

“F”

77

Hexadecimal

“4D”

Algorithm The algorithm remains basically the same. You check whether the number passed can be represented by a single digit of the desired number system, such as smaller than 8 (octal) or 16 (hexadecimal). Otherwise, you first extract the last digit using a modulo operation and also the remainder. For the remainder, this function is called recursively and then the string representation of the last digit is concatenated. In this solution, you use an explicit division and the modulo operator for octal number processing and the built-in function divmod() when checking for hexadecimal numbers:
def to_octal(n):
    if n < 0:
        raise ValueError("n must be >= 0")
    # recursive termination: check for digit in octal system
    if n <= 7:
        return str(n)
    last_digit = n % 8
    remainder = n // 8
    # recursive descent
    return to_octal(remainder) + str(last_digit)
def to_hex(n):
    if n < 0:
        raise ValueError("n must be >= 0")
    # recursive termination: check for digit in hexadecimal system
    if n <= 15:
        return as_hex_digit(n)
    remainder, last_digit = divmod(n, 16)
    # recursive descent
    return to_hex(remainder) + as_hex_digit(last_digit)
For the sake of completeness there remains the conversion into a hexadecimal digit:
# easier handling of hexadecimal conversion
def as_hex_digit(n):
    if 0 <= n < 9:
        return str(n)
    if 10 <= n <= 15:
        # special character arithmetic
        return chr(ord('A') + (n - 10))
    raise ValueError("value not in range 0 - 15, " + "but is: " + n)
HINT: POSSIBLE OPTIMIZATION
Although the implementation shown for converting a single hexadecimal digit to a string is pretty straightforward, there is an amazingly elegant variant that is also readable and understandable. It checks in a given character set with indexed access via [n]:
def as_hex_digit_optimized(n):
    if 0 <= n <= 15:
        return "0123456789ABCDEF"[n]
    raise ValueError("value not in range 0 - 15, " + "but is: " + n)

Verification

For testing, use the following inputs, which show the correct operation:
@pytest.mark.parametrize("value, expected",
                         [(5, "101"), (7, "111"), (22, "10110"),
                          (42, "101010"), (256, "100000000")])
def test_to_binary(value, expected):
    assert to_binary(value) == expected
@pytest.mark.parametrize("value, expected",
                         [(42, "52"), (7, "7"), (8, "10")])
def test_to_octal(value, expected):
    assert to_octal(value) == expected
@pytest.mark.parametrize("value, expected",
                         [(77, "4D"), (15, "F"), (16, "10")])
def test_to_hex(value, expected):
    assert to_hex(value) == expected

3.3.8 Solution 8: Exponential Function (★★✩✩✩)

Solution 8a: Power of Two (★★✩✩✩)

Write recursive function is_power_of_2(n) that evaluates the given positive integer to see if it is a power of two.

Examples

Input

Result

2

True

10

False

16

True

Algorithm If the given number is smaller than the value 2, only the value 1 corresponds to a power, namely the 0th (i. e., 20). Now you have to check if it is an odd number. If this is the case, it is impossible for it to be a multiple and therefore not a power of 2. If the number is even, then check recursively with the number divided by 2.
def is_power_of_2(n):
    # recursive termination
    if n < 2:
        return n == 1
    if n % 2 != 0:
        return False
    # recursive descent
    return is_power_of_2(n // 2)

For the initial check, use a little trick with return n==1, which has the following effect:

n < 0 : False (negative number, so never the value 1)

n = 0 : False (0 ≠1)

n = 1 : True (1 = 1)

Let’s take a look at a short version of the implementation. To my mind, the upper one is more comprehensible. Moreover, in the first version, the recursive termination and the recursive descent are much clearer.
def is_power_of_2_short(n):
    return n == 1 or n > 0 and n % 2 == 0 and is_power_of_2_short(n // 2)

Solution 8b: Exponentiation Recursive (★★✩✩✩)

Write recursive function power_of(value, exponent) that exponentiates the given positive integer with the positive number specified as second parameter. For example, the call power_of(4, 2) should return the square of 4, so compute 42 = 16. You may not use the built-in functionality pow() or the operator **.

Algorithm Invoke the method recursively and multiply the number by the result of the self call until the exponent reaches 0 or 1. Furthermore, you have to reduce the exponent by 1 with each call.
def power_of(value, exponent):
    if exponent < 0:
        raise ValueError("exponent must be >= 0")
    # recursive termination
    if exponent == 0:
        return 1
    if exponent == 1:
        return value
    # recursive descent
    return value * power_of(value, exponent - 1)

This alternative has a cost of O(n). But it is quite easy to optimize this and reduce it to O(log(n)).

Optimized algorithm For optimization, use the trick of squaring the value and thereby halving the exponent. This leaves only the special treatment of an odd exponent, which requires another multiplication.
def power_of_optimized(value, exponent):
    if exponent < 0:
        raise ValueError("exponent must be >= 0")
    # recursive termination
    if exponent == 0:
        return 1
    if exponent == 1:
        return value
    # recursive descent
    result = power_of_optimized(value * value, exponent // 2)
    if exponent % 2 == 1:
        return value * result
    return result
Python shortcut Of course, the whole thing can be achieved in a much more straightforward way by calling the built-in functionality pow() or the operator **. But this task is about getting to know the recursive calculation.
result = pow(value, exponent)
result = value ** exponent

Solution 8c: Exponentiation Iterative (★★✩✩✩)

Write an iterative version of this exponentiation functionality.

Examples

Input base

Input exponent

Result

2

2

4

2

8

256

4

4

256

Algorithm As with the recursive version, you probably start with the two checks. Besides, the self call has to be converted into a loop, and the number has to be multiplied with the previous intermediate result. Furthermore, in each iteration, the exponent has to be reduced. However, a sharp look quickly shows that the two initial checks are already covered by the general case and therefore are no longer included in the listing.
def power_of_iterative(value, exponent):
    result = 1
    while exponent > 0:
        result *= value
        exponent -= 1
    return result

Verification

For testing, use the following inputs, which show the correct operation:
@pytest.mark.parametrize("value, expected",
                         [(2, True), (3, False), (4, True),
                          (10, False), (16, True)])
def test_is_power_of2(value, expected):
    assert is_power_of_2(value) == expected
def inputs_and_expected():
    return [(2, 2, 4), (4, 2, 16), (16, 2, 256),
            (4, 4, 256), (2, 8, 256)]
@pytest.mark.parametrize("number, exponent, expected",
                         inputs_and_expected())
def test_power_of(number, exponent, expected):
    assert power_of(number, exponent) == expected
@pytest.mark.parametrize("number, exponent, expected",
                         inputs_and_expected())
def test_power_of_iterative(number, exponent, expected):
    assert power_of_iterative(number, exponent) == expected

3.3.9 Solution 9: Pascal’s Triangle (★★✩✩✩)

Write function print_pascal(n) that prints Pascal’s triangle. For the value 5, the following output should be generated:
[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]

Starting with the third line, each subsequent line is calculated based on the previous one with the help of an addition, as shown in the last line of the following definition. For each line, these values are flanked by a 1 at the front and at the back. Since this is a two-dimensional structure, the recursive definition is a little more complex.

Tip

For background information and an in-depth explanation, please consult https://en.wikipedia.org/wiki/Pascal's_triangle.

Algorithm Implement the recursive definition as function as follows:
def calc_pascal(row, col):
    # recursive termination: top
    if col == 1 and row == 1:
        return 1
    # recursive termination: border
    if col == 1 or col == row:
        return 1
    # recursive descent
    return calc_pascal(row - 1, col) + calc_pascal(row - 1, col - 1)

Actually, there is no need for a separate termination condition for the top. Nevertheless, this is shown here for the sake of better comprehension—but of course, that is a matter of taste.

To calculate Pascal’s triangle, the previous method must now be invoked for each position in the triangle using two nested loops covering all rows and columns:
def print_pascal(n):
    for row in range(1, n + 1):
        for col in range(1, row + 1):
            print(calc_pascal(row, col), end=' ')
        print()
To try it out, use the Python console:
>>> print_pascal(7)
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1

Optimized algorithm The pure recursive definition results in quite a lot of computations. It becomes more understandable, comprehensible, and performant if you work line by line.

The starting point is the first line, which contains only the value 1. For all other values, you must call the method itself n times and then use the helper function calc_line(previous_line_values) to compute the new line. But to avoid mixing the computation and the console output, you add a parameter that is capable of performing actions, such as logging intermediate steps to the console.
def calc_pascal_with_action(n, action):
    # recursive termination
    if n == 1:
        if action:
            action([1])
        return [1]
    else:
        # recursive descent
        previous_line_values = calc_pascal_with_action(n - 1, action)
        new_line = __calc_line(previous_line_values)
        if action:
            action(new_line)
        return new_line
You can find a bit more complexity in the helper function __calc_line(previous_line) for calculating the values of the new line based on the previous one. It is important to keep in mind that the previous line contains at least two values and that you do not sum up to the last element, but only to the second last element. With the help of list comprehension, however, this can be implemented quite understandably and briefly as follows:
def __calc_line(previous_line):
    # value results from the two values of the previous line
    current_line = [previous_line[i] + previous_line[i + 1]
                    for i in range(len(previous_line) - 1)]
    # flanked by a 1 in each case
    return [1] + current_line + [1]

Verification

For testing, use the following call, which shows the correct operation:
>>> calc_pascal_with_action(5, print)
[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
You can then check something more formal with a unit test:
@pytest.mark.parametrize("n, expected",
                         [(1, [1]),
                          (2, [1, 1]),
                          (3, [1, 2, 1]),
                          (4, [1, 3, 3, 1]),
                          (5, [1, 4, 6, 4, 1]),
                          (6, [1, 5, 10, 10, 5, 1]),
                          (7, [1, 6, 15, 20, 15, 6, 1])])
def test_calc_pascal_with_action(n, expected):
    assert calc_pascal_with_action(n, None) == expected

3.3.10 Solution 10: Number Palindromes (★★★★✩)

A palindrome is a word that reads the same from the front and the back. You can extend this definition to the digits of a number. Write recursive function is_number_palindrome(number) but without converting the number into a string and then using string functionalities like [::-1].

Examples

Input

Result

7

True

13

False

171

True

47742

False

Algorithm Because of the restriction demanded in the exercise, it is not possible to compare character by character. However, the operations modulo and division are suitable, which you have already used for similar tasks. You use both to separate and compare the left and right digits.

Let’s approach the solution with examples:
#digits     value         calculation
-------------------------------------------------------------------------
1 digit                  => special case, is always palindrome
2 digits        11        divisor = 10
< 100                     1 % 10 = 1
                          11 / 10 = 1    palindrome
                13
                          3 % 10 = 3
                          13 / 10 = 1    X
3 digits        171       divisor = 100
< 1000                    1 % 10 = 1
                          171 / 100 =  1
                          remainder:   7 (171 / 10 = 17 % 10 = 7)
                          => check recursively
4 digits        4774      divisor = 1000
<10000                    4 % 10 = 4
                          4774 / 1000 = 4   ok
                          remainder:   77 (4774 / 10 = 477 % 100 = 77)
                          => check recursively
The right and left digits of a digit have to be extracted. If they match, the new value is determined by first dividing by 10 (cutting off the last digit) and then using the modulo operator with the appropriately selected amount of digits to determine the remainder (i. e., cutting off the front number). In particular, you have to figure out the length of the number as a power of ten to get the correct divisor.
def is_number_palindrome(number):
    if number < 10:
        return True
    factor = calc_pow_of_ten(number)
    divisor = int(pow(10, factor))
    if number < divisor * 10:
        left_number = number // divisor
        right_number = number % 10
        # cuts away a leading zero ...
        remaining_number = (number // 10) % (divisor // 10)
        return left_number == right_number and
               is_number_palindrome(remaining_number)
    return False
In the following, the calculation of the power of ten, as well as the counting of digits, are shown as helper functions, which resides in the utility module math_utils:
def calc_pow_of_ten(number):
    return count_digits(number) - 1
def count_digits(number):
    count = 0
    while number > 0:
        number = number // 10
        count += 1
    return count

The solution shown is by no means optimal since the factors have to be determined constantly. Furthermore, the entire procedure is still quite difficult to understand from the source code, even though helper functions have already been extracted.

Optimized algorithm As an optimization, implement the following version. Always separate the last digit, divide by 10, and call the function with the new values. Beforehand, compute the new value from the current value and the last digit by multiplying the current value by 10 and appending the last digit. If it is a palindrome, then the original value corresponds to the calculated value. The recursive termination occurs when either no more digits exist or only one single digit exists. The trick is that you rebuild the number from the back and finally compare it with the original value. In contrast to the other recursive helper functions presented so far, you need two buffers here, one for the current value and one for the remaining value.
def is_number_palindrome_rec(number):
    return __is_number_palindrome_rec_helper(number, 0, number)
def __is_number_palindrome_rec_helper(original_number, current_value,
                                      remaining_value):
    # recursive termination
    if current_value == original_number:
        return True
    # recursive termination
    if (remaining_value < 1):
        return False
    last_digit = remaining_value % 10
    new_current = current_value * 10 + last_digit
    new_remaining = remaining_value // 10
    print("last_digit: %d, new_current: %d, new_remaining: %d" %
          (last_digit, new_current, new_remaining))
    return __is_number_palindrome_rec_helper(original_number, new_current,
                                             new_remaining)
The calls for the value 121 can be illustrated as follows:
__is_number_palindrome_rec_helper(121, 0, 121) =>
last_digit: 1, new_current: 1, new_remaining: 12
__is_number_palindrome_rec_helper(121, 1, 12) =>
last_digit: 2, new_current: 12, new_remaining: 1
i__s_number_palindrome_rec_helper(121, 12, 1) =>
last_digit: 1, new_current: 121, new_remaining: 0
__is_number_palindrome_rec_helper(121, 121, 0)
True
Certainly it is of interest to see how the entire procedure works for a number that is not a palindrome, for example 123:
__is_number_palindrome_rec_helper(123, 0, 123) =>
last_digit: 3, new_current: 3, new_remaining: 12
__is_number_palindrome_rec_helper(123, 3, 12) =>
last_digit: 2, new_current: 32, new_remaining: 1
__is_number_palindrome_rec_helper(123, 32, 1) =>
last_digit: 1, new_current: 321, new_remaining: 0
__is_number_palindrome_rec_helper(123, 321, 0)
False

Verification

For testing, use the following inputs, which show the correct operation:
@pytest.mark.parametrize("number, expected",
                         [(7, True), (13, False), (171, True),
                          (47742, False), (123321, True),
                          (1234554321, True)])
def test_is_number_palindrome(number, expected):
    assert is_number_palindrome(number) == expected

3.3.11 Solution 11: Permutations (★★★✩✩)

Calculate all permutations of a sequence of letters given as a string; this means all possible combinations of these letters. Implement this calculation in function calc_permutations(text). Consider also the case of duplicate letters, but do not use the standard Python functionality from the itertools module.

Examples

Input

Result

“A

“A”

“AA”

“AA”

“AB”

“AB”, “BA”

“ABC”

“ABC, “BAC”, “ACB”, “CAB”, “CBA”, “BCA”

“AAC”

“AAC”, “ACA”, “CAA”

Algorithm The best way to compute all permutations for a given string is to take a look at the recursive definition and then implement it:

You recognize that for a single character, the permutations consist of the character itself. For multiple characters, the permutations are computed by finding the permutations of the remaining string without the character and by later combining them back with the character appropriately—more on this later. The original problem is reduced from a string of length n to n problems for strings of length n − 1. Thus, for the string ABC, you obtain the solution illustrated in Figure 3-4.
Figure 3-4

Computation of the permutations of ABC

With this knowledge in mind, the implementation will become much easier, and you can transform the following steps into Python.

  • Select and extract the ith character.

  • Build the remaining string and calculate the permutations for it.

  • Put the whole thing together again.

This is implemented as follows:
def calc_permutations(text):
    # recursive termination
    if is_blank(text) or len(text) == 1:
        return {text}
    combinations = set()
    # extract i-th character as new first character
    for i, new_first in enumerate(text):
        # recursive descent for rest without i-th character
        permutations = calc_permutations(text[0:i] + text[i + 1:])
        # adding the extracted character to all partial solutions
        for perm in permutations:
            combinations.add(new_first + perm)
    return combinations
def is_blank(text):
    return not (text and text.strip())

This implementation leads to the creation of quite a lot of instances of strings and sets as intermediate buffers. How can this be improved?

Optimized algorithm The drawbacks mentioned above are negligible for a short string. However, the longer the string gets, creating all the temporary objects and performing the string actions become more noticeable. How can this be avoided?

Let’s revisit ideas you’ve seen in other solutions. Instead of assembling the strings, you can cleverly pass them as parameters. One of them defines the remaining string, and the other one the currently already calculated prefix.
def calc_permutations_mini_opt(text):
    return __calc_permutations_mini_opt_helper(text, "")
def __calc_permutations_mini_opt_helper(remaining, prefix):
    # recursive termination
    if len(remaining) == 0:
        return {prefix}
    candidates = set()
    for i, current_char in enumerate(remaining):
        new_prefix = prefix + current_char
        new_remaining = remaining[0:i] + remaining[i + 1:]
        # recursive descent
        candidates.update(__calc_permutations_mini_opt_helper(new_remaining, new_prefix))
    return candidates

Let me comment a bit on the optimization. While calling the method calc_permutations("abcdefghij") takes about 7 to 8 seconds with my iMac (i7 4Ghz), calc_permutations_mini_opt("abcdefghij") finishes after only about 4 to 5 seconds—this is due to the very large number of calls, for which smaller optimizations may be worthwhile.

However, if you add one additional character to the input, the overhead grows enormously to around 111 seconds and for the optimized version to around 85 seconds. Such increases in running time are, of course, absolutely undesirable. After reading Chapter 7 covering more advanced recursion techniques, you may want to look again at the computation of the permutations to attempt an improvement with the help of memoization. However, this will be at the expense of the required memory.

Python shortcut Interestingly, Python provides ready-made functionality in the itertools module. Its result is a bit clumsy because the permutations are represented as a sequence of single characters. For your desired representation of the outcome, you only need to merge the values of the result tuples with join(). Again, the performance is better than that of the optimized variant. A call with “abcdefghij” takes about 3 seconds; with one character longer, it takes about 50 seconds.
import itertools
def calc_permutations_built_in(text):
    result_tuples = list(itertools.permutations(text))
    return {"".join(tuple) for tuple in result_tuples}

Verification

For testing, use the following inputs, which show the correct operation:
def input_and_expected():
    return [("A", {"A"}),
            ("AA", {"AA"}),
            ("AB", {"AB", "BA"}),
            ("ABC", {"ABC", "BAC", "ACB", "CAB", "CBA", "BCA"}),
            ("AAC", {"AAC", "ACA", "CAA"})]
@pytest.mark.parametrize("input, expected", input_and_expected())
def test_calc_permutations(input, expected):
    assert calc_permutations(input) == expected
@pytest.mark.parametrize("input, expected", input_and_expected())
def test_calc_permutations_mini_opt(input, expected):
    assert calc_permutations_mini_opt(input) == expected
@pytest.mark.parametrize("input, expected", input_and_expected())
def test_calc_permutations_built_in(input, expected):
    assert calc_permutations_built_in(input) == expected

3.3.12 Solution 12: Count Substrings (★★✩✩✩)

Write function count_substrings (text, value_to_find) that counts all occurrences of the given substring. Thereby, when a pattern is found, it should be consumed, so it should not be available for hits again. This is shown in the following table as the last case. Implement the whole thing yourself without resorting to the standard count().

Examples

Input

Search term

Result

“xhixhix”

“x”

3

“xhixhix”

“hi”

2

“mic”

“mic”

1

“haha”

“ho”

0

“xxxxyz”

“xx”

2

Algorithm First of all, check whether the first characters from the source text and the search string match. If this is the case, the number is increased and the search continues. If there is no match, then the source text is shortened by the first character. The process is continued recursively as previously described. The termination criterion is that the length of the given input is smaller than that of the search text. This indicates that no occurrences can exist.
def count_substrings(text, value_to_find):
    # recursive termination
    if len(text) < len(value_to_find):
        return 0
    count = 0
    remaining = ""
    # does the text start with the search string?
    if text.startswith(value_to_find):
        # hit: continue the search for the found
        # term after the occurrence
        remaining = text[len(value_to_find):]
        count = 1
    else:
        # remove first character and search again
        remaining = text[1:]
    # recursive descent
    return count_substrings(remaining, value_to_find) + count
HINT: POSSIBLE VARIATION
You could imagine that a small modification of the requirements would now be to find all potential substrings rather than continuing to search behind them after finding a substring. Interestingly, this simplifies the implementation:
def count_substrings_v2(text, value_to_find):
    # recursive termination
    if len(text) < len(value_to_find):
        return 0
    # does the text starts with the search string?
    count = 1 if text.startswith(value_to_find) else 0
    # remove first character and search again
    remaining = text[1:]
    # recursive descent
    return count_substrings_v2(remaining, value_to_find) + count

Optimized algorithm Calls to text[len(value_to_find):] and text[1:] keep generating new strings in the original algorithm. For short input values, this is not so dramatic. But for a very long text, this can be unfavorable.

Well, what might an optimization look like? You still traverse the input from left to right. But instead of shortening the input, it is more feasible to use a position pointer left. This causes the following adjustments:
  1. 1.

    Since the text does not get shorter, you must now subtract the value of left from the original length.

     
  2. 2.

    You used startswith() to compare for a match. Conveniently there is a variant that allows for providing an offset.

     
  3. 3.

    If there is a match, you must move the position pointer by the number of characters in the search pattern, otherwise by one position.

     
This results in the following implementation:
def count_substrings_optimized(text, value_to_find):
    return count_substrings_helper(text, value_to_find, 0)
def count_substrings_helper(text, value_to_find, left):
    if len(text) - left < len(value_to_find):
        return 0
    count = 1 if text.startswith(value_to_find, left) else 0
    if text.startswith(value_to_find, left):
        left += len(value_to_find)
    else:
        left += 1
    return count_substrings_helper(text, value_to_find, left) + count

Python shortcut Conveniently, this functionality is already built into Python. Therefore, a call to the built-in functionality count() for strings would be much simpler. However, the point here is to look at variants and see how to avoid too many temporary strings.

In practice, please use calls like the following, here for the inputs from the example of this task:
print("xhixhix".count("x"))
print("xhixhix".count("hi"))
print("mic".count("mic"))
print("haha".count("ho"))
print("xxxxyz".count("xx"))

Verification

The following inputs show the correct operation for the three variants. You find the same entries here in the first and last test cases. You have, therefore, already outsourced this to a function to avoid duplication.
def create_inputs_and_expected():
    return [("xhixhix", "x", 3), ("xhixhix", "hi", 2), ("mic", "mic", 1),
            ("haha", "ho", 0), ("xxxxyz", "xx", 2), ("xxxx", "xx", 2),
            ("xx-xxx-xxxx-xxxxx-xxxxxx", "xx", 9),
            ("xx-xxx-xxxx-xxxxx-xxxxxx", "xxx", 5)]
@pytest.mark.parametrize("input, search_for, expected",
                         create_inputs_and_expected())
def test_count_substrings(input, search_for, expected):
    assert count_substrings(input, search_for) == expected
@pytest.mark.parametrize("input, search_for, expected",
                         [("xhixhix", "x", 3), ("xhixhix", "hi", 2),
                          ("mic", "mic", 1), ("haha", "ho", 0),
                          ("xxxxyz", "xx", 3), ("xxxx", "xx", 3),
                          ("xx-xxx-xxxx-xxxxx-xxxxxx", "xx", 15),
                          ("xx-xxx-xxxx-xxxxx-xxxxxx", "xxx", 10)])
def test_count_substrings_v2(input, search_for, expected):
    assert count_substrings_v2(input, search_for) == expected
@pytest.mark.parametrize("input, search_for, expected",
                         create_inputs_and_expected())
def test_count_substrings_optimized(input, search_for, expected):
    assert count_substrings_optimized(input, search_for) == expected

3.3.13 Solution 13: Ruler (★★✩✩✩)

In the introduction, I showed how to draw a simple shape of a ruler as well as a stylized snowflake (see Figure 3-3) using recursion. In this exercise, you want to imitate an English-style ruler. This involves dividing an area of one inch into 1/2 and 1/4 and 1/8. In doing so, the length of the strokes decreases by one each time.

Example

The output should look somewhat like the following:
---- 0
-
--
-
---
-
--
-
---- 1
-
--
-
---
-
--
-
---- 2
Algorithm The drawing of the full inch markers is done in a loop. The intermediate lines are generated in function draw_interval() . This, in turn, takes advantage of the recursive nature of the distribution of lines. A shorter line is drawn around each slightly longer centerline. This is repeated as long as the line length is greater than or equal to 1.
def draw_ruler(major_tick_count, max_length):
    draw_line(max_length, "0")
    for i in range(1, major_tick_count + 1):
        draw_interval(max_length - 1)
        draw_line(max_length, i)
Finally, you need two helper functions for drawing an interval and a line of the specified length, including an optional marker (for the full inch numbers):
def draw_interval(center_length):
    if center_length > 0:
        draw_interval(center_length - 1)
        draw_line(center_length, "")
        draw_interval(center_length - 1)
def draw_line(count, label):
    print(("-" * count) + " " + str(label))

Verification

For testing, you call the draw_ruler() function as follows:
>>> draw_ruler(3, 4)
---- 0
-
--
-
---
-
--
-
---- 1
-
--
-
---
-
--
-
---- 2
-
--
-
---
-
--
-
---- 3

3.4 Summary: What You Learned

This introductory chapter laid the foundation for a good understanding of recursion. The exercises expanded your knowledge on how to use recursion to solve problems. This is crucial to be able to implement recursive solutions in the following chapters in an efficient way and with a solid basis.

Now let’s move on to sequences of characters, also known as strings. Very few program can live without them—time to get into it.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset