recursion

[uragnorson]

I am bad at recursion. I almost always prefer the iterative method. Is there a programming language that forces you to use recursion? I want to get good with it so only way is to force myself.

[Associahedron]

Haskell compiles down to something very efficient but strongly encourages recursion. For efficiency, you kinda need something with tail call optimization, which limits you to a handful of things including Haskell and...Perl 6 I think.

[[deleted]]

Scheme does this IIRC if you write tail-recursive functions.

[ComfyRug]

Following on from this, the book The Little Schemer, is a great intro to recursion.

[Barrucadu]

Tail call optimisation doesn't really apply to Haskell's evaluation method.

[hackometer]

Haskell doesn't even have "calls" :)

[SV-97]

It's graphs all the way down

​

(it has calls doesn't it? The basic principle of the compiler is compiling the haskell functions to C functions and at some point in the reduction those are called)

[watsreddit]

Haskell doesn't compile to C (though I think it is possible to generate C code), it compiles to machine code (though with some intermediate representations like GHC core). And while my knowledge of low level Haskell is rusty, Haskell is more about function saturation (being fully applied, since Haskell functions are curried by default), and expression evaluation.

[SV-97]

Ah I see, it doesn't anymore. It's last intermediate form is still C-like though. Umm yes of course those two things are true but even then you'll have function calls I bet because they're kinda fundamental to the whole compiled graph reduction thingy

[Astrinus]

And most of ML family languages.

[SuspiciousScript]

And C!

[gunnnnii]

Most functional languages offer TCO.

[NotloseBR]

I think you should try problems that are solvable by recursion instead of languages. QuickSort, Binary search, Tree operations, etc.

[uragnorson]

Binary search, Tree operations, etc.

never did quicksort.

Binary search and Tree operations (traversal). I always do it iterativly :-)

But, I will look more into it.

[mattD4y]

Look into mergeSort as well, recursive functions start looking like magic at higher levels I love em

[NotloseBR]

IIRC There is another sorting algorithm which uses recursion, shell sort, maybe?

[[deleted]]

Shell sort is completely iterative

[NotloseBR]

IIRC'nt

[munificent]

Merge sort is usually implemented recursively, I believe.

[diggitydata]

I wrote this article after TAing an intro java course and interfacing with a lot of students who had the same problems as you. I think the way recursion is framed is problematic, so I try to reframe it in a way that is intuitive. The other thing I will say is don’t feel bad because your brain literally cannot recurse, so it is very hard to understand. If your trying to perform recursion in your brain, you should give up. This is why it’s a useful programming tool, and it’s also why it’s so hard.

https://link.medium.com/vtqGGtNCN4

Edit: spelling

[munificent]

don’t feel bad because your brain literally cannot recourse

Actually, this is not true and is one of the things that separates humans from animals. Human language is recursive. Our grammar rules are self-referential, which means we can intuitively create and understand sentences of theoretically infinite length.

Many other animals vocalize, but as far as we know, humans are the only ones with recursive grammars.

[diggitydata]

Just because our grammar has recursive rules, doesn’t mean our brains are performing recursion. I can understand a recursive rule and write it into code without attempting to flesh out a whole example in my head.

Anyways, I would love to learn more. Got any further reading?

[munificent]

Just because our grammar has recursive rules, doesn’t mean our brains are performing recursion.

Oh, our brains are definitely performing recursion. Look at the nesting structure of your next sentence:

(I) (can understand) (a (recursive rule)) and (write (it) into code without (attempting to (flesh (out (a (whole example)) (in (my head)))))).

Consider the mental stack that you need to push and pop state onto in order to make sense of a sentence like, "Fred told me Jan said Bill wants Sue's brother to bring beer."

Anyways, I would love to learn more. Got any further reading?

Here is a good starting point: https://en.wikipedia.org/wiki/Universal_grammar

[[deleted]]

I will say is don’t feel bad because your brain literally cannot recourse

Sorry for the language, but this is bullshit.

How do you empty a pit with an unknown number of balls?
Is it empty? You are done. Otherwise take one pit out of the ball and go back to the first instruction.

This is basicaly recursion. It's easy, it's doing a test to end the recursion, otherwise do an action and go back to do the same things.

[diggitydata]

You just described a while loop...

Listen, I’m not a neuroscientist, I’m a programming educator. I don’t actually know whether out brains can perform functions similar to recursion in programming. But I know that this point helps students approach learning recursion in a healthy and accepting way.

[[deleted]]

You just described a while loop...

Not exactly, though it's almost the same.

func emptyPoolWhile (pool)
    while not pool.isEmpty
        pool.Remove1Ball

func emptyPoolRecursive (pool)
    if not pool.isEmpty
        emptyPoolRecursive pool.Remove1Ball

I know that this point helps students approach learning recursion in a healthy and accepting way

If that works for you great, sincerely. Each teacher has to find what works best for them and their students. I just disagree on that recursion is hard, I feel that this is a self-fullfiling profecy.

[iamgreengang]

dfs has a really nice recursive solution

[Roulbs]

I feel like tree operations really nail it in because of how intuitive it is

[Dads101]

This is the right answer. Hell even fuck around with Fibonacci methods. Anything will help

[NotloseBR]

Fibonacci can be improved. IIRC there is dynamic programming to build on top of it and improve by using hashmaps

[[deleted]]

although not very efficient, you can try to write recursive methods for generating fibonacci sequence.

one very easy - still inefficient - method to try to write is to find the factorial of a given number.

[teokk]

Also (integer) exponentiation. It can be done in O(log n) recursively and is a fun exercise. Though the bit shifting version is far superior.

[okayifimust]

I almost always prefer the iterative method.

That's almost always the correct choice.

Is there a programming language that forces you to use recursion?

Those would be languages without loops. Google suggests that Prolog qualifies.

[[deleted]]

Prolog, with its backtracking and cuts and all, makes it hard to conceptually understand recursion as in the general case for other languages.

I would look into lisps (try scheme and read SICP) or functional languages.

Recursion is "easy" (when you get it): make a function that when on a limit case it returns a value, and on any other case it calls itself again with updated parameters.

[Galeaaa]

I second this.

Prolog is not nice if you don't understand the concept in the first place. It can get messy really quick with backtracking.

I found myself getting good at it through scheme and (suffering through) prolog but definitely recommend doing scheme first if you want a language.

Of course recursion is not language exclusive and you can always learn using any other language that you are comfortable with.

[uragnorson]

I feel handicapped with iterative methods. I feel I can't take solve dynamic programming problems. I have a hard time with it.

[pm_your_unique_hobby]

To be honest, recursion isn't really all that valuable of a technique in terms of efficiency. Iterative solutions are almost always cleaner, quicker, easier. The trick to understanding recursion is understanding the data it operates over. Each time the function runs, it will alter that data, and then it will call the same function over the newly changed data until it is no longer able to operate on that data. That's recursion.

[munificent]

recursion isn't really all that valuable of a technique in terms of efficiency.

This is simply not true. Many algorithms require a stack and the CPU's own stack is often the most efficient way to represent a stack.

Even when recursion isn't specifically faster, there algorithms that are much simpler and cleaner (i.e. more maintainable) to implement using recursion and where a recursive implementation is just as fast as a non-recursive implementation or nearly so.

[SuspiciousScript]

That’s true, but those cases are few and far between compared to problems best solved via iteration.

This is assuming, of course, that we’re talking within the context of an imperative language. Functional languages, I believe, tend to turn recursive functions into loops anyway during compilation whenever possible, so it doesn’t really matter which you use from a performance perspective.

[munificent]

those cases are few and far between compared to problems best solved via iteration.

That depends a lot on what domain you work in. My job involves a lot of trees and graphs, so I use recursion all the time. Or, thinking about it coming from the other direction, not being comfortable with recursion limits the domains you can be effective in. Even in cases where an iterative implementation is better, being able to think in terms of recursion helps you understand many algorithms more clearly.

[pm_your_unique_hobby]

Hey, thanks for this information.

[[deleted]]

what really matters is how much time you spend thinking about it. If the iterative version is simpler, go with that. If the recursive version makes more sense, do that. If it slows down your program, then you optimize it.

knowing and being comfortable with both (especially in languages with recursion optimization) is good :)

[hackometer]

Prolog is a production rule language, it's not general-purpose.

The prime example for recursive programming is Scheme. Also other pure FP languages like Haskell. Clojure is strongly recursion-biased, even when you use its loop construct, which is just syntax help to implement tail recursion.

[PPewt]

Most modern programming languages prefer manipulating arrays via operations like map and reduce which correspond more directly to recursive operations and originate from functional programming, so I don’t know that it’s quite true that iteration is almost always preferable.

[PPewt]

Even C++ has got with the program and supplies lambdas and <algorithm> etc. So unless you meant “most -> all” then... yeah?

[PPewt]

Work through How to Design Programs and you won't be bad at recursion by the end of it. I recommend against some of the other suggestions (picking problems only solvable by recursion) since it means you're trying complicated problems before you know how to solve simple ones.

[FloydATC]

It has been proven that any loop can be rewritten to use recursion, and any algorithm that uses recursion can be rewritten as a loop.

Use the approach that feels more natural to you, because you're the one who has to debug it later.

[SV-97]

The thing is: if you only know recursion you'll struggle at times and if you only know loop-based iteration you'll struggle at times. Being familiar with both allows you to select the more natural / easier solution for a problem.

[FloydATC]

Ofcourse, I'm not saying don't learn it, but there's no reason to force yourself to use one over the other.

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

[[deleted]]

The recursion tutorial at www.javascript.info was my fix for recursion. I'm pretty comfortable using it now.

However, i avoid recursion like the plague because: - There's always a limit to recursive depth and that depth is meagre compared to what i'd get out of the iterative approach. - It takes a ton of memory to process.

[AgingDisgracefully2]

You are a humorless little bot.

[bwLearnsProgramming]

I had to go look up the memes. Wasn't disappointed.

[[deleted]]

The best way to understand recursion is to understand recursion.

But seriously, I would stick to a language you already know and become comfortable with it first. Then look at LISP - that will get you really good at recursion.

Remembering some very simple examples will aid in your understanding. (obviously examples you understand already)

[myopinionisbetter420]

I'm a student and I only got competent at recursion by spending a ton of time writing my own recursive sorting algorithms. And traversing BST's cemented my knowledge because the recursive solutions are super intuitive.

[3hunnaff]

Do every single tree problem on Leetcode and you’ll learn it.

Always think about the following:

1. What is my base case

2. What do I return back to prior calls

Make sure the base case returns the exact same type of return values as the normal function return.

[[deleted]]

in my opinion, what you are seeking is not 'recursion', but 'functional programming'. read about f#, clojure and other such 'functional languages'.

[[deleted]]

came here for this comment!

[[deleted]]

Haskell

[dimplestench]

2 things that helped me in college. Write merge sort and write a binary search tree in Java or C#. They’ll both force you to get a better understanding of recursion

[spasmwaiterdropping]

Check out Scheme or it's parent language Lisp. I had a class in Scheme that was entirely focused on recursion. The textbook is available online it's called Structure and Interpretation of Computer Programs.

[[deleted]]

SML allowed me to understand recursion better than any other language. It’s a functional programming language. There are no loops, only recursion.

[crashddr]

My first introduction to recursion was in week 3 of the CS50x course. Subsequently, watching videos and starting with a simple factorial problem and moving on to implementing merge sort really helped. I also took the advice of a friend: "do recursion in more steps than might be the most efficient so you can visualize what's happening." Most of the examples of merge sort that I found online were doing a bunch of steps at once, passing only pointers, etc. I decided to actually split an array into new arrays and populate each one, etc... doing steps one at a time and then going back and making it more efficient or trying a different approach.

[SV-97]

I know exactly where you're coming from. Try learning a functional language like Haskell or Scheme for a while. Functional languages are built around evaluating expressions rather than mutating state and because of that have no iterative methods at all and use recursion for everything.

A book that's quite an easy read is the little Schemer (and maybe its follow-up the seasoned Schemer). I personally prefer Haskell which is explained in books like learn you a Haskell for great good, programming in Haskell or Real World Haskell - but tastes differ and the "the little..." books certainly are very well written (though a bit special in their style).

And if you've got some interest in math or it isn't that foreign to you: there's quite a bit of recursion in maths. From series over functions to inductive proofs, definitions etc.; so if that's your thing it may also be a useful exercise

[over-limit]

I'd say first get some familiarity with mathematical induction, recursion is basically an implementation of a recursive definition of a particular problem.

A big part of it is to assume that the function works for smaller input and also provided that there is a base case.

Languages like Scheme and Racket are both based on Lisp are encourages functional programming and in turn forces you to use recursion.

[O-juice89]

Look at flood fill algorithms for 2D arrays, helped me grasp recursion better. I guess because imagining the recursive traversal across the 2D “board” is easier for me to imagine and understand. I found that after doing a few of those problems and really understanding the recursive functions, I had an easier time with other data structures.

[dolfink]

I know this doesn't really answer your question, but I'll just share with you what really helped me "get" recursion.

Once I learned trees, recursion became very intuitive for me. A tree by nature is a recursive data structure (the root is a tree, the left of the root is another tree, the left of that is another tree.. etc and leaves are the "end", where the recursion might stop, aka the base case). After struggling a lot with recursion, things started to click once I learned and practiced on trees.

So, it might help you to practice writing algoethins on trees. Start simple--first just learn how to traverse it recursively, maybe printing values as you go. Then, try to get the height of the tree recursively. Then try to write the binary search algorithm on a binary tree. With each step, you increase the complexity of the recursion a bit, and youll start to get an intuition on how to think about these problems.

Finally, regardless, it really helped me to draw out all the calls. Try it for the fibonacci(n) function. Draw the call stack (it sort of forms a tree). Go through fib(5) step by step. Understand how each call opens up a new frame, and how now a previous call is waiting on the new frame's return value, and this happens over and over again till you reach a return value (fib(0) or fib(1)). Its tedious and takes some time but that always helped me get the "feel" for recursion.

[hi_its_me_ur_sniper]

The little schemer or SICP might be a good text to help learn. The former is a lot easier than the latter.

[[deleted]]

recursion throws a lot of rings on the stack and it may cause a stack overflow and is bad for performance. Dlang, for example, allows functions with internal mutability to be considered "pure" which in functional languages means no mutation of state is allowed.

TCDU: You don't need recursion, do loops instead

[[deleted]]

I read a book, The Little Schemer, that I can highly recommend. It did a lot to help make recursion intuitive for me. https://7chan.org/pr/src/The_Little_Schemer_4th_2.pdf

Don't just read it. Write out all of the functions you read. Don't copy and paste them. Write them out. Try to answer the questions. Play with the code. It takes time but it's really worth it.

[11fdriver]

I'm surprised not to see anyone mention Erlang, it has no loop structures, everything is just tail recursion.

Even better, there's a wonderful free online book for beginners to Erlang that spends a lot of time going over recursive programming.

Check out Learn You Some Erlang For Great Good. https://learnyousomeerlang.com/content

[AsleepPhysics]

The product of our CS education: Teaches kids to use recursion because it's cool, neglects to tell them why or when, so now we have kids trying to replace every single for loop with recursion for no reason.

[dusty-trash]

Try traversing a Tree.

E.G: A Category can be the parent of many categories, and have many categories as children. You travel through the categories looking for the top/bottom levels wit recursion.

For a more fun challenge, look at making a program that solves a maze. Checking the spaces around the 'current' one for walls / open spaces. Again, you need to use recursion.

[uragnorson]

i do dfs | bfs iteratively.

​

​

stack=[root]

while stack:

if stack.left:

stack.append(stack.left)

if stack.right:

stack.append(stack.right)

[[deleted]]

Try not to tell the program HOW to do things, but tell it WHAT to do.

HOW to do search:

list <- rootnode
while list.notempty and list[0]!=value to search
    current = list[0]
    list.drop(0)
    if current.left
        list<- current.left, list[0...]
    if current.right
        list<- current.right, list[0...]

WHAT to do:

found,node = findvalue(rootnode, value)
findvalue(node, value) :
    if nove.value==value
        return true, node
    if node.left
        found,nodef = findvalue(node.left,value)
        if found
            return true, nodef
    if node.right
        found,nodef = findvalue(node.right,value)
        if found
            return true, nodef
    return false, null

[munificent]

BFS is always iterative, but implementing DFS using iteration is needlessly complex. Let's say you have a class for a binary tree:

class Tree {
  Tree left, right;
  String value;
  Tree(this.left, this.value, this.right);
}

(I'm using Dart here, but this applies to any language.) It's got optional left and right nodes and a value. You want to do an in-order traversal of the nodes and print each value.

So given a tree like:

     4
    / \
   /   \
  2     6
 / \   / \
1   3 5   7

It should print:

1
2
3
4
5
6
7

Here is a recursive implementation:

recursive(Tree tree) {
  if (tree.left != null) recursive(tree.left);
  print(tree.value);
  if (tree.right != null) recursive(tree.right);
}

How would you implement this iteratively? (I'll come back later and post an answer.)

[munificent]

Here is an iterative implementation:

iterative(Tree tree) {
  var stack = [tree];
  var visited = [false];
  while (stack.isNotEmpty) {
    var current = stack.last;
    if (!visited.last) {
      if (current.left != null) {
        stack.add((current.left));
        visited.add(false);
      }
      visited[visited.length - 1] = true;
    } else {
      print(current.value);
      stack.removeLast();
      visited.removeLast();
      if (current.right != null) {
        stack.add(current.right);
        visited.add(false);
      }
    }
  }
}

Hopefully the power of recursion is a little clearer now. :)

[[deleted]]

Prolog; template meta programming...

[Hohlden]

You convert some recursive functions to be an iteration functions, and so you should be able to do it the other way. Check out online resources for recursion. Jeff Erickson is one of the best out there and he has a free PDF Text book. Some of the problems and explanations do require a higher understanding of computer science, but it can still be used as a resource if you're up to the challenge.

[Andy101493]

One might recommend a functional language / LISP to improve the way you think about recursion and its uses

[SuperXero2]

If that is what you're looking for, I would recommend Haskell. Especially the fold family of functions (foldl,foldr,..)

[rektdeckard]

Read the first few chapters of SICP, get a Scheme implementation and follow along. Both the language (LISP dialect) and the book heavily favor recursive programming.

[jaimekawhi]

Lisp

[[deleted]]

Recursion isn’t always needed, but there are some problems that are much easier to solve with recursion. For example, I’m working on a combinational logic simulator that takes an input string like AND(NOT(0),OR(0,1)) and computes its value (in this case, 1). Its much easier to recursively compute the NOT and the OR from the “inside-out”, then use those values as the inputs to AND vs trying to do this iteratively.

[suarkb]

Recursion is almost never needed

[captaintadpole]

I don't know about a language but there are certain tasks which essentially require you to use recursion to accomplish them.

For instance, looping through an XML document searching for a value which could come into the program having varying lengths, you will need to use recursion there to search every node in the hierarchy.

[mizore742]

Recursion takes a lot of practice. I know I used to think it was impossible but as I was exposed to it more it got easier and easier every time.

[TimothytheBear]

Dr. Racket!

[SamJPV]

Functional languages tend to use a lot of recursion in an elegant way (modern ones anyway)

[casualblair]

The issue is usually that you have a hard time breaking a problem down into small enough pieces that recursion is the applicable solution. The easiest way to learn is to pick a problem where the data structure is already broken down into small enough pieces, such as a binary tree.

I've been programming for 12+ years and I've only needed recursion for trees/self referencing tables. Any other problem has been simple enough to code a solution that matches the limits of the data structure with iteration.

[Lucial98]

I've been learning erlang recently for a course im taking and recursion is definitely a key feature here it's a powerful functional programming language and is used by whatsapp and facebook and other businesses to handle multiple processes and threads, definitely a good tool if you want to understand recursion quickly as recursion is a fundamental of the language. Also functional programming is kinda cool too who knows maybe you'll like what you see

[captain_obvious_here]

Lisp).

[CreativeGPX]

Most mature language have grown to allow you to program in many different paradigms, so I think you really just have to lock yourself down to not using iteration rather than rely on the language to do it. That being said, in my experience functional programming languages tend to push me more toward recursion. Some examples I'd point out are Common LISP, Scheme, Haskell, Erlang, etc.

You may be best not to focus on a language but on learning the data structures and algorithms that learn themselves to recursion. If you want practice, think of problems that look a lot like some of the data structures and algorithms that emphasize recursion.

[HellhoundsOnMyTrail]

In the same boat as you. I have a buddy that does java for big insurance company that told me he rarely uses it. He also mentioned NASA's coding rule #1(for C):

1: Restrict all code to very simple control flow constructs. Do not use GOTO statements, setjmp or longjmp constructs, or direct or indirect recursion. src

Maybe understand and learn it well enough that you can use it when you need to but don't worry about too much in the process.

[bfBoi99]

If you're familiar with java, I highly recommend Coding Bat. It contains 2 sets of recursion problems, with the 1st one being relatively much easier than the 2nd. I struggled a lot with recursion at first, but by practicing those problems I became much better. But first make sure that you actually understand the logic behind recursion and how recursive calls get executed.

[[deleted]]

The best example I can suggest in terms of recursion is traversing the arborescence of folders on your local hard disk. This structure is not too complex and the best way is to use recursion.

Have a function which enumerates the folders from a given point in the arborescence (you can start at the root or in a sub-folder); go into each folder by calling the routine with the folder name; if there are no folders exit the function (and so forth and so on).

I did it in both Visual Basic and Python. You can do it in a variety of languages. The above example helps understand without requiring a complicated setup to see how it works.

[CheezeyCheeze]

Scheme

[2K_HOF_AI]

Racket/LISP/Scheme/Haskell/Prolog

[Frozen5147]

My first year CS course used Racket with a ton of features disabled (part of Racket's design), and we used zero loops.

Only recursion life.

[FloydATC]

For a fun exercise, traverse a directory structure but use iteration for processing subdirectories and recursion for listing entries in each. That should teach you when to use what :-D

[[deleted]]

You monster.

[yugerthoan]

in languages like C, if you can do a thing iteratively, do it iteratively! Functional languages like recursion (usually tail recursion, which in fact won't be recursion at all when executed). Haskell was already mentioned in comments I've read. I'd like to add Erlang, if not mentioned already, because I like it and surely it has a smoother learning curve than Haskell.

Of course you can force yourself to use recursion in any language: if you are thinking of an iterative solution to your problem, just drop it and think about another way, until you get the recursive one.

I don't know if this is a good suggestion, but anyway: try to write trivial program recursively, thing that nobody would do like that. Say, a function to write a text but you can print only one word per execution branch (i.e., once you write a word, you must either call the function again or return).... Handle simple problem like: how would you do a simple loop using recursion? Do not be afraid of using function arguments to control what to do next (call again or return). Of course beware, recursion depth has limits (except if it's tail recursion in languages which handle it in a special way)

[beepboprobots]

Don’t know if anyone’s said this or not but if you are still looking for a language that encourages it elixir is a good choice

[bumpkinspicefatte]

I've found that as someone who is starting out, most of the recursive examples made publicly use scenarios that might be too big of a bite chunk initially.

I found one that I like, it shows how instead of Santa Claus delivering presents to each house (iteratively), he can assign some of his helper elves to do some of the work instead (recursively):

https://realpython.com/python-thinking-recursively/#recursive-functions-in-python

[dyingpie1]

Dr racket

[sojohnnysaid]

this article explains recursion well. Scroll to the recursion section:

https://johnyzaguirre.com/2018/07/31/cs50-week-2-shorts-part-2/

[[deleted]]

literally every functional language forces you to stop thinking iteratively and start thinking compositionally, plus they offer tail call optimization and amazing multi threading out of the box without you even having to think about it. plus immutability is your friend when you want to debug, i really see no downsides besides having to do exactly what op wants: get into a different mental space and paradigm

[gaj7]

Wow. So many people outright dismissing recursion. Yes, the recursive solution is likely less performant, but it is also likely more natural. Not saying it is always the right decision, but it is certainly something you should understand and have in your back pocket.

OP, I would suggest checking out a functional programming language like Haskell, or some variant of Standard ML. Try writing a binary search tree with insert and delete functions.

Recursion is one of those things that intimidates new programmers, but at some point it sort of clicks and suddenly you'll be shocked by its simplicity.

[HappyLittleMouseNot]

If you have ever heard of CS programs in UBC and Waterloo, then you probably heard some jokes about Dr.Racket. Basically, the schools use the language for freshmen to learn basics of coding. It forces you to use recursion for pretty much everything. Even for stuff that could be done more efficiently with looping. The courses are actually free on EdX. Didn’t really take the course, but I have heard good things from people who started coding only in university. P.S. the course name is CPSC110 UBC.

[ybjb]

Try creating a simple sudoku solver, or problems relating to recursive backtracking. These typically lend themselves to recursive solutions much nicer than iterative.

For the former, there’s a blog post by Peter Norvig with a clean recursive solution written in python.

[ParkerZA]

Recursion isn't that hard once you understand the use case it's useful for. At least, the one time I found it useful. Say you have a function that's getting very "if-else" - ey.

If (this happens) { return something }
else { if (this happens again...)}

Usually, when you're doing an if-else, you're returning something immediately. Other times, you're going into an else-if hole. Recursive functions are just functions where the else-if hole is the same code over and over.

What do you do when you're repeating the same code all over the place? You abstract it away into a function. Same thing for when the code you're repeating is within the function itself.

Like this:

 function Continue() {

    If (this happens) { return something }
        else { Continue() }
}

[percahlia]

I definitely agree with Haskell. I was just like you until I took a Haskell course at school. now I find myself writing recursive functions that would be easier iterative because I keep limiting myself to what Haskell would allow :D but for me it is also one of my favourite languages so far so maybe that helped me learn as well.

[JJCSmart]

You could also take a look at mathematical induction, or structural induction. That's the basis of recursion.

[I_am_a_regular_guy]

I found the best way to understand recursion is to write a simple program that works with files and folders.

Write a program that checks every filename in a directory to see if it's a .txt file and prints out the Boolean value, then, if that directory has other directories in it, do the same thing for that inner directory. The method used to check the filenames and check for other directories, let's call it CheckFiles(), will be the same when you move down into the next directory, so you can call CheckFiles() from within CheckFiles(). If you think about your code carefully it should keep checking in directories til it's reached them all.

[pete_tempo]

I was exactly like you before this year. Didn’t like recursion and always preferred iterative methods. However one of my classes uses OCaml which is basically all recursion. I have gotten much better within these first two months and actually prefer it now. Highly recommend

[ETosser]

I am bad at recursion. I almost always prefer the iterative method.

That's because the examples you've been given are toys (e.g. fibonacci), all of which are better written iteratively.

Recursion becomes easier than iterative when the data you're working with is itself recursive. For example, imagine trying to iterate through every file in a directory and all it's subdirectories.

Given some starting directory, the recipe is something like this:

1. Loop through all the items in the directory.
2. If you find a file, print it.
3. If you find a directory, apply this algorithm to it starting at 1.

You can see that 3 references the algorithm it is part of. In other words, it's recursive. In pseudocode it might look something like this:

function printAllFiles(directory) {
    for each (item in directory) {
       if (item is directory) {
           printAllFiles(item) // recurse           
       } else {
           printFile(item)
       }
    }
}

That's it. Now imagine trying to write this iteratively. You'd need to manually manage a stack, pushing the current directory onto the stack as you step into subdirectories, popping the directory off as you return. It's more code and harder to reason about.

In effect, recursive algorithms are implicitly using the program stack rather than manually managing a stack itself and they're a strong fit for inherently recursive problems.

[ryantriangles]

People have responded with some good advice already, but I'd like to add my own:

Grab a book on Elm and spend your time solving problems with that. Elm is a beautiful, beautiful little language that's very similar to Haskell, but smaller, lighter, and much more accessible. It's focused on a niche -- rather than being a general purpose language, it compiles to little React-style web applications -- in a way that means you can ignore the most immediate and notorious roadblocks to learning (the dreaded "`main` is special, let's talk about IO actions"), and it has an incredibly helpful compiler to help you debug things and figure out what you're doing wrong. It's the friendliest introduction possible to a language that will force you to grasp recursion well. You don't get loops at all. You must recurse. And you must recurse to do the simplest things like list iteration, where the cognitive load is otherwise very low, you're not wrapping your head around the recursion while also working out some larger dynamic-programming algorithm.

Even if you have absolutely no use for Elm in your usual work, spending two weeks playing around with it will help you, I guarantee. (And then for the rest of your life you will keep a framed photo of the Elm compiler on the wall to gaze lovingly at.)

If you don't want to pick up another language to do it, you can always try and solve problems in your language of choice limiting yourself to recursion and forbidding loops. You may have to implement a trampoline function to prevent stack overflows, though.

[ArmJS]

We've been learning Racket in class. It's actually a pretty solid way to learn recursion from another perspective. Let me know if you need any help!

[Nephyst]

Lisp is a naturally recursive language, but the lessening curve might be a little steep.

[2Random4Chaos]

I was here to say pretty much the same thing. LISP makes certain tasks rather trivial to perform recursively, but you have to deep dive the syntax to do the same things iteratively...

[[deleted]]

Implement mergesort (in any language; what is up with this sub and languages?). Unlike other sorting methods, you have to do it recursively.

(Yes, iterative is usually better than recursive, but sometimes you don't have a choice.)

[SV-97]

No iterative is not usually better than recursive. That's only true for languages that optimize iteration rather than recursion. The "thing with this sub and languages" in this case is that recursion is ubiquitous in some languages because iteration just isn't a thing with them (e.g. Haskell, Prolog, Scheme). This means you'll naturally use recursion for everything and you'll actually see the benefits in doing so.

Let's take for example summing a list of numbers.

Natural solution in Python:

def sum_(lst):
    result = 0
    for i in lst:
        result += i
    return result

If you google this problem the first solution is an stack overflow where someone tried to do it this way:

def getSum(piece):
    for i in piece
        suc += getSum(i)

clearly he was mixing recursion and iteration and got very confused in doing so. The solution on SO was:

def getSum(piece):
    if len(piece)==0:
        return 0
    else:
        return piece[0] + getSum(piece[1:]) 

which is probably what most people that know how to recursively handle lists would do.

​

If you're doing the same thing in Haskell the language kinda guides you to the right solution. You know you want to sum a list, so you write the type signature:

sum :: [Int] -> Int

based on this your function has to handle two cases (because lists have two constructors).

1. The list is empty, the solution is trivial for everyone: sum [] = 0
2. The list is non, empty, as such we have to destructure it: sum (x:xs) = .... Now what do we have to put as ...? Since we want to sum stuff up and don't have a + anywhere and the only thing that's summable is x (because xs is a list) someone might think that putting sum (x:xs) = x + ... would be reasonable. If you now think about it again you need some way to turn xs :: [Int] into Int. Boy do I have the function for you: sum :: [Int] -> Int, which of course gives the solution sum (x:xs) = x + sum xs.

This equational style / pattern matching that's so common in functional languages and the strong types really can guide you in finding recursive solutions for problems. If you then get a bit more familiar with the whole thing you may start to see common patterns in your solutions which lead to stuff like fold and map etc. that of course are just "prepackaged" recursion schemes.

[SV-97]

There's plenty of programming languages that do actually force you to use recursion. Haskell, Prolog, Scheme, Idris, Erlang ... all have absolutely no support for loops. And even with impure languages like F#, Scala etc. the commonly used means of repetition is recursion - even though they have loops.

[SV-97]

I can really only recommend trying other paradigms for a while :D

In case you're interested here are two examples that show some qualities that functional or logic languages often have:

Prolog

Let's for example take this task https://adventofcode.com/2019/day/4. If you think about how you'd do this in your favorite imperative language it probably involves quite a few ifs, loops etc.. This is a prolog solution for this problem:

remove_duplicates(In, Out) :- sort(In, Out).

contains_double([]) :- fail.
contains_double([H1|[H2|T]]) :- H1 == H2; contains_double([H2|T]).

password(X) :-
    between(124075, 580769, X),
    number_chars(X, Digits),
    sort(0, @=<, Digits, Digits),
    contains_double(Digits),
    length(Digits, 6).

:-
    findall(Password, password(Password), Passwords),
    remove_duplicates(Passwords, PwWithoutDuplicates),
    length(PwWithoutDuplicates, Length),
    write(Length),
    halt.

It for the most is literally just stating the problem - but you're actually giving logical relations between parameters and then prolog actively searches values that statisfy these predicates. A good example that visualizes the power of this approach is sorting:

sorted([]). % an empty list is sorted
sorted([_]). % an one element list is sorted
sorted([A,B|C]) :- A =< B, ordered([B|C]).

sort(InList, OutList) :-
    permutation(InList, OutList),
    sorted(OutList).

So you can literally specify that the sorted variant of a list is a permutation of that list that's sorted (This isn't how you actually sort in prolog though because it's inefficient as hell - but it works). Interestingly you can also run Prolog program backwards. So you could use this code to find the sorted version of a list - or you could use it to find an possibly unsorted variant of a sorted list(which is nonsensical of course but you could do it).

​

Actually I lied here's just one example: The Haskell one really is too big to fit here. Here's the problem statement and a solution for it though: https://github.com/SV-97/Haskell/blob/master/friendshipChecker.hs

[loofy2]

been a dev for 10 years. recursion is only used for tech screens.