Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Understanding Recursion as an Absolute Beginner

bigomega.dev

Post reply on HN
Print view View original

31–40 of 55 posts

Re: Understanding Recursion as an Absolute Beginner

#31

Post by SwiftyBug »

pretendscholar wrote: post #10

Is there a good example of a time where recursion would be much more efficient than iteration?

I like to use recursion when I can't predict the number of iterations necessary to do the job. For example, a program that calculates the total size of a folder. With recursion I can easily iterate through all levels of the tree and get their sizes.

I've used the same approach recently when I wrote a GraphQL query generator in Swift. I recursively iterate through an array of dictionaries, each being able to also hold an array of dictionaries of it's own, each being able to also hold an array of dictionaries of it's own, and so on. In the end all I end up with is single a string.

Maybe it's not exactly more efficient, but it was certainly much easier for me.

Re: Understanding Recursion as an Absolute Beginner

#32

Post by cr0sh »

I'm not sure when I learned recursion, so I don't know if I can say whether or not I had any trouble with understanding it.

I do know that once you understand recursion, knowing how to properly change a routine to a stack or other non-recursive routine (generally because you keep blowing the return call stack because the nesting level gets too deep) can be tortuous at times depending on what the routine is doing.

So perhaps that might be an insight to how people facing recursion as a beginner might feel...?

Re: Understanding Recursion as an Absolute Beginner

#33

Post by justinv »

RcouF1uZ4gsC wrote: post #9

>Most of the people find recursion difficult but it's not. Recursion is really hard. According to https://phys.org/news/2019-08-recursive-language-modern-simu... Recursive language is a relatively recent phenomenon and even now is much harder to acquire than language and grammar. Recursion is probably the biggest thing that separates our communication from that of other species and gives such a big advantage. That be…

Thanks for sharing this article!

Re: Understanding Recursion as an Absolute Beginner

#36

Post by alejohausner »

The problem with recursion (and with the counting example in the post) is that a student will ask "why can't I do this with a loop?" It's better to use a problem where recursion MUST be used, such as a binary tree:

The size (# of nodes) of a binary tree is:

- 0, if the tree is empty, or

- size of left subtree + size of right subtree + 1

If you draw a tree, any student will agree that the recursive method makes sense. Indeed, they would be hard-pressed to come up with solution that uses a loop (unless they know about stacks, OK OK).

Re: Understanding Recursion as an Absolute Beginner

#37

Post by physicles »

alejohausner wrote: post #36

The problem with recursion (and with the counting example in the post) is that a student will ask "why can't I do this with a loop?" It's better to use a problem where recursion MUST be used, such as a binary tree: The size (# of nodes) of a binary tree is: - 0, if the tree is empty, or - size of left subtree + size of right subtree + 1 If you draw a tree, any student will agree that the recursive method makes sense.…

True. But then you need to first teach the student about pointers/references, linked lists, and then binary trees. The point of this article was to explain recursion to an absolute beginner.

Re: Understanding Recursion as an Absolute Beginner

#38

Post by dreamcompiler »

pretendscholar wrote: post #10

Is there a good example of a time where recursion would be much more efficient than iteration?

I don't know of,a case where it's more efficient, but tail recursion is exactly as efficient as iteration, because they compile to the same code. No stack is used and there's no function call overhead. But you need a compiler that knows how to compile tail calls.

Re: Understanding Recursion as an Absolute Beginner

#40

Post by wittenator »

alejohausner wrote: post #36

The problem with recursion (and with the counting example in the post) is that a student will ask "why can't I do this with a loop?" It's better to use a problem where recursion MUST be used, such as a binary tree: The size (# of nodes) of a binary tree is: - 0, if the tree is empty, or - size of left subtree + size of right subtree + 1 If you draw a tree, any student will agree that the recursive method makes sense.…

Just a nitpick, loop languages and recursive languages have the same expressive power. Therefore you can write a loop program for any recursive one. So there is no "must".
Post reply on HN