I’m having a hard time understanding recursive functions with return statements. I’ve read many other explanations and I’m just not getting it. I’m using the example provided in freeCodeCamp’s Python Tutorial for Beginners (with mini-projects) here with extra print statements to help me understand the work flow, but didn’t help much:
def add_one(num):
print("add_one starting")
if (num >= 9):
print("num is >= 9")
print(num)
return num + 1
total = num + 1
print("num is less than 9")
print(total)
return add_one(total)
newtotal = add_one(0)
print("printing newtotal")
print(newtotal)
What I’m not understanding is why the return in last line in add_one() is necessary instead of just calling the function again without the return. Eventually it will get to the if block and return num + 1, which should be 10, but instead it returns None. Where and when is the return in the last line of add_one() going? Why is it necessary to use return instead of just calling the function again and again until it gets to the if block and returns num + 1 back to the initial call and assigns it to newtotal?
I’m not a hi-tech guy so an explanation in simple terms would help me understand, or maybe a flow chart of what is going on behind the scenes that my print statements are not showing might help.
>>> def add_one(num):
... print("add_one starting")
... if (num >= 9):
... print("num is >= 9")
... print(num)
... return num + 1
... total = num + 1
... print("num is less than 9")
... print(total)
... add_one(total)
...
>>> add_one(0)
add_one starting
num is less than 9
1
add_one starting
num is less than 9
2
add_one starting
num is less than 9
3
add_one starting
num is less than 9
4
add_one starting
num is less than 9
5
add_one starting
num is less than 9
6
add_one starting
num is less than 9
7
add_one starting
num is less than 9
8
add_one starting
num is less than 9
9
add_one starting
num is >= 9
9
The return at the end is not needed.
EDIT:
The return is needed if you need the final value. It’s not needed if you just want to modify the variable in place.
In the place where there is the call to add_one(total) replace it with the entire content of the function.
Do an example in which the recursion is not so deep, like starting with add_one(8)
What you get is the code
print("add_one starting")
if (8 >= 9): # This IF you can delete, since its condition is False
print("num is >= 9")
print(8)
return 8 + 1
total = 8 + 1
print("num is less than 9")
print(9)
return ( # This is not proper Python, but just to visualize
print("add_one starting")
if (9 >= 9): # This IF is entered this time
print("num is >= 9")
print(9)
return 9 + 1 # We exit the parentheses here and give the resulting 10 to the outside
# The next few lines are removed, since we exited in the previous return.
)
If the return were not there, in front of the parentheses, then the value coming out of the call happening in the parenthesis would not go out of the first call to the function.
I guess it depends what you mean by “work”. It prints out the values as a side effect, but it doesn’t return the final answer, which is what I usually want in my functions.
That’s not really happening either, since integers are immutable. At the end of execution, all of the internal variables get cleaned up, and nothing in the global scope was modified.
Thank you for this but, to me, it looks like just another call to the function in the parentheses so I still don’t see why return is necessary if it exits out of the parentheses and returns when it gets to the if block.
If I re-write it as a while loop:
def add_one_v2(num):
print("add_one_v2 starting")
while num <= 9:
print("num is less than or equal to 9, adding 1 to num")
num = num + 1
print(num)
print("add_one_v2 ending")
return num
I only need one return statement. Is the while loop doing something like the return in the original function in the background in that it returns the num to itself to keep iterating through the loop until the condition is False? I just find the while loop much easier to understand and it is shorter. Maybe this isn’t a good example, but is there any instance where we would need to use recursion when a while loop couldn’t do the same thing? Are there any particular applications (AI, game development, data visualization, etc.) that use recursion more than others?
No, you can replace recursion with an iteration together with some way to keep a state. In a recursion the state keeping is done by the computer keeping track of in which function call it is in, all the functions that have been called before and have still to be finished, and with which arguments the functions were called.
Recursion is just a way to write the code that is convenient sometimes. When the solution to a problem has some subproblems that are smaller versions of the same problem, then recursive calls allow you to directly write that idea into code. There is always a way to not have to do recursive calls.
Your example is particularly simple to remove the recursion. So much that it has a name tail recursion. Maybe that is why it looks like the recursion was unnecessary.
The loop takes advantage of mutation to change the value of num from one iteration to the next. The recursive version does not change the value of the variable; it makes another function call to create a new scope where a different instance of the variable gets the updated value.
If you’re calling it without the return, and just put add_one() by itself? It means it’s discarded—you’re saying you don’t need the value. If you want to keep the value, you need to tell it what you’re doing with it:
return add_one(x)
newtotal = add_one(x)
some_list.append(add_one(x))
# or any number or other things
Otherwise, the value just goes away.
Because return always means return to the function that calls it. Your function then just returns it again, but some other function could take the that return value and do something else with it. Another function might just not need the value of the function it called (such as when you call print—you’re calling it for the side effects).
A while loop can do anything recursion can, and vice versa. Sometimes it will make more sense to write it one way, sometimes the other way. In this example, neither one is actually necessary, so, indeed, it probably isn’t a good example. You can find many more examples of both recursion and loops out there.
I think that putting these pieces together has helped me understand. So, if I do understand correctly, I should think of it as nested returns, where the last return that happens in the if block gets returned back up the chain of returns, one by one until it gets back to the initial call within the function that then returns it to the initial call outside the function?
Yes, that’s exactly it. You can think of recursion as a program nesting calls to a function deeper and deeper, each one making the problem a little bit simpler, until it finds a base case that it can solve trivially. The base case returns, and the higher levels will pass it back up the chain (along with whatever additional work they need to perform).
Exactly; you need to keep in mind two separate concepts: the definition of a function, and a call to the function. There can be many separate instances of the function executing at once; each one blocks waiting for the one it called to return.
It might make it a little easier to think about the same function changed slightly to not be recursive. I’ll also remove the calls to print to simplify the logic, and since we’re computing num + 1 either way, we’ll do it once, before we look at the value.
def add_one_nonrecursive(num, f):
total = num + 1
if (num >= 9):
return total
return f(total)
Here’s a function that takes two arguments: a number to add one to, and some … other function: it could be anything. If num is 10 or more, we just add 1 and return that value. Otherwise, we pass num + 1 on to the other function, and return whatever it returns.
So how do we call our new version of add_one? We’ll pass 0 as the first argument, as before. What do we pass for f? Well, comparing to our old version, we want f to behave the same way add_one_nonrecursive did, so we’ll just pass add_one_nonrecursive itself as the second argument!
We could have passed any function as the second argument, but by passing the same function, we get the same behavior as the original recursive function.
Also best not to modify variables that are passed in and expect the caller to know the function has done this, this is a side effect.
Instead, return the modified value. So this function would instead take start_num and declare its a num as a copy of the value start_num, then you modify num leaving start_num alone. This helps to preserve the original value for debugging and leaves the caller value alone (param value num is not owned by this function because this function does not initialise its value so it’s a side effect to modify it).