Actually you should break the function down first:
A loop has a few parts:
the header, and processing before the loop. May declare some new variables
the condition, when to stop the loop.
the actual loop body. It changes some of the header's variables and/or the parameters passed in.
the tail; what happens after the loop and return result.
Or to write it out:
foo_iterative(params){
header
while(condition){
loop_body
}
return tail
}
Using these blocks to make a recursive call is pretty straightforward:
foo_recursive(params){
header
return foo_recursion(params, header_vars)
}
foo_recursion(params, header_vars){
if(!condition){
return tail
}
loop_body
return foo_recursion(params, modified_header_vars)
}
Et voilà; a tail recursive version of any loop. breaks and continues in the loop body will still have to be replaced with return tail and return foo_recursion(params, modified_header_vars) as needed but that is simple enough.
Going the other way is more complicated; in part because there can be multiple recursive calls. This means that each time we pop a stack frame there can be multiple places where we need to continue. Also there may be variables that we need to save across the recursive call and the original parameters of the call.
We can use a switch to work around that:
bar_recurse(params){
if(baseCase){
finalize
return
}
body1
bar_recurse(mod_params)
body2
bar_recurse(mod_params)
body3
}
bar_iterative(params){
stack.push({init, params})
while(!stack.empty){
stackFrame = stack.pop()
switch(stackFrame.resumPoint){
case init:
if(baseCase){
finalize
break;
}
body1
stack.push({resum1, params, variables})
stack.push({init, modified_params})
break;
case resum1:
body2
stack.push({resum2, params, variables})
stack.push({init, modified_params})
break;
case resum2:
body3
break;
}
}
}
Actually you should break the function down first:
A loop has a few parts:
the header, and processing before the loop. May declare some new variables
the condition, when to stop the loop.
the actual loop body. It changes some of the header's variables and/or the parameters passed in.
the tail; what happens after the loop and return result.
Or to write it out:
foo_iterative(params){
header
while(condition){
loop_body
}
return tail
}
Using these blocks to make a recursive call is pretty straightforward:
foo_recursive(params){
header
return foo_recursion(params, header_vars)
}
foo_recursion(params, header_vars){
if(!condition){
return tail
}
loop_body
return foo_recursion(params, modified_header_vars)
}
Et voilà; a tail recursive version of any loop. breaks and continues in the loop body will still have to be replaced with return tail and return foo_recursion(params, modified_header_vars) as needed but that is simple enough.
Going the other way is more complicated; in part because there can be multiple recursive calls. This means that each time we pop a stack frame there can be multiple places where we need to continue. Also there may be variables that we need to save across the recursive call and the original parameters of the call.
We can use a switch to work around that:
bar_recurse(params){
if(baseCase){
finalize
return
}
body1
bar_recurse(mod_params)
body2
bar_recurse(mod_params)
body3
}
bar_iterative(params){
stack.push({init, params})
while(!stack.empty){
stackFrame = stack.pop()
switch(stackFrame.resumPoint){
case init:
if(baseCase){
finalize
break;
}
body1
stack.push({resum1, params, variables})
stack.push({init, modified_params})
break;
case resum1:
body2
stack.push({resum2, params, variables})
stack.push({init, modified_params})
break;
case resum2:
body3
break;
}
}
}
Following up on @ratchet freak's answer, I created this example of how the Fibonacci function can be rewritten to a while loop in Java. Note that There's a much simpler (and efficient) way to rewrite the Fibonacci with a while loop though.
class CallContext { //this class is similar to the stack frame
Object[] args;
List<Object> vars = new LinkedList<>();
int resumePoint = 0;
public CallContext(Object[] args) {
this.args = args;
}
}
static int fibonacci(int fibNumber) {
Deque<CallContext> callStack = new LinkedList<>();
callStack.add(new CallContext(new Object[]{fibNumber}));
Object lastReturn = null; //value of last object returned (when stack frame was dropped)
while (!callStack.isEmpty()) {
CallContext callContext = callStack.peekLast();
Object[] args = callContext.args;
//actual logic starts here
int arg = (int) args[0];
if (arg == 0 || arg == 1) {
lastReturn = arg;
callStack.removeLast();
} else {
switch (callContext.resumePoint) {
case 0: //calculate fib(n-1)
callStack.add(new CallContext(new Object[]{arg - 1}));
callContext.resumePoint++;
break;
case 1: //calculate fib(n-2)
callContext.vars.add(lastReturn); //fib1
callStack.add(new CallContext(new Object[]{arg - 2}));
callContext.resumePoint++;
break;
case 2: // fib(n-1) + fib(n-2)
callContext.vars.add(lastReturn); //fib2
lastReturn = (int) callContext.vars.get(0) + (int) callContext.vars.get(1);
callStack.removeLast();
break;
}
}
}
return (int) lastReturn;
}
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
I managed to do so by defining the following function:
def ric(find, n, c):
if n < len(find):
if find[n] in find:
c += 1
n += 1
return ric(find, n, c)
else:
return c
and calling it with ric(find, 0, 0)
python - How to use recursion for "for" loops - Stack Overflow
loops - Recursive looping function in Python - Stack Overflow
Converting a for loop to recursion in Python - Stack Overflow
python - Recursive for loop - Stack Overflow
Videos
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.
Recursion is just a function that keeps calling itself until it reaches a condition that disallows it from continuing.
Here's an example that's themed toward your needs.
""" Emulation Of:
for row in range (len(matrix)):
for col in range (len(matrix[0])):
print(matrix[row][col])
"""
matrix = [[1,2,3],[4,5,6],[7,8,9]]
#wrapping everything in this function makes `i` unreachable
#because it should be managed internally
def process_matrix(r:int, c:int) -> None:
def columns(i:int=0, r:int=0) -> None:
if i==c: return #columns finished
print(matrix[r][i]) #work
columns(i+1, r) #next column
def rows(i:int=0) -> None:
if i==r: return #rows finished
columns(0, i) #recurse all columns for this row
rows(i+1) #next row
rows(0) #start recursion
#use
process_matrix(len(matrix), len(matrix[0]))
If you are trying to retrieve data, you have to return the "recursion call". Otherwise, you'll get None back from the very first call, and the recursion will carry on in a way that is unreachable by your code.
data = [10,20,30,40,50,60]
def where_is_50(i:int=0) -> int:
if data[i] == 50:
return i #stop recursion
return where_is_50(i+1) #next
print(where_is_50())
If it isn't clear, The first time the function is called, it is not 50 so, it returns a call to itself. However, the actual return can't finish until the call does. Essentially, you end up with a string of "active" functions that are all waiting for the call that finds 50. When 50 is found, the return value keeps ascending through all the calls back to the very first one.
Whatever recursive functions you make should have a local reference to the data to traverse. In other words, don't pass your entire matrix on each call. Pass names or indexes recursively.
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
I generally avoid recursion like the plague in python because it's slow and because of the whole stack overflow error thing.
def collect_folders(start):
stack = [start.id]
folder_ids = []
while stack:
cur_id = stack.pop()
folder_ids.append(cur_id)
stack.extend(folder.id for folder in getChildFolders(cur_id))
return folder_ids
This assumes that getChildFolders returns an empty list when there are no children. If it does something else, like return a sentinel value or raise an exception, then modifications will have to be made.
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.
You should have a look at the builtin package itertools:
for a,b,c,d in itertools.product(range(10),range(10),range(10),range(10)):
if (a*b*c*d)%6==0:
allProducts.append(a*b*c*d)
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 batteries for this in SymPy are already included:
from sympy.utilities.iterables import subsets
from sympy.core.mul import prod
numbers = [1, 2, 3] # or whatever factors you want
p = 2 # how many factors you want
for n in subsets(numbers, p, repetition=True):
print(n + (prod(n),))
This outputs
(1, 1, 1)
(1, 2, 2)
(1, 3, 3)
(2, 2, 4)
(2, 3, 6)
(3, 3, 9)
This is different from cartes (or product) in that you won't get permutations of the factors, e.g. the latter would also give (2, 1, 2), a permutation of (1, 2, 2). You can read more about subsets using help(subsets) in SymPy and you can read the source if you want to.
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.
- 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_valuesanddict_keysare 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,dictkeys 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 hereNotice 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 :)
Assuming that your given structure does not change for other cases, I think this is what you are looking for:
dic = {
"dict1": [["Movie1", "Fiction"], ["Movie2", "Romance"]],
"dict2": [["Movie3", "Comedy"]],
}
def rec_search(data, movie_name):
if isinstance(data, dict):
for key in data.keys():
result = rec_search(data[key], movie_name)
if isinstance(result, tuple):
return f"found in {key}; Title: {result[0]}; Genre: {result[1]}"
return None
elif isinstance(data, list):
for element in data:
if isinstance(element, str):
if element == movie_name:
return element
else:
result = rec_search(element, movie_name)
if result:
return (result, element[1])
return None
print(rec_search(dic, "Movie2"))
Hey guys, I'm pretty new to python and I'd like to practice using Recursion in my code to further assist my understandings with the recursive function. From what I am aware of, identifying a base case is required to prevent infinite recursion but I cannot seem to figure out the base case for this scenario.
Simplified code as shown below:
for y in range(N):
for x in range(M):
if origin[x][y] == 1 and CellsMap[x][y] == 0:
CellsCounter += 1
DiscoverCells(origin, x, y, CellsCounter) Basically the above code will scan for every (x, y) coordinate in a grid (Implemented by the nested For Loop)
How do I go about converting this code into recursion, with a call to function of def DiscoverCells()?
Thanks in advance!!
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
Your function is needlessly complicated. The return value is never used. You also print from the end of the list, which is a bit odd: tail recursion is a more usual style. For example:
def printCollection(c):
if c:
print c[0]
printCollection(c[1:])
This still has the flaw that it copies the list for every element in the list, making it an O(n^2) function. It's also limited to data structures that use slices and indices. Here's a recursive version that prints any iterable:
def printCollection(c):
it = iter(c)
try:
el = it.next()
print el
printCollection(it)
except StopIteration:
pass
It's still a bit odd to recurse here as this is a naturally iterative problem.
So I was watching this video on youtube and was simply amazed by this function to calculate factorials with recursions.
def factorials(n):
if n == 1:
return 1
else:
return n * factorial(n-1)Since I'm pretty new to python and coding in general (I'm a lawyer by profession), I would have solved this problem with loops. The moment I understood the concept of this function, I was baffled by the simplicity and beauty of it.
Now here's my question:
-
In which cases is it smarter to use one or the other and what are the benefits? (if there even is a general rule)
-
Where can I learn more about recursions? Are there any tutorials online?
Thanks :)
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 you want to do away with a nice (mostly) well coded loop? (mostly because you probably want to use enumerate instead of range(len(lst))) -- enumerate is pretty cool, once you start using it, you'll never look back.
Anyway, I guess we can do that:
def silly_loop(lst,index=0):
try:
#do something with index and lst here
silly_loop(lst,index=index+1)
except IndexError: #or maybe a different error, depending on what you're doing with index ...
return
an example:
def silly_loop(lst,index=0):
try:
print lst[index]
silly_loop(lst,index=index+1)
except IndexError:
return
a = range(10)
silly_loop(a)
Note that I can't think of ANY reason why you would want to do this in real code, (But, if you're just doing this to teach yourself about recursion, then I hope this helps).