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

21–30 of 55 posts

Re: Understanding Recursion as an Absolute Beginner

#21

Post by zwkrt »

arc33 wrote: post #16

I think the simplest way to understand recursion is as a for loop where you use the stack as the counter. Recursion is basically implementing the operations of a repetitive loop but the loop controls are not explicit like in a for loop, instead you use the stack as the counter of the loop. Once you think of recursion as just another way to do for loops, it immediately is demystified.

I don't know if I would consider this easy for a beginner, but it does lead to an interesting result in the 'contrapositive' case:

Any recursive solution can be turned into an iterative solution if you store the arguments of the recursive function in a data structure on the heap, and turn the recursive call itself into an access/modification of the data structure. As a specific example, any tail-recursive function can be turned into a for loop that modifies a stack. Recursive functions that are not tail-recursive (such as fibonacci) will require more complex data structures, depending on their internal recursive structure. (fibonacci can use an indexable list, for instance).

This is the heart of memoization and dynamic programming.

Re: Understanding Recursion as an Absolute Beginner

#22

Post by rileytg »

ChristianBundy wrote: post #11
js2 wrote: post #2

countDownFrom(--n) There's no reason to reassign the decremented n within the function. Prefer: countDownFrom(n - 1)

Thank you! This immediately stood out to me as a clever hack that makes it more complicated than it needs to be. I'd have written this function as: function countDownFrom(n) { console.log(n) if (n > 0) { countDownFrom(n - 1) } } This removes both the decrement operator and the return keyword, both of which distract from the concept being taught. This would also make it simple to add a `step` argument, which could be…

the only problem with this approach is it doesn’t clearly teach the concept of a base case and a recursive case

Re: Understanding Recursion as an Absolute Beginner

#23

Post by rileytg »

pretendscholar wrote: post #10

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

not necessarily efficient but here’s my latest use case:

scheduling a health check job recursively. if the health check fails, it schedules itself to run again in X seconds with N-1 runs until giving up and marking the service as down.

iteration here simply wouldn’t work

Re: Understanding Recursion as an Absolute Beginner

#25

Post by [deleted] »

arc33 wrote: post #16

I think the simplest way to understand recursion is as a for loop where you use the stack as the counter. Recursion is basically implementing the operations of a repetitive loop but the loop controls are not explicit like in a for loop, instead you use the stack as the counter of the loop. Once you think of recursion as just another way to do for loops, it immediately is demystified.

[deleted]

Re: Understanding Recursion as an Absolute Beginner

#27

Post by Fishkins »

kazinator wrote: post #14
ChristianBundy wrote: post #11

Earlier quoted context omitted.

Thank you! This immediately stood out to me as a clever hack that makes it more complicated than it needs to be. I'd have written this function as: function countDownFrom(n) { console.log(n) if (n > 0) { countDownFrom(n - 1) } } This removes both the decrement operator and the return keyword, both of which distract from the concept being taught. This would also make it simple to add a `step` argument, which could be…

coutDownfrom(n--) contains a pointless assignment to a variable that has no use in the function after the logging call. It's not what I'd call clever. It spoils the teaching value of the solution, because a beginner might be confused into thinking that the mutation of n is essential, like that there is only a single n and it is being stepped to bring about the countdown. The student needs to understand that the count…

countDownfrom(n--) produces infinite recursion, which is arguably why you could call coutDownfrom(--n) clever (you have to understand the subtleties of those operators). I agree that "pointless" or "stupid" are better descriptors, though :)

Re: Understanding Recursion as an Absolute Beginner

#28

Post by lhnz »

When I was a beginner the two problems I had with recursion were:

1. Not handling the base case and accidentally causing an infinite loop.

2. Never reaching the base case so ending up in an infiniite loop.

3. Creating too much incorrect state, and not having a sane way of debugging or visualising this due to the speed and quantity in which it is created.

Nowadays, I carefully focus on the first two problems, before moving on to working out a way of visualising the next N function calls, etc.

Re: Understanding Recursion as an Absolute Beginner

#29

Post by tempguy9999 »

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…

While recursive human language and recursion in computing terms are related, I really don't see they gain much from each other.

> Recursive language is a relatively recent phenomenon

Is there any evidence it's more recent than non-recursive language acquisition, evolutionarily (rather than developmentally ie child to adult)?

For reference for others in this thread, an example of linguistic recursion is https://en.wikipedia.org /wiki/This_Is_the_House_That_Jack_Built>

    This is the horse and the hound and the horn
    That belonged to the farmer sowing his corn
    That kept the rooster that crowed in the morn
    That woke the judge all shaven and shorn
    That married the man all tattered and torn
    That kissed the maiden all forlorn
    That milked the cow with the crumpled horn
    That tossed the dog that worried the cat
    That killed the rat that ate the malt
    That lay in the house that Jack built.
Post reply on HN