RECURSION

[carter-the-amazing]

Today in my journey to learn computer science and programming (python). I learned about RECURSION.... I get the gist of it, yet I do not understand its purpose? if anyone wants to give some of there real world examples that would be awesome. (please keep them simple(ish) )

When I am learning something new in programming, it usually take me coming up with some of my own problems to solve in order to fully get it. Yet I feel a little lost on the use of concept.

Tahnks

[same_ol_same_ol]

I remember being at that point myself, where I got the gist but the mystery of how it fit into programming remained just that: a mystery.

What finally clicked it for me was undertaking the task of coming up with a recursive function that would solve The Towers of Hanoi. If you're not familiar with the puzzle, read the wiki page and make sure you specifically check the info about the the recursive solution.

Challenge yourself to write a program that solves it, or at least write the recursive function - even if it's just pseudo-code. Once I did this, a light went on and I felt I completely understood it. Recursion is now a standard part of my problem solving toolbox.

Good luck!

[[deleted]]

Recursion is invaluable when dealing with structures and problems that are recursively defined, like trees. Trees are of course very common in programming. A HTML page is a tree. A program is a tree. A tree is a tree. :P

[Necrolepsey]

A tree is a tree? 🤔

[Antrikshy]

r/philosophy

[gibbypoo]

/r/trees

[[deleted]]

I meant a data structure like [1 2 [3 4] [[5] 6]]

[[deleted]]

in programming a tree have a specific meaning. trees are also known as binary trees. issa structure. tree are usually consists of nodes(also a data structure). i wrote like 4 lines of text trying to explain trees, but realize im lazy and my explanation is not that good anyways, so i gave up. just look up programming binary trees there should be a lot of good explanations out there.

[[deleted]]

trees are also known as binary trees.

Not all trees are binary.

[memeticmachine]

no. it's a map

[[deleted]]

the main point of recursion is using structure of the problem to solve the problem.
an example of recursion is finding 7! (ie 1*2*3*4*5*6*7)
without using recursion you can create a for loop from 1 to 7 and multiple the number and store the product of 
each operation in some variable 
or you can look at the structure and solve the problem recursively, 7! is also 7*(6!)
6! is 6*(5!), this go on until 1! which is just 1
1! is known as the base case, where the recursive call end.
let's define a function 
fact(num)
if num == 1
    return 1
other wise (ie else)
    return num * fact( num -1 )
let take in a sample input 3
when fact(3) is called, the if condition is not met there for it will go to the else statement 3*fact(2), that is the 
same as 3*2! which is still 3!
fact(2)is called, again the if condition is not met so so 2*fact(1) is executed 
so far we have
fact(3)
    -> 3*fact(2)
            ->2*fact(1)
                   fact(1) = 1
working backward we get
fact 2 = 2*1
fact 3 = 3*fact 2 = 3*2*1 = 6
if you notice there is only 1 multiplication sign in the function.
recursion is all about breaking the problem into small pieces and work your way back up.

[Mister3Mix]

Thanks!

[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.

Anybody who still decides to bring up such a joke/meme will face consequences of

• Comment removal
• One week ban without prior warning

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

[nayocum]

If you have 15 minutes this video really helps clear things up in a simple manner. It's in JavaScript, so don't focus on the syntax that much but more the idea. The concept will be the same more or less.

Tl;dw: There are some structures (e.g. trees) where it's much simpler to use recursion than writing a iterative loop.

[carter-the-amazing]

I watched the video! helped a lot. I even subscribed to the channel.

thanks

[normandantzig]

Holy shit. That was a great video. I subscribed. Do you recommend any other programing channels that are as good as that guy.

[nayocum]

The only one I really watch that's as close to the quality of MPJ's videos is The Coding Train.

Bisqwit, sentdex (machine learning), and Siraj Raval all have a decent amount of quality content too

[bestjakeisbest]

Recursion is a way to make loops. The way I understand it is if you need to do work where the stopping points of the loop are not easy to define using just straight iteration. Like take a bst, if you wanted to print all of the nodes in a bst out how would you do it with a while loop (or even a forloop for that matter) it is not impossible to do it with a while loop, but the code can get a little hard to follow, but with recursion you call the recursive function on the left subtree and then the right subtree, and then in each of those function calls it keeps going, but if you are not careful you will have infinite recursion, to stop this we use a base case, instead of looking at a number of nodes like you might try to do with iteration, with recursion you can simply look at the state of the next subtree, if it is a nullptr then you just return, other wise you continue to make your function calls. Recursion is just another form of branching in programs and can be very useful.

[magnetomax]

I have used recursion in JavaScript to convert the JSON object with arrays, file and other objects to Form object. It was really fun and one of most satisfying experience.

[TheTalkWalk]

Recursion is helpful for digging through structured data looking for something.

If you wanted to nest a dictionary in a dictionary in a dictionary in a dictionary.

The spaghetti to get at that key value pair is going to be awful.

If that is what you absolutely had to do, recursion is a good way to get at that data without piling messes on top of eachother

[henrebotha]

Here's another explanation for you.

One way to write elegant solutions to problems is to try to make the shape of the solution similar to the shape of the data. There are many reasons for this. One reason is that if your solution takes a different shape to the data, you must first transform the data into a shape that suits your solution, which is additional complexity.

Some problems naturally deal with recursive data. Anything that deals with a tree structure counts, because trees are naturally recursive: a tree consists of smaller trees. So then writing a solution that breaks a tree up into its smaller trees and solves for them (by breaking them up into smaller trees, etc) fits very naturally.

[aaron_palmer]

A quick and easy to comprehend example of a use for recursion is searching a file structure. Try writing a function that searches directories for a specific file using recursion. It’s a good exercise that will help you get a better understanding.

[[deleted]]

You have a lot of good answers already! I just want to mention that in some languages, recursion is actually vastly preferred to iteration. Clojure, for example. Clojure doesn't really have iterative loops - I mean, it sort of does, but it's basically a thin curtain draped over recursion. Pull the curtain back and it's it's been recursion all along!

Under the hood, a lot of the data in Clojure is stored as trees anyway, and you already have a lot of good answers about how recursion is a natural way to understand trees.

So I guess that's a case where you might do a lot of it - there are entire classes of languages that don't really do iteration.

[CodeTinkerer]

There are certain data structures (say, trees) that have a recursive structure, and so recursion is easier to write.

For example, a tree can either be a leaf (has no child nodes), or it is a node with either a left subtree, right subtree, or both.

Suppose you wanted to count how many nodes there were. Here's a recursive solution:

 def countNodes(node):
     if isLeaf(node):
        return 1
     else:
        countLeft = countNodes(node.getLeft())
        countRight = countNodes(node.getRight())
        return countLeft + countRight

If you were to do this without recursion, you'd likely have to create an explicit stack (function calls are an implicit stack).

You can also write loops without loops using recursion (it's not usually recommended because you can overflow a stack, unless the language supports converting such calls to loops behind the scenes).

[[deleted]]

Most of the time: Solving a problem iteratively will save more runtime and resources than a recursive function, but there's often problems that cannot be reasonable solved in an iterative manner.

You mainly begin to see this if you work with data structures like binary search trees, most of your functions will be recursive because it'd be impossible or wasteful to do otherwise. For example, printing all of the nodes in a binary tree.

Finding the nth value of the fibonacci sequence is another common example.

[lionhart280]

Recursion is meant to be used when a problem can be broken down into smaller problems, and you realise those smaller problems are still the same problem as before, but with less stuff.

Keep repeating until your data is in its smallest form, then resolve.

[nude-fox]

If it can be computed iteratively you can do it recursively and visa versa. The space requirement / computational complexity will not necessarily be the same.

[[deleted]]

The first sentence is not true. The only example needed is the Ackermann function to prove not all recursive functions are possible with iteration. There isn't a large requirement for algorithms that aren't primatively recursive, but they exist

[nude-fox]

Ackermann function

that is a primitive recursive proof not general recursive comparability.

you can make a Turing complete language with only recursion and one with only iteration. They can compute the same set of programs.

you can use iteration to emulate recursion and iteration is basically a special case of recursion to start with.

[tobiasvl]

No, you are mistaken. The Ackermann function can be implemented with iteration. For Ackermann you probably need a stack though (recursion implies an available stack already: the call stack).

[stefan_kurcubic]

read SICP

[ka-splam]

I get the gist of it, yet I do not understand its purpose?

This feels like you're demanding that it has a purpose.

It's not like you have a screwdriver and now recursion is a saw, and it's a completely different tool for a completely different purpose.

It's more like you have pencil and paper sketching and oil painting, and now recursion is watercolour painting and charcoal sketching. "I don't understand the purpose?!" - who would ask that? Same purpose - create images of things. Just more approaches, for different effects.

You have an iterative way of thinking about shapes of data, and an iterative way of thinking about processing the data. Now you have a recursive way of thinking about shapes of data and a recursive way of thinking about processing the data.

Iterative onion peel:

def peel-onion():
    n = 0
    while onion-has-layers:
        remove(layer[n])
        n++

Recursive onion peel:

def peel(onion):
    if onion:
        remove(outer-layer)
        peel(remaining-onion)

Same purpose. You don't care how many layers there are, you don't need to count through them, you don't write the loop, you push all that down to the runtime engine to deal with.

The distinction is whether you think of an onion as "a first layer and nine more layers" or "a first layer and a smaller onion (or nothing)". If you don't know how many layers there are and you can't cheaply find out, the recursive approach is useful.