I am trying to understand this recursive example, how does the if statement evaluate to be true
Thanks
Say you call the function with n equal to 3, obviously the if will be False. Because of this the function returns the value of calling the same function but with n - 1, plus the value of n.
Now the second call to the function has n equal to 2, which still results in the if being False, so it repeat the process of returning n - 1 plus the value of n.
The third call to the function now has n equal to 1, once again failing the if condition and returning n - 1 plus the value of n.
The fourth call to the function has n equal to 0, which has the if equal to True. The fourth call now returns 0 to the third call,
the third call returns 1 + 0 to the second call,
the second call returns 2 + 1 + 0 to the first call,
and finally the first call returns 3 + 2 + 1 + 0 or 6.
It may be worth noting the mathematics take place before the function returns so the actual return values look like:
4th call == 0
3rd call == 1
2nd call == 3
1st call == 6
But don’t worry about the details here too much. Just focus on the basic concept for now.
There is no range function how are you going from 3, 2,1,0 and if the fourth call returns 0 to the third
then if n = 0
the third call will be
0 + (0-1) = -1
Hi,
Try putting print statements inside your recursive statement to see what is happening.
The best thing though is to not only do it by hand, but to try various different things with recursion (like drawing shapes with * asterisks). Recursion is one of those topics that you really have to both practice and be thoughtful about the way you practice it to start getting the hang of it.
@8-bit-gaming is correct in his analysis.
You could try putting the code in a visualizer to help you see how the computer treats recursion: Python Tutor - Visualize Python, Java, JavaScript, C, C++, Ruby code execution
2 Likes
ok will do print statements but how does it go from 3 to 2 to 1 to 0 there is no range function or loop
Play with this
def recursive_function(n):
if n==0:
return
print(n)
recursive_function(n-1)
recursive_function(6)
@jagmeetsond589256300 What on Earth is Recursion? - Computerphile - YouTube
ok l understand the concept l just don’t get how the function is called again minus 1
this part
can be written as this as well right
recursive_function(n) - 1, so
that
recursive_function(n) calls the function again and it starts back up am l right?
Many thanks
Hi,
No, you can’t write recursive_function(n) - 1.
The base case is the condition to stop the recursion, but since the value of n never changes it gets stuck in a loop. In the example I posted it would print the diabolical 6666666.... Yikes!
1 Like
So what makes the function get called again and again
It’s because it’s being called inside of itself.
Python doesn’t use brackets but it’s happening like this:
def r_function(n)
{
r_function(n-1)
}
The fact that within the definition it’s being called means it calls itself.
2 Likes
how did you get this 1
How did you get this 2
Thanks
Learning to use print() for troubleshooting is very important, maybe this will help you:
def recursive_function(n, count=0):
count += 1 #keeps track of how many times the function is called
if n == 0:
print(f'''
Base case of n == 0 has been reached.
function has been called {count} times.
returns will now begin for each function call
\n{count} base case return
''')
return
print(f"n is currently {n} and the function\nhas been called {count} times\n")
recursive_function(n-1, count) #the recursive function call
print(f"{count} return") #this is after the recursive call so it can only occur once n == 0
#this means functions begin to return, without a base case the function
#is called infinite times or until your computer runs out of resources.
recursive_function(6)
2 Likes
Excellent suggestion by @bavarcarus, and I believe @toastedpitabread suggested the same.
Printing information to the console is an excellent way to track the flow of your program.
ok thanks for this bavarcarus, l have gained from it, but l don’t understand the maths, which has not be answered, if someone could help
Thanks
In truth, the only math in that function is the addition on each value. It’s confusing perhaps because we don’t see where that is assigned (since it is returned).
The tricky thing to get one’s head around is that there is no summing until the call stack winds down which begins once the base case is reached. Then the returns are quickly added in sequence so that the final return (the one we see) is the completed sum.
The addition of N terms in a unit sequence (1, 2, …) is known as the nth triangle. The above function will have N returns. We see that as return n + sum_to(n -1).
Printing during recursion might not be very informative since we need the return of the NEXT function call to complete the addition. When we reach the base case, we return 1 which will add to the next item to be popped off the stack, and all the way to the empty stack. This is not math, but an algorithm.
Let’s say N is 7,
N = 7
Within our function we are not able to store any value except the parameter. All we can do is see if we have reached the base case, else,
return n + sum_to(n - 1)
The call stack will look like this (as each return is pushed onto it)…
return 7 + sum_to(7 - 1)
return 6 + sum_to(6 - 1)
return 5 + sum_to(5 - 1)
return 4 + sum_to(4 - 1)
return 3 + sum_to(3 - 1)
return 2 + sum_to(2 - 1)
return 1
The way push and pop work is Last On - First Off. So that means the last return is the first one popped off the stack, and on up to the first one.
One would only advise printing during this process if you know what to expect, and can interpret what you read from the screen. It might do just as well to understand the example above and do the math in your head at each step. It boils down to simple addition.
5 Likes
We can further refine the code using the conditional expression, which is Python’s equivalent of a ternary.
>>> def factorial(n):
return n if n == 1 else n * factorial(n - 1)
>>> factorial(7)
5040
>>>
Same algorithm, similar concept. Instead of adding the unit sequence, we are multiplying. Again, very basic math. The above assumes n is 1 or greater. It is not a complete function since error checking is missing. No checking necessary if values are integer and greater than zero.
4 Likes
Had to circle back to the original question; begging your pardon.
We’ve covered a lot of narrative and should be able to answer this question directly, by now.
The true component is behind the scenes. If..else is the binary representation of a state. If it is something… then do this; else it is something else, so we do that. ELSE is a default action when the expected truthy state is not found. else is only even needed if we have an alternate (default) action. If there is no default action, then else is superfluous.
When 0 or 1 are not that state, then recurse on n - 1, else return 1.
1 Like
so once base case is reached you add 1 upwards to this
giving
7+6+1
5+4+1
4+3+1
3+2+1
2+1+1
1
I saw this video on youtube discussing the same problem, very helpful
Another question l had why do we do
n + sum_to (n - 1) and not
n + (n-1)
Using n - 1 instead has no way to continue the flow since it doesn’t call the function again. Try running the code with it instead. Without the recursion the function can only run once, meaning you only get the sum of the first two numbers returned.