How to Build a Recursive Function in Python

How to create a recursive function to create a list of values

You don't need the second function or any outside variables. You simply need an edge condition to know when to stop and then recursion that does something. Here that something can be creating a part of your list and recursing to get the rest.

It's often helpful think about the edge case first, then think about what happens with one recursive call.

You also need to remember to return from your function (and think about what the edge condition should return (for example an empty list):

def create_list_recurse(start, end):
    if start > end:
        return []

    return [start] + create_list_recurse(start + 1, end)

create_list_recurse(0, 9)
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

create_list_recurse(3, 1) #edge case returns empty 
# []

Recursive Function through dict of lists

You could iteratively call recurse_over_object under if 'subfolder' in key:. So like:

def recurse_over_object(dict_obj):
    for key, value in dict_obj.items():
        if 'subfolder' in key:
            for item in value:
                recurse_over_object(item)
        else:
            print(key, value)

Then

for d in data:
    recurse_over_object(d)

outputs:

name Business Operations
team_edit ['BusinessOperations']
team_view ['Snaptest']
name test_sub
team_edit ['BusinessOperations', 'Freddy']
team_view ['hugo']
name test_sub2
name test_sub_sub
team_edit ['BusinessOperations', 'Freddy']
team_view ['hugo']

how to make a recursive function that builds a list

Thanks to your comment I think having understood the real purpose of your question. If you take a look to the following code, you will find the recursion you are looking for and you will see how to "save the variables of the childs".

import os

def print_directory_listing(directory = '.'):
    files_list=[]

    for file_structure in os.listdir(directory):                
        file_structure_path = os.path.join(directory, file_structure)
        if os.path.isdir(file_structure_path):
            files_list+=print_directory_listing(file_structure_path)
        else:
            files_list.append(file_structure_path)

    return files_list

How to build a pandas dataframe in a recursive function?

Unfortunately pandas doesn't have functionality to do subtotals - so the trick is to just calculate them on the side and concatenate together with original dataframe.

from itertools import combinations
import numpy as np

dim = ['A', 'B']
vals = ['M']

df = pd.concat(
    [df]
# subtotals:
    + [df.groupby(list(gr), as_index=False)[vals].sum() for r in range(len(dim)-1) for gr in combinations(dim, r+1)]
# total:
    + [df.groupby(np.zeros(len(df)))[vals].sum()]
    )\
    .sort_values(dim)\
    .reset_index(drop=True)\
    .fillna("ALL")

Output:

      A    B    M
0     1    1   10
1     1    1   20
2     1    2   30
3     1    3   40
4     1  ALL  100
5     2    1   50
6     2  ALL   50
7   ALL    1   80
8   ALL    2   30
9   ALL    3   40
10  ALL  ALL  150

Returning list of different results that are created recursively in Python

Currently the practice I do is pass along a list in the function call (as an argument) and the function would return this list

This is not the purest way to attack a recursive problem. It would be better if you can make the recursive function such that it solves the sub problem without an extra parameter variable that it must use. So the recursive function should just return a result as if it was the only call that was ever made (by the testing framework). So in the example, that recursive call should return a list with trees.

Alternatively the recursive function could be a sub-function that doesn't return a list, but yields the individual values (in this case: trees). The caller can then decide whether to pack that into a list or not. This is more pythonic.

As to the example problem, it is also important to identify some invariants. For instance, it is clear that there are no solutions when n is even. As to recursive aspect: once you have decided to create a root, then both its left and right sided subtree will have an odd number of nodes. Of course, this is an observation that is specific to this problem, but it is important to look for such problem properties.

Finally, it is equally important to see if the same sub problems can reoccur multiple times. This surely is the case in the example problem: for instance, the left subtree may sometimes have the same number of nodes as the right subtree. In such cases memoization will improve efficiency (dynamic programming).

When the recursive function returns a list, the caller can then iterate that list to retrieve its elements (trees in the example), and use them to build an extended result that satisfies the caller's task. In the example case that means that the tree taken from the recursively retrieved list, is appended as a child to a new root. Then this new tree is appended to a new list (not related to the one returned from the recursive call). This new list will in many cases be longer, although this depends on the type of problem.

To further illustrate the way to tackle these problems, here is a solution for the example problem: one which uses the main function for the recursive calls, and using memoization:

class Solution:
    memo = { 1: [TreeNode()] }
    
    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
        # If we didn't solve this problem before...
        if n not in self.memo:
            # Create a list for storing the results (the trees)
            results = []
            # Before creating any root node, 
            #    decide the size of the left subtree.
            #    It must be odd
            for num_left in range(1, n, 2):
                # Make the recursive call to get all shapes of the
                # left subtree
                left_shapes = self.allPossibleFBT(num_left)
                # The remainder of the nodes must be in the right subtree
                num_right = n - 1 - num_left  # The root also counts as 1
                right_shapes = self.allPossibleFBT(num_right)
                # Now iterate the results we got from recursion and 
                #    combine them in all possible ways to create new trees
                for left in left_shapes:
                    for right in right_shapes:
                        # We have a combination. Now create a new tree from it
                        # by putting a root node on top of the two subtrees:
                        tree = TreeNode(0, left, right)
                        # Append this possible shape to our results
                        results.append(tree)
            # All done. Save this for later re-use
            self.memo[n] = results
        return self.memo[n]

This code can be made more compact using list comprehension, but it may make the code less readable.

Recursive function with strings and integers

You may use bitwise operators:

# Define the length of the code word in bits
# Normaly i would expect the encoding word 
# length as a parameter of the function or as a member of a relating class.
word_length = 5

# Define the bitmask: 0000 0000  0000 0000  0000 0000  0000 0000  0001 1111 
bitmask = 2 ** word_length - 1

def decompress(n):
    result = ''
    if n > 0:
        # Take the only the last n bit by a and with the bitmask
        letter_code = n & bitmask
        # Decode the resulting code
        result += alphabet[letter_code]
        # recursively call the function without the current letter
        # by using a bitwise right shift with the word length
        result += aux(n >> word_length)
    return result

But if you have to use the division and modulo operators:

word_length = 5

max_letters_count = 2 ** word_length

def decompress(n):
    result = ''
    if n > 0:
        # Take the only the last n bit by taking the modulo with the max_letters_count 
        letter_code = n % max_letters_count 
        # Decode the resulting code
        result += alphabet[letter_code]
        # recursively call the function without the current letter
        # by using a integer division with the max_letters_count 
        result += aux(n // max_letters_count )
    return result 

Now you can make these functions tail recursive (https://en.wikipedia.org/wiki/Tail_call):

def aux_tail_recursive(result_string, code):
    if code <= 0:
        return result_string
    result_string += alphabet[code & bitmask]
    next_code = code >> word_length
    return aux_tail_recursive(result_string, next_code)

or

def decompress_tail_recursive(result_string, code):
    if code <= 0:
        return result_string
    result_string += alphabet[code % max_value]
    code_next = code // max_value
    return decompress_tail_recursive(result_string, code_next)

---

Related Topics