A recursive function is a nice way to do this:

def collect_folders(start, depth=-1)
    """ negative depths means unlimited recursion """
    folder_ids = []

    # recursive function that collects all the ids in `acc`
    def recurse(current, depth):
        folder_ids.append(current.id)
        if depth != 0:
            for folder in getChildFolders(current.id):
                # recursive call for each subfolder
                recurse(folder, depth-1)

    recurse(start, depth) # starts the recursion
    return folder_ids

def count(ls):
    if not ls:  # empty
        return 0
    return count(ls[1:]) + 1

Use it like this:

>>> find = [a, b, c, d]
>>> count(find)
4

You can use itertools.product and its repeat argument:

from operator import mul
import itertools


def myprod(n, div, repeat=4):
    # i is a list of factors
    for i in itertools.product(range(n), repeat=repeat):
        # calculate product of all elements of list            
        prod = reduce(mul, i, 1)
        if prod % div == 0:
            yield prod

print list(myprod(10, 6))

Changing the repeat argument of myprod will change the number of loops and factors you are calculating.

Also, since multiplication is commutative (a * b == b * a) you should eliminate repetitive computations using itertools.combinations_with_replacement:

from operator import mul
import itertools


def myprod_unique(n, div, repeat=4):
    for i in itertools.combinations_with_replacement(range(n), r=repeat):
        prod = reduce(mul, i, 1)
        if prod % div == 0:
            yield prod

print list(myprod_unique(10, 6))

If you remove duplicate results from myprod using set you will find that the two results are equal:

print set(myprod_unique(10, 6)) == set(myprod(10, 6))

but you have cut down the number of operations drastically from n ** r to (n+r-1)! / r! / (n-1)!. For example 92,378 instead of 10,000,000,000 for n=10, r=10.

but I wonder if it's okay there's no "return" line under "else:"

Yes, that's OK. You don't need to return anything from your function if you don't want to. In fact, in the interest of consistency, you may as well remove the thing returned in the if block too:

def printElement(inputlist):
        newlist=inputlist
        if len(newlist)==0:
                return
        else:
                removedElement=newlist[len(inputlist)-1]
                newlist=newlist[:len(inputlist)-1]
                Element=printElement(newlist)
                print(removedElement)


collection = ['hey', 5, 'd']

printElement(collection)

Is it better code with or without the newlist?

Assigning new things to inputlist won't modify it outside of the function, so there's no harm in doing so. May as well get rid of newlist.

def printElement(inputlist):
        if len(inputlist)==0:
                return
        else:
                removedElement=inputlist[len(inputlist)-1]
                inputlist=inputlist[:len(inputlist)-1]
                Element=printElement(inputlist)
                print(removedElement)


collection = ['hey', 5, 'd']

printElement(collection)

you don't use Element after assigning it, so you may as well not assign it at all.

def printElement(inputlist):
        if len(inputlist)==0:
                return
        else:
                removedElement=inputlist[len(inputlist)-1]
                inputlist=inputlist[:len(inputlist)-1]
                printElement(inputlist)
                print(removedElement)


collection = ['hey', 5, 'd']

printElement(collection)

You don't really need to modify inputlist, since you only use it once after modifying it. Just stick that expression straight into the printElement call. And now that inputlist is never modified, you can get rid of removedElement too, and just inline its expression in the print function.

def printElement(inputlist):
        if len(inputlist)==0:
                return
        else:
                printElement(inputlist[:len(inputlist)-1])
                print(inputlist[len(inputlist)-1])


collection = ['hey', 5, 'd']

printElement(collection)

Fun fact: for any list x, x[len(x)-1] can be shortened to x[-1]. Same with x[:len(x)-1] to x[:-1].

def printElement(inputlist):
        if len(inputlist)==0:
                return
        else:
                printElement(inputlist[:-1])
                print(inputlist[-1])


collection = ['hey', 5, 'd']

printElement(collection)

Since the first block unconditionally returns, you could remove the else and just put that code at the function level, without changing the code's behavior. Some people find this less easy to read. Personally, I like my code to have the least amount of indentation possible.

def printElement(inputlist):
        if len(inputlist)==0:
                return
        printElement(inputlist[:-1])
        print(inputlist[-1])


collection = ['hey', 5, 'd']

printElement(collection)

That's about as compact as you can get, with a recursive solution. You should probably just stick with the iterative version, for a few reasons:

• Fewer lines
• More easily understood
• Doesn't raise a "maximum recursion depth exceeded" exception on lists with 200+ elements

Recursion is about a base case and an iterative case. In your situation, think of the smallest matrix you can - an empty matrix. That is your base case. Your function should return a path length of 0 if it is empty.

The iterative case is a bit more difficult, and usually where things become confusing. The key goal of the iterative case is to reduce the size of the problem, usually by the smallest amount possible.

To overly simplify, if you start with a function like this:

def f(ls):
    for x in ls:
        result = g(x, result)
    return result

Then the iterative version looks like this:

def f(ls, result):
    if 0 == len(x):  # Base Case
        return result
    else:  # Iterative Case
        result = g(x, result)
        return f(ls[1:], result)

The trick is figuring out what of your internal logic goes into g() and how to represent the result.

Let's take a simpler version of your problem, where we deal with a single array and want to return the longest 'path' in that array. A path is a sequence of integers that are incrementing by one.

So, if we have [0,1,2,3] the expected value is 4. If we have [0,1,1,2,3] the expected value is 3. Similarly, 3 would be expected for the input [0,1,2,2,1]. [3,2,1] should return 0.

The most basic signature we require is this:

def f(ls: list[int]) -> int

Essentially, 'a function that takes a list of ints and returns the length of the longest path'. But we have to remember a bit of extra state to do this properly. Specifically, we need to remember the length of the current path we are on, and the lengths of all paths we have found.

def f(ls: list[int], current_path: int) -> int

Let's examine the base case. A base case is any case where reducing the size of your input (in our case 'input' really refers only to ls) would not yield an easier problem to solve. There are two base cases - if the input list is length 0 or 1. In both these cases, we have no need to shrink the problem any further.

def f(ls: list[int], current_path: int) -> int:
    # If there are no elements, current_path is the only valid length
    if 0 == len(ls):
         return current_path
    # If there is one element, increment current_path before returning it, to account for the length that element adds
    if 1 == len(ls):
         return current_path + 1
        

These serve to terminate the recursion. Now lets look at the iterative case:

def f(ls: list[int], current_path: int) -> int:
    # Base cases
    if 0 == len(ls):
        return current_path
    if 1 == len(ls):
        return current_path + 1
    # Iterative case - guaranteed that len(ls) >= 2
    current_path = current_path + 1  # Increment the current_path to account for the current element.
    if ls[1] == ls[0] + 1:
        # In this branch we know that the path will continue.
        return f(ls[1:], current_path)  # ls[1:] reduces our problem space by one element
    else:
        # In this branch the path ends, because the next element breaks the incremental sequence.
        recursive_result = returnf(ls[1:], 0)  # Reduce the problem space and start a new path of length 0
        return max(recursive_result, current_path)  # Choose which path is longer

There is a lot going on here, so I'll break it down in parts. The key thing to remember is that we are going to reduce the problem space - shorten the list - and then recurse with that smaller problem space. The element we are removing is therefore key to determining how we proceed.

Since we are removing one element, we add one to the current path. If the incoming path length was 0, we now have a path length of 1. If it was 3, we now have a path of 4.

Then we check the value of the next element. Is it exactly larger than the current element? If so, we know the path will continue, so we recurse, passing along a list without the current element and the length of our current path.

If it is not exactly one more, we know our current path ends here. In the recursion we pass along a new path length of 0, resetting the counter. But we have to do something with the returned value - decide whether it is larger than the current path as it stands at this element. Hence using max() to choose between the two possibilities.

This gives you a recursive function that iteratively shortens the problem at each step until it finds a base case, at which point it returns - but it returns up through the recursive function, accumulating the results.

(n.b. There are ways to optimize this, clean it up, add default values, etc. I'm skipping that because it doesn't help you think about the recursion.)

Your actual problem is harder. You're going along a two dimensional array. The key insight to have is this: in the iterative step in the example I gave, I looked at all the possible cases for moving forward and chose between them. However, you can go down all possible paths. If you are at a particular element in a two dimensional array, you know that you can go one way or the other - that's two recursive function calls. Because recursion is shortening your problem space, your iterative step can simply trust it will return, and only deal with the results. In your case, that is choosing which of the two recursive calls you made returned the larger result.

(At this point I have to make assumptions about your problem because you included neither a complete specification nor full code.)

def f(matrix: list[list[int], coords: (int, int), current_path: int) -> int:
    # Find all possible 'next steps'. For a next step to be valid it must be exactly one greater than the current location.
    # Base Case - There are no possible next steps -> return current path + 1
    # Increment path
    # Iterative cases
        # There is only one next step -> recurse passing new coordinates and path length
        # There are two or three next steps -> recurse passing new coordinates and path length, then choose which result is the longest.

The difficulty here is that this finds the longest path from any given starting position. To truly find the longest path in the matrix, you would have to add a fourth argument to your function - a list of all the starting positions you have tried. Then you would change your logic for finding the next steps from 'is it strictly one larger' to 'is it strictly one larger or have I not tried starting from that point'?

# Use type aliases so you're clear about the types
type Matrix: list[list[int]]
type Coordinate: (int, int)  # x-y coordinates
type Cache: list[Coordinate]  # All the places we've started from

def f(matrix: Matrix, 
      coords: Coordinate, 
      current_path: int, 
      starting_points: Cache) -> int:
    if 0 == len(matrix):
      return current_path
    if 1 == len(matrix) and 0 == len(matrix[0]):
      return current_path
    current_path = current_path + 1  # From here on, we have a valid element at this coordinate
    if 1 == len(matrix) and 1 == len(matrix[0]):
      return current_Path
    moves = get_all_moves(...)
    if 0 == len(moves):  # This is *also* a base case - the problem cannot be shrunk any further!
      return current_path
    results = try_each_move(moves)  # This is also a recursive function... but a *different* recursive function, in order to avoid using a for loop (or list comprehension)
    return max(max(results), current_path)

A few closing notes:

• Do try to adhere to python style guides. It makes reading python easier!
• Any information you think you need to store outside the function can just be passed as a parameter. Pure recursive functions don't have access to a closure or outer scope. Depending on your case, this may not be the most efficient solution, but it is where you should start until you're much more comfortable with recursion.
• Similarly, if copying a value rather than a reference makes it easier for your to reason about what you're doing, do that first. Efficiency is for later. Clarity first.
• Recursion often (though not always) easier if you're building up a solution from the return of the recursion call. In the examples here, the max() function is doing that accretion, but you could imagine inverting the approach here and first doing the recursive call, which returns two values - the value of the last element and the length of the path. Then you could decide if you're smaller than that value. I didn't do that here because you'd have to remember two path lengths at a time.
• In this specific problem, do take care with the cache. You can't just remember if you've ever visited a coordinate.

What I think you are trying to achieve can be done with recursion:

def recursive(n, p=2, prev=[]):
    productList = []
    for k in range(10**(n-1),10**n):
        if p == 1:
            productList.append([k, k])
        else:
            for product in recursive(n, p=p-1):
                productList.append([k] + product[:-1] + [k*product[-1]])
    return productList

do you need all products to be unique, as this will give (2*4=8) also as (4*2=8)?

The standard structural recursive formula (and the one you'd use if you were using a functional language like Scheme) would be to deconstruct the list recursively:

func([]) => nothing
func([x, ...]) => do_stuff(x), func([...])

Therefore, the "functional" way to do this would be to take a single list (not an index), and to recurse on smaller lists:

def rec_list(l):
    if not l: return # empty list case
    # process l[0]
    return rec_list(l[1:])

Note that this is terribly, terribly inefficient because of the l[1:], but it's the basis for understanding more complex recursive constructs (e.g. recursing on binary trees).

We can do interesting things with this kind of structural recursion. For example, here's how you'd reverse a list in a functional language:

def rev_list(l):
    if not l: return []
    return rev_list(l[1:]) + [l[0]]

(Of course, you could just do l[::-1] in Python, but here we're trying to show how it would be done recursively).

So in a recursive solution you dont use a for loop but instead utilise the functional programing model of using the stack as your loop

def recur_factorial(n):
    total = 1
    if n > 1:
        total = n * recur_factorial(n - 1)
    print(total)
    return total


recur_factorial(5)

OUTPUT

1
2
6
24
120

This hopefully gives you a better idea and if your requirement changes you can just adapt this model to achieve what you need.

UPDATE

Just realised in your comment you said the function needs to return a list of factorials from 2 to n. so below is updated code to return a list.

def recur_factorial(n, factorials=[]):
    if n == 1:
        factorials.append(1)
    else:
        total = n * recur_factorial(n - 1)[-1]
        factorials.append(total)
    return factorials

factorials = recur_factorial(10)
print(factorials)

OUTPUT

[2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800]

def func(my_list, z):

    if z == len(my_list):
        return something
    else:
        # do something else
        return func(my_list, z+1)

z = someValue
print func(my_list, z)    

You should not use list as variable name.

I think the key here is really in just getting used to thinking about recursion and how to solve problems with it. It really is a "work backwards" kind of a solution. With that in mind, let's see if we can develop a recursive solution together.

1. Whenever you're writing something recursive, you're essentially always going to want to start at the end of the problem -- what will or should the behavior of the code be when it is finished, when it has found the answer? What overall environment and inputs should we expect at that final state? And, most importantly, how can we "propagate" our answer back up the call stack without losing anything we care about in the process?

   • First things first: before we can properly get started thinking about or writing any code, we need to make sure we're equipped with the right tools for the job: choosing and preparing the proper data structures (where minor differences in choice can be the difference between hacking away at an incorrect or suboptimal solution for days, or figuring out an elegant and optimal one in a few hours!) The dictionary you've provided as shown here really isn't doing you any favors: the values, as lists of lists, are difficult to check through cleanly and efficiently, Pythonically without a lot of cruft. Personally, I think this particular problem lends itself well to a dict of dicts, i.e.

     d = {
          'dict1': {
              'Movie1': 'Fiction',
              'Movie2': 'Romance'
           },
           etc...
         }
     

     considering that the dict values already form a natural association (in fact, they closely resemble a popular way of instantiating dicts: with a list of (key, value) tuples). If this doesn't seem like your cup of tea, I think another strategic choice would be having parallel dicts of lists -- sharing the same keys, but having one just for movie titles and one just for genres. The lists should be easy to use while coding your solution, but (unlike the nested dictionaries before -- dict_values and dict_keys are implemented as sets behind the scenes) won't make lookup quite as quick...so depending on your use case this would be less preferable. A quick illustrative example:

     movies = {'dict1': ['Movie1', 'Movie2'], 'dict2': ['Movie3']}
     genres = {'dict1': ['Fiction', 'Romance']}
     

     In this set-up, you'd first check through the level of dictionary keys and then the list indices of the value for the matching entry in the corresponding dictionary.

     In general, though, it can really simplify your code and your thought process to not try to cram too many different things (data with different meanings or uses) into the same object rather than having a neat, well-laid plan for utilizing a collection of objects designed to work together, especially if that can be done in a manner so as to not waste a lot of memory.

• Now that we have a general plan (the dict-of-dicts approach first described above) we can return to our original question: where do we end when solving this problem? What is our base case (important terminology as you progress with recursion)? Well, that actually seems trivially easy -- the base case is when we are looking at some collection (a list, set, dict keys or values, what have you) and we find that it contains the movie title we are searching for. So we can already write our base case (partially)

  def recursive_movie_search(movie, db, ...):
      if movie in db:
          return movie, db[movie]
      # Rest of search logic goes here
  

  Notice that because of our choice of data structure, once we've found the movie title we've already got the genre as well, since they're formally associated. We're not quite done yet though, as hinted at by the comment and the ellipsis in the function signature above.

• Here's the last challenge to the recursive technique -- how do we make it so that, by the time we find what we're looking for, we have any and all other information we need to produce our final answer? Often, as in this case, this has to do with cleverly passing along any necessary auxiliary information on our way (down the recursive call stack) to solving the problem. One simple way (not that there's only one!) to finish off the implementation in this case would be something like the following:

  def recursive_movie_search(movie, db, prev=None):
      prev = prev or []
  
      if movie in db:
          return prev.extend((movie, db[movie]]))
      for key in db:
          search = recursive_movie_search(movie, db[key], prev + [key])
          if search: return search
  
      return False
  

Now, to be fair, the problem as you gave it wasn't particularly well-suited to a recursive solution since the searching we needed to do was quite shallow. But the approach above should work with arbitrarily deeply nested dictionaries (then once you get the answer you can decide which of the keys along the path that led to it are significant and worth reporting, or should just be omitted). The only assumption made is that at the bottom level the movie titles will be associated with their genres.

Note also that there are several minor changes you could have made just based on personal choice: instead of accumulating the keys and passing them into the function, this could have been handled simply in the recursive call, e.g. search = key + recursive_movie_search(movie, db[key]) but then this would have required a slightly more thorough check on the next line to ensure that we got a "hit" with that call. Also, you could just as easily return None, an empty list [], or any other item whose boolean value evaluates to False (in the failure case where the movie isn't found) and this logic will work just as well. You just need some kind of flag there to tell you that the search failed -- you could even use a special string that you check for specifically.

P.S. This is my first answer on StackOverflow -- I really hope it helps! And I'm very much open to further questions or feedback on how I can improve :)