Two ways of writing a recursive one-liner: (1) write the function with return statement in a single line such as in def f(x): return f(x+1), or (2) assign a lambda function to a variable name and use the variable name in the return expression of the lambda function such as in f = lambda x: f(x). To define a recursion base case, you can use the ternary operator x if c else y to return x if condition c is met, else y.
Let’s dive into the problem and several detailed examples!
Problem: How to write a recursive function in a single line of code?
You may find this challenging because you need to define the function name, the base case, and the recursive function call—all in a single line of Python code!
Related Article: To refresh your general recursion skills, check out my detailed blog article (including video).
Here’s an overview of the different algorithms, we one-linerized recursively! 😉
Exercise: Run the code and test the results. Are they correct? Now change the inputs to the recursion base cases and run the code again! Are they correct?
Let’s dive into each of those methods!
Method 1: Recursive Fibonacci
What are Fibonacci numbers? The Fibonacci numbers are the numbers of the Fibonacci series. The series starts with the numbers 0 and 1. Each following series element is the sum of the two previous series elements. That’s already the algorithm to calculate the Fibonacci series!
We consider the following problem: Given a number n>2. Calculate a list of the first n Fibonacci numbers in a single line of code (starting from the first Fibonacci number 0)!
# Method 1: Recursive Fibonacci
def fib(n): return 1 if n in {0, 1} else fib(n-1) + fib(n-2)
print(fib(10))
# 89This one-liner is based on this Github repository but made more concise and more readable. It uses the ternary operator to compress the return value of the function.
Explanation Ternary: the most basic ternary operator x if c else y consists of three operands x, c, and y. It is an expression with a return value. The ternary operator returns x if the Boolean expression c evaluates to True. Otherwise, if the expression c evaluates to False, the ternary operator returns the alternative y.
Method 2: Recursive Factorial
Consider the following problem: There are 20 football teams in England’s premier league. Each team can possibly reach any of the 20 ranks at the end of the season. How many possible rankings exist in the premier league, given 20 fixed teams?
Figure: Example of three possible rankings of the football teams in England’s premier league.
The figure shows three different rankings of the teams. In computer science terminology, you would denote each ranking as a “permutation”. A permutation is defined as a specific order of set elements (here: football teams). Using this terminology, our goal is to find the number of permutations of a given set (the set of all football teams). The number of those permutations has important implications in practice such as betting applications, match prediction, and game analysis. For example, when assuming 100 different rankings with equal probability, the probability of a specific ranking is 1/100 = 1%. This can be used as a base probability (a priori probability) for game prediction algorithms. Under these assumptions, a randomly guessed ranking has a 1% probability of being the correct outcome after one season.
How to calculate the number of permutations of a given set? As it turns out, the factorial function n! calculates the number of permutations of a given set of n elements. The factorial is defined as follows:
For example:
Why does the factorial count the number of permutations of a given set of elements? The answer is very straightforward: Say, you have a set of ten elements S = {s0, s1, ..., s9} and ten buckets B = {b0, b1, ..., b9}. In the football example, there are twenty teams (the elements) and twenty table ranks (the buckets). To get a permutation of S
- First, you take a random element from the set
S. In how many buckets can you place this element? There are ten empty buckets so you have ten options. - Second, you take the next element from the set. In how many buckets can you place this element? There are nine empty buckets so you have nine options.
- …
- Finally, you take the last element from the set. In how many buckets can you place this element? There is only one empty bucket so you have one option.
In total, you have 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 10! different options. Each option of placing elements into the buckets represents one permutation of the set elements. The number of permutations of a set with n elements is n!.
You now know everything you need to know to solve the following problem: Write a Python one-liner solution that computes the number of permutations n! of a set with n elements.
# Method 2: Recursive Factorial def fac(x): return 1 if x<=1 else x * fac(x-1) print(fac(10)) # 3628800
This one-liner is based on this forum post but, again, I improved readability and conciseness. For instance, it’s generally a good idea to handle the recursion base case first.
The factorial function can be defined recursively as
with the recursion base cases defined as
The intuition behind these base cases is the following: A set with one element has one permutation. And a set with zero elements has one permutation (there is one way of assigning zero elements to zero buckets).
Method 3: Factorial One-Liner with Lambda
An alternative to calculate the recursive factorial in a single line is the following:
# Method 3: Recursive Factorial with Lambda fac = lambda n: 1 if n<=1 else n * fac(n-1) print(fac(10)) # 3628800
The code uses the previously-discussed recursive definition. It creates a lambda function with one argument n. It assigns the lambda function to the name fac. Finally, it calls the named function fac(n-1) to calculate the result of the function call fac(n). By using the solution to the easier problem fac(n-1), we can construct the solution of the harder problem fac(n) by multiplying it with the input argument n. As soon as we reach the recursion base case n <= 1, we simply return the hard-coded solution fac(1) = fac(0) = 1.
Let’s dive into a more advanced recursive one-liner: the Quicksort algorithm!
Method 4: Recursive Quicksort One-Liner
Next, you’ll learn about the popular sorting algorithm Quicksort. Surprisingly, a single line of Python code is all you need to write the Quicksort algorithm! This code is based on this detailed blog tutorial. If you want more explanations, check it out!
Quicksort sorts a list by recursively dividing the big problem (sorting the list) into smaller problems (sorting two smaller lists) and combining the solutions from the smaller problems in a way that it solves the big problem. In order to solve each smaller problem, the same strategy is used recursively: the smaller problems are divided into even smaller subproblems, solved separately, and combined. Because of this strategy, Quicksort belongs to the class of “Divide and Conquer” algorithms. Let’s dive deeper into the Quicksort algorithm:
The main idea of Quicksort is to select a pivot element and then placing all elements that are larger or equal than the pivot element to the right and all elements that are smaller than the pivot element to the left. Now, you have divided the big problem of sorting the list into two smaller subproblems: sorting the right and the left partition of the list. What you do now is to repeat this procedure recursively until you obtain a list with zero elements. This list is already sorted, so the recursion terminates.
The following Figure shows the Quicksort algorithm in action:
Figure: The Quicksort algorithm selects a pivot element, splits up the list into (i) an unsorted sublist with all elements that are smaller or equal than the pivot, and (ii) an unsorted sublist with all elements that are larger than the pivot. Next, the Quicksort algorithm is called recursively on the two unsorted sublists to sort them. As soon as the sublists contain maximally one element, they are sorted by definition – the recursion ends. At every recursion level, the three sublists (left, pivot, right) are concatenated before the resulting list is handed to the higher recursion level.
This brings us to the following problem:
Create a function q which implements the Quicksort algorithm in a single line of Python code – and thus sorts any argument given as a list of integers.
## The Data unsorted = [33, 2, 3, 45, 6, 54, 33] ## The One-Liner q = lambda l: q([x for x in l[1:] if x <= l[0]]) + [l[0]] + q([x for x in l if x > l[0]]) if l else [] ## The Result print(q(unsorted))
Listing: One-liner solution for the Quicksort algorithm using recursion.
We have already discussed the recursive Quicksort algorithm above. The one-liner resembles exactly the discussed algorithm. First, we create a new lambda function q which takes only one list argument l. The lambda function has the following structure:
lambda l: q(left) + pivot + q(right) if l else []
The lambda function returns the empty list [] in the recursion base case (that is – the list to be sorted is empty and, therefore, trivially sorted). In any other case, it selects the pivot element as the first element of list l, divides all elements into two sublists (left and right) based on whether they are smaller or larger than the pivot. To achieve this, we use simple list comprehension. As the two sublists are not necessarily sorted, we recursively execute the Quicksort algorithm on them. Finally, we combine all three lists and return the sorted list.
Therefore, the result is:
## The Result print(q(unsorted)) # [2, 3, 6, 33, 33, 45, 54]
Python One-Liners Book: Master the Single Line First!
Python programmers will improve their computer science skills with these useful one-liners.
Python One-Liners will teach you how to read and write “one-liners”: concise statements of useful functionality packed into a single line of code. You’ll learn how to systematically unpack and understand any line of Python code, and write eloquent, powerfully compressed Python like an expert.
The book’s five chapters cover (1) tips and tricks, (2) regular expressions, (3) machine learning, (4) core data science topics, and (5) useful algorithms.
Detailed explanations of one-liners introduce key computer science concepts and boost your coding and analytical skills. You’ll learn about advanced Python features such as list comprehension, slicing, lambda functions, regular expressions, map and reduce functions, and slice assignments.
You’ll also learn how to:
- Leverage data structures to solve real-world problems, like using Boolean indexing to find cities with above-average pollution
- Use NumPy basics such as array, shape, axis, type, broadcasting, advanced indexing, slicing, sorting, searching, aggregating, and statistics
- Calculate basic statistics of multidimensional data arrays and the K-Means algorithms for unsupervised learning
- Create more advanced regular expressions using grouping and named groups, negative lookaheads, escaped characters, whitespaces, character sets (and negative characters sets), and greedy/nongreedy operators
- Understand a wide range of computer science topics, including anagrams, palindromes, supersets, permutations, factorials, prime numbers, Fibonacci numbers, obfuscation, searching, and algorithmic sorting
By the end of the book, you’ll know how to write Python at its most refined, and create concise, beautiful pieces of “Python art” in merely a single line.