I’d like some more resources on recursive functions that are easy to follow and show practical examples. After doing some digging on the topic for the Sum All Odd Fibonacci Numbers exercise, I’ve got a grasp of the basics. I’ve watched a few videos that explain it, including one that uses recursion to create an object tree.
It’s clear to me that recursion is a core concept of functional programming, but I’m still not 100% on when you should use a recursive function, and how to go about conceptualizing one. It took me a while to wrap my head around using a recursive function to find the Greatest Common Divisor of two numbers using Euclid’s Algorithm, and I wouldn’t know how to begin writing a recursive function to do something more than just count backwards.
With recursion you look for a pattern that refers to the same problem in some way.
You identify how you can go from one problem to a smaller problem, or from a smaller problem to a larger problem.
When we see the fibonacci numbers, or the towers of hanoi puzzle, we can see there’s a solution based on smaller problems.
We can say the nth fibaonacci number is based on the n-1th and n-2th number, so given those ones we can get the nth one
We can see that for the towers of hanoi puzzle, if we can move n-1 disks to the third peg, the nth disk to the middle peg, and then solve the n-1 disks puzzle from the third peg to the middle, we have won. So if we have a way of solving n-1 disks, we have an immediate solution for n disks.
Both of these then have a base case we can trivially solve. In the case of the towers of hanoi puzzle, this is the single disk problem, which is trivial.
So to come up with a recursive algorithm then simply involves spotting a pattern, which isn’t itself easy, but the more familiar you become the easier that’ll be
As for when to use recursion, it’s like when to use any algorithm really, so it’s quite a difficult thing to answer.
Does using a recursive algorithm simplify the problem and code? In the case of traversing a tree it may certainly do so.
It’s important to note that many languages don’t support certain types of optimization for recursive function calls, and recursive function calls may then suffer a very large performance penalty.
Many types of recursive problems (but not all) can be done with explicit stacks or other data structures that can move away from recursive function calls but still retain the recursive algorithm in some way.
So as for when to use it, unfortunately less than I’d personally like, but always be aware than it’s just another problem solving tool that’s available for you to use
but I’m still not 100% on when you should use a recursive function, and how to go about conceptualizing one.
When you need to execute the SAME series of steps repeatedly, you can either use recursion or iteration (for loop, while loop, etc).
The difference between the (2) is that in recursion, the method/function you called upon to execute will also call “itself”… which will then call “itself” again, so on and so on. That’s why it’s called recursion.
That pattern is not something you see in iteration, where in your loop (that contains the steps of instructions you want executed) have to iterate a certain number of times, or when a certain condition is met.
In recursion, you cannot keep on calling itself, ad infinity, or your program/computer will hang/crash. Same with iteration, a condition must be met to end the loop. With recursion, a condition must be met to exit the function and therefore stop calling itself.
Problems can be solved using either method. But recursion may require shorter code solutions vs. iteration/loops.
For example, try this: Print a string “Your name” 10 times on your screen without using a for-loop, but instead recursion.
Thanks for the replies. So there isn’t a hard and fast rule for when to use recursion over loops, but will depend on the problem.
I get the feeling that having a firm grounding in math would be helpful. However, I don’t have a math foundation. Should I begin studying certain branches of math to better prepare myself for the kinds of problems web developers face?
It’s probably more important to be familiar with algorithms’ and data structures’ performance characteristics than the mathematics backing it first I think, but it’s important to learn later
That might be a controversial opinion though, I’ve seen people range in opinions from it not being important at all for basic web development to saying it’s fundamental knowledge that all should know in the profession
It doesn’t need a math background, you just need to think about it slightly differently. A key reason it is used in functional programming so much is that functional languages depend heavily on immutability. You often can’t have a JS-like for loop: that implies a mutable value for the counter, so you have to use recursion if you want to manually loop over things (rather than using library functions like map, reduce etc).
(Mandatory 20 character limit)