Recursion in Python
Let’s skip the factorial example and the fibonacci examples we’ve all seen those.
Let’s look at recursion in Python using an example based on data discrepancies between 2 temperature sensors
Solve the problem with iteration first!
If you can solve the problem with recursion you can solve it with iteration and vice versa.
Recursion is great for trees and backtracking so still well worth learning.
For this article we’ll solve the problem with a for loop first and then we’ll break it down into a recursion example.
Below we can see the counter is increasing as we iterate through the elements of the array:
code: https://github.com/RGGH/recursion/blob/main/noteboobs/arrdiff.ipynb
Recursion version
A way to break down the problem to make recursion code easier to write is to solve just the difference of last element of the arrays.
This will be the variable that gets added to our recursive function call. “last_ele_diff“
Once we have the last_ele_diff we then add the function inside the function to do the actual recursion, and then add the last element ‘last_ele_diff‘ to give us our answer.
If you watch the video on YouTube you can see me debug the stack frames for this which shows how the stack unwinds.
-> This gives the same (correct) answer as the iterative example that we got when we used the for loop.
NB. I accidentally left “count = 0” in the code. It’s not needed.
You can try the code and watch it do the recursion in the debugger here
Summary
We’ve used an example where we perform 1 part of the problem, and remove it from the end, and then reduce the size of the original problem by 1.
When the stack unwinds it adds up the differences until it gets back to the final one.
