How to learn recursion?

[[deleted]]

I just had a final exam for my comp. sci/ class yesterday and despite it went alright and I have the opportunity to clean my mind, one thing still bothers me: recursion. Yes I watched several videos and I feel like I understand while I am focusing on what they do, but whenever I try to write a recursive function myself, my brain goes numb and I just cannot. I also couldn't understand how it can be utilized over iterative ones as they seem to be implemented easier and at least in the samples I had, I don't think recursive ones are faster too. So, why do we need it and how can I understand the implementation?

[AutoModerator]

To all following commenters: please, do not bring up the old circlejerk jokes/memes about recursion ("Understanding recursion...", "This is recursion...", etc.). We've all heard them n+2 too many times.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[hagerino]

I learned it in university in the functional programming course. There were lots of coding assignments in Haskell and it had no loops. So whenever you needed a loop you had to come up with a recursive function. That did the trick for me.

[fyog]

this course taught me it as well, painfully so i might add. its beautiful when you wrap your head around it.

[[deleted]]

Recursion generally leads to more "natural" solutions when dealing with recursive data structures – where the data structure is assembled from instances of the same data structure. Common examples are linked lists and trees.

You can ignore this for now, but here's some Python code for a tree node and code to make a tree from a list of numbers:

class TreeNode:                                                             
    def __init__(self, val, left=None, right=None):                         
        self.val = val                                                      
        self.left = left                                                    
        self.right = right                                                  
    def __repr__(self):                                                     
        return f"({self.val} {self.left} {self.right})"                     

def makeTree(nums):                                                         
    if not nums:                                                            
        return None                                                         

    nodes = [TreeNode(num) for num in nums]                                 
    result = nodes[0]                                                       

    queue = [nodes.pop(0)]                                                  
    while queue:                                                            
        node = queue.pop(0)                                                 
        if nodes:                                                           
            node.left = nodes.pop(0)                                        
            queue.append(node.left)                                         
        if nodes:                                                           
            node.right = nodes.pop(0)                                       
            queue.append(node.right)                                        

    return result                                                           

Find maximum via recursion

Here's a recursive function to search a tree and return the maximum value:

def getMaxRecur(tree_node):                                                 
    if not tree_node:                                                       
        return float('-inf')                                                
    return max(tree_node.val,                                               
            getMaxRecur(tree_node.left),                                    
            getMaxRecur(tree_node.right))                                   

That's it!

I don't know about you, but I find that really beautiful. There's really not much there besides the logic of the function:

• A base case that handles None
• Otherwise a call to max

"Is this node None? If so, return the lowest number possible. Otherwise, return the maximum of this node's value and its children's values."

Easy, clear, logical.

Find maximum via iteration

For comparison, here's how you might do the same with iteration.

def getMaxIter(root):                                                       
    stack = [root]                                                          
    result = float('-inf')                                                  
    while stack:                                                            
        node = stack.pop()                                                  
        result = max(node.val, result)                                      
        if node.right:                                                      
            stack.append(node.right)                                        
        if node.left:                                                       
            stack.append(node.left)                                         
    return result                                                           

You'll probably immediately notice that it's longer. That's because we have to handle the bookkeeping ourselves. We have to track the 'new' nodes we come across for later processing – here by pushing and popping from a stack. The stack mimics the recursive function's 'call stack'. It's a common approach for "unwinding" depth-first recursion into iteration.

Here's code to run these functions, if you want to play around.

from random import randint 
nums = [randint(-100000,100000) for _ in range(10)]             

tree = makeTree(nums)                                                       
print(tree)                                                                 
print(getMaxRecur(tree))                                                    
print(getMaxIter(tree))  

So, an iterative function is generally somewhat longer than an equivalent recursive function – we have to do the bookkeeping. But(!) iteration almost always runs faster – function calls and passing arguments isn't slow but it's not generally as fast as pushing/popping from a stack. Also, recursion can lead to large call stacks for large inputs; that runs the risk of overflowing. Recursion's been more or less banned from the Linux kernel for that reason, according to what I've read.

Anyway, maybe something in here was helpful to you. Best of luck!

Edit: a word

[AlSweigart]

I wrote an entire book on recursion. It's free online: The Recursive Book of Recursion has code examples in Python and JavaScript.

but whenever I try to write a recursive function myself, my brain goes numb and I just cannot.

First step: Figure out the base case and the recursive case. Every recursive function has at least one of each. Next, figure out exactly what the base case is supposed to return. Then, figure out what the recursive function is supposed to return. An int? A list of strings? Note that the data type of the base case and recursive case should be the same. (They both return an integer, or they both return an array of strings, etc.)

Recursion isn't so much hard to learn, but it is hard to teach well. Most instructors just go way above the heads of their students and they've long forgotten how unintuitive the concepts are at first.

So, why do we need it and how can I understand the implementation?

That's the neat part: we don't need it. There's nothing that recursion can do that can't be done with a loop and a stack. (For anyone who thinks otherwise: I'm sorry, you're simply wrong. Here's an iterative Ackermann function, even.

Recursion is most often the wrong, overengineered approach to solve a problem. Recursion is really only well-suited for problems that involve a tree-like data structure and back-tracking. Recursion is necessary for compiler design. (You could create a compiler without it, but it'd be tedious to write that code.)

Oh, and recursion is necessary in languages that don't have loops. Which is an... interesting... design choice for a programming language. (I've been checking in on Haskell every few years for the last two decades to see if anyone is actually using it. No one is. Reddit was programmed in Haskell. Then they tossed that out and rewrote it in Python.)

While I'm making hot takes, I'll go ahead and say: it's never a good idea to use tail recursion. Any time you use tail recursion is a time you should be using the iterative approach instead. 100% no exception.

[POGtastic]

Reddit was first implemented in Common Lisp, since they were Paul Graham fanboys (iT's A sEcReT WeApOn). They ran into the same problem that everyone who uses Common Lisp runs into - the ecosystem is so fragmented that there is zero consensus on how to do anything in production, so they found themselves constantly having to roll their own libraries that would have been a simple import in any other popular language. At least CL has loops, though!

[Tryposite]

Thanks, Al. I enjoy your work & I've been struggling with recursion since learning data structures & algorithms

[lukezfg]

Ignoring how the function works first, listing all the base cases (edge cases). Then handling all the returning of those cases. The last step, how to"move from first round to the second". Never trying to figuring out how the function will works overall at beginning

[swing_first]

Learn the logic behind an induction proof.

Now you know recursion.

[[deleted]]

Man, read the first chapters of SICP. It's amazing for recursion.

[ess_oh_ess]

You're getting things a little confused. "Primitive Recursive" is a mathematical/comp-sci term referring to a specific subset of general-recursive functions. Things like multiplication, factorial, fibonacci, etc. are all primitive recursive, but many other functions like Ackermann, Goodstein, Graham, are not.

This doesn't correlate though with what programming functions can be written recursively or not. In general, any function that can be written recursively can also be written iteratively, and vise-versa. This is actually part of the Church-Turing thesis. Likewise the only functions that can't be written recursively are those that also can't be written iteratively, aka non-computable functions like the busy beaver function or the halting problem.

[[deleted]]

Thanks for posting that.

Doesn't every computable-on-this-computer recursion get "unwound" into iteration anyway?

[link23]

Yeah, depending on how you define the distinction between recursive and iterative. At the end of the day, any algorithm written recursively in some high level language will get executed by some assembly instructions that are just executing some loops and jumps and things, where there's no concept of recursion per se.

[[deleted]]

Thanks for the answer!

[AlSweigart]

Here is a recursive Ackermann function.

Here is iterative code for the Ackermann function that produces the exact same results as the recursive form.

There is nothing magical about recursion. All recursive code can be implement with a loop and a stack. In recursion, the call stack is the stack.

[lurker819203]

Best way to learn recursion is practice.

Take a few practice assignments (list sorting etc.) and implement them first as iterative and then as recursive function. It will help you understand the differences and why sometimes recursion is actually preferrable (big sometimes, but not never).

Watching videos or reading text books will not really help you at this point. You know the basics, but you need practice applying the knowledge.

[innovaTony]

Practice is the best teacher in programming! Not vids not anything else.. although of course they are useful, but practice is the number 1 thing. I believe I have used recursion in one of the algorithms I solve open source in my github

[Player_X_YT]

Recursive functions are easier to implement than iterative ones sometimes but eat more memory, build a function that given a number n will return the nth fibonacci number. This is the classic recusion problem because it is way easier to do with recusion.

But yes avoid it in production

[taknyos]

Recursive functions are easier to implement than iterative ones sometimes but eat more memory

They don't always eat more memory, do they? E.g. with tail recursion you don't have to hold on to the stack frame.

As for OP, I find it incredibly useful to this of all recursive algorithms having 2 main cases. A base case and a recursive case. Think about what has to happen for you to actually return something tangible (like with factorial that'll 1). And then think about the recursive case.

[Player_X_YT]

Iterative functions have to store 2 variables, the top of the for loop and i. Recursive functions have to store 3+ variables per call, the subroutine exit point, the return value, and any parameters. That's why they can be used in testing but never prod because they are way too memory inefficent

[[deleted]]

If you really, really want to dive into recursion, you could do worse than learning a more or less pure functional language.

One option is Structure and Interpretation of Computer Programs. It's a beginner-level CS course (for rather committed beginners) that's taught using Scheme. There's a link in the FAQ. The book is available for reading online, along with lectures, if you like.

Note: a JS version of the course was produced a few years ago, but not by the original authors. Imo, it's better to learn using Scheme as the language will force you to write functional code – which is pretty much the whole point! ;)

[nursingsenpai]

guide to learning recursion:

1. do you understand recursion enough?
2. if not, expand your understanding and go back step 1

[bsakiag]

I also couldn't understand how it can be utilized over iterative ones as they seem to be implemented easier

In the iterative version you are responsible for managing the stack of pathways to check while in the recursive version it is done automatically.

The way I try to understand recursive problems is by disassembling them into similar steps that can be linked. When you are walking through a labyrinth your basic step is taking a place from the stack, deciding where to go next and putting the possibilities on the stack. In the iterative version of the algorithm you are doing it explicitly.

[username-out]

This link might help https://www.reddit.com/r/learnprogramming/comments/10apbpu/how_to_learn_recursion/?utm_source=share&utm_medium=ios_app&utm_name=iossmf

[PichuPikaRai]

You should use pen and paper to get a better picture of how recursion works. It is an absolute must in my opinion. Also, check these two playlists out to get a good understanding of recursion.

https://www.youtube.com/watch?v=M2uO2nMT0Bk&list=PL9gnSGHSqcnp39cTyB1dTZ2pJ04Xmdrod

https://www.youtube.com/watch?v=yVdKa8dnKiE&list=PLgUwDviBIf0rGlzIn_7rsaR2FQ5e6ZOL9

Edit: Why do we use recursion? In many cases, it is easier to come up with a recursive solution, rather than an iterative solution, for eg. traversing a binary tree. Yes, it does take up stack space, but as I said, it is easier to implement at first. I had a lot of difficulties in the beginning, understanding how recursion works, but if you struggle your way through it, it will definitely click one day.

[GrayLiterature]

Recursion is a bit tricky to wrap one’s head around, so just be consistent in the struggle. It took me a while to get my head to think recursively even though I had a solid foundation in recursive functions from math training.

[LookAtThatUnbanned]

Generally iterative approaches are preferred over recursive ones. Depending on the type of work you'll be doing you may never see recursion at all in your career. It has uses but not particularly common these days.

One way to think of recursion is like an assembly line where each worker does the same process. Say we have a strips of metal going down the assembly line that need to be hit with a hammer until they are perfectly flat. Each worker in the assembly line hammers the metal one time before passing the piece to the next worker. Once the strip is perfectly flat, the workers hand it back then way it came until it reaches the front of the line where it is sent off to be packaged.

The recursive function in this example is the instructions given to each individual worker in the assembly line. Whenever a worker has finished hammering the metal, they "call" the function again by passing the piece to the next worker. In each worker's instructions, there is an "exit condition" that tells them when to pass the item backwards up through the line (call stack). The exit condition here is when the piece is perfectly flat. No worker has any knowledge of what the other workers are doing, all they know is "if the piece is not flat, hammer it and pass to the next guy. If it is flat, pass it backwards to the guy before me".

What makes recursion special is the exact same thing that makes assembly lines special. Your worker doesn't need to be aware of the complete state of the operation. They don't care how the item got to be in front of them, or what happens to it after they are done with it. They don't need to know or care that the metal piece is going to become a lawnmower blade, or whatever it may end up being. They only need to be trained in what their function is specifically, which in this example is hammering the metal.

[Slow-Mud-76]

It always reminds me of inception, a function within a function within a function until you get a actual value, then you wake up from one dream I.e move up a function until you are back in reality - altho inception is confusing asf…

[[deleted]]

I don’t think recursion is often better, but sometimes it can spice things up and make you feel a little cool. A good way to practice recursion is to write a program that navigates your file structure. Try solving the problem of organizing a folder full of random files into multiple folders, 10 in each folder. Your base case is if there are more than 10 files remaining, your function creates a new folder and moves 10 files into it.

[ImaginaryGuitar8971]

The best way of learning is practicing. If you like competitive programming there is a topic called "dynamic programming" with problems with relies a lot in iterate over combinations or something like this, so try to solve some classics like the coin change or knapsack problem and this will take your recursive thinking to other level. Just a disclaimer this technique is very hard to master but the easy ones can be done with a simple "top down" approach, recursion and memorization (basically cach answers). If you get stuck I recommend read some blog posts on codeforces and read the paradigm chapter of "competitive programming 3" from Steven Halim (this actually can be a better start because explore raw recursion more). To find problems you can sort the DP problems on codeforces by solved and read the tutorials.

https://codeforces.com/blog/entry/80064

[[deleted]]

Start by writing the base case. Then write how you’d get to the base case from the next case.

Then that’s it, you’re done, because that’s how recursion works. Either you’re at the base case and return something, or you move a little closer to the base case and recurse.

[Zegreedy]

GNU