Movatterモバイル変換


[0]ホーム

URL:


Skip to content
DEV Community
Log in Create account

DEV Community

Cover image for Recursion in simple terms
Gonçalo Morais
Gonçalo Morais

Posted on • Originally published atblog.gnclmorais.com on

     

Recursion in simple terms

A few years ago, while pairing with a mentee, I (re)realised how hardrecursion is. It’s not exactly intuitive. After you understand it, it looks simple and quite elegant, but it’s not an easy place to get to when you’re new to programming.

Imagine if you could solve a huge problem doing the same simple step over & over again. Like iteration, but with a twist. Every time you act on the problem, you’re hacking away a small part of it and leaving the rest for the next time you’ll do that simple step.

That’s the power or recursion: you define the solution of a problem as the sum/group of all these repetitive small steps you perform on a tiny subset of the problem. And you do this over & over again until the problem is gone. You solve a bit of the problem now and delay the rest of it for the next iteration, which will occur not on the complete problem that you got on this iteration, but on a smaller set.

Here’s a simple recursive array sum:

functionrecursiveSum(arr){returnarr.length?arr[0]+recursiveSum(arr.slice(1)):0;}
Enter fullscreen modeExit fullscreen mode

The function above returns0 if the array it gets is empty (because the sum of an empty array is zero), but if the array is not empty, it states the total sum of an array as the sum of its head (the first element) with its tail (the rest of the array). If you keep applying that definition on the rest of the array, you end up unfolding the expression.

See howrecursiveSum([1, 2, 3]) unfolds:

recursiveSum([1,2,3])1+recursiveSum([2,3])2+recursiveSum([3])3+recursiveSum([])01+2+3+0=6
Enter fullscreen modeExit fullscreen mode

The way I see it, every time you want to solve a problem recursively, there are three main things that must be present:

  • Base case
  • Solve a bit of the problem
  • Call the solution on a smaller problem

Base case

This is basically yourstop criteria , the condition that will be eventually met in order to stop execution. It usually boils down to returning a trivial value, without recursion involved. For example, in the case offactorial, the base case is0! == 1, so whenn gets down to 0, our function just returns 1. In some cases, more than one base case might be present.

Solve part of the problem

Now that we have our base case(s) defined, we can focus on actually solving the big problem. On the recursive array sum example, we’re taking the array’s head and framing it in a sum with the rest of the array. In the case of aFibonacci sequence, we frame the number we want as the sum of the two previous numbers.

Call the solution on a smaller problem

Finally, when you solved part of the problem, you call the function you are in, but now on a smaller portion of the problem. On a recursive array sum, for example, you would be callingrecursiveSum in a smaller array, typically without its head. In the case of a Fibonacci sequence, we get to the two previous numbers we need by calling the Fibonacci function twice; one call for one index before and another for two indexes before (thus we get the two previous numbers we need). Eventually, by executing the solution on a gradually smaller problem will get it solved.

And that’s basically it. I hope I did a good job in explaining this concept, which sometimes I still struggle with.

Recursion in 'Adventure Time'


Resources

Top comments(0)

Subscribe
pic
Create template

Templates let you quickly answer FAQs or store snippets for re-use.

Dismiss

Are you sure you want to hide this comment? It will become hidden in your post, but will still be visible via the comment'spermalink.

For further actions, you may consider blocking this person and/orreporting abuse

UX Engineer, @recursecenter alumnus, ESTJ. Getting into Ember at the moment, previously Rails and Vue. Runner and climber. I grow a beard most of the time.🤘 light themes 🤘
  • Location
    Nantes, France
  • Work
    Senior Developer
  • Joined

Trending onDEV CommunityHot

DEV Community

We're a place where coders share, stay up-to-date and grow their careers.

Log in Create account

[8]ページ先頭

©2009-2025 Movatter.jp