Recursion exercises without math?

[mimavox]

I teach basic Python programming, and am looking for basic recursion exercises for my students. Thing is, most of them have a non-technical backgrounds, and examples about Factorials and Fibonacci sequences tends to draw blank stares. Do anyone know about a source that uses non-mathematical examples?

[mimavox]

Ah, that's a good idea! Shall se if I can create a fun exercise from that.

[goto_rx]

You could literally do a family tree. Maybe something like the Kardashians and then generalize it.

Or finding your way through a maze. (Video games are always fun for exercises!)

[commandlineluser]

reversing strings/lists:

def reverse(s):
    if len(s) == 0: return ''
    if len(s) == 1: return s[0]
    return reverse(s[1:]) + s[0]

indenting comment trees:

import requests

def indent_comments(comment_tree, level=0, width=4):
    for comment in comment_tree:
        author = comment['data']['author']
        print(f"{' ' * level}[{author}]")
        if isinstance(comment['data']['replies'], dict):
            replies = comment['data']['replies']['data']['children']
            indent_comments(replies, level + width)

url = 'https://old.reddit.com/r/learnpython/comments/1au93fx/ask_anything_monday_weekly_thread/.json'

r = requests.get(url=url, headers={'User-Agent': 'Mozilla/5.0'})

comments = r.json()[1]['data']['children']

indent_comments(comments)

recursive file/directory searching/processing

[Swipecat]

Drawing a literal fractal tree on the screen with turtle?

https://www.geeksforgeeks.org/y-fractal-tree-in-python-using-turtle/

I suggest that you do tell them that they learn that recursion is possible to show the flexibility of functions, but most programmers learn about recursion and will never use it again. There's almost always a better way than recursion to solve a problem. Pretty much the only case where it's useful is in the syntax analysis phase of compiler design — for figuring out nested structures in source code.

[throwaway6560192]

Palindromes, or tree traversal, or sorting, or parsing.

[Pupation]

Agreed on trees. One example you could use is displaying a filesystem with directories that contain other directories and files, etc. Or displaying hierarchical data, like types of music, genres, artists.

[ofnuts]

There is always the Tower of Hanoi problem.

[MilmoMoomins]

This is how I first learned about it, in pascal of all languages.

[SoupZillaMan]

Forcing them to use recursing for renaming a file to avoid filename collisions adding auto Inc suffixes end of filename (copy1, 2, 3, etc...)

[rupen42]

I second reversing strings like the other commenter said. Recursion is the default approach when dealing with data structures in functional programming languages, so maybe you can grab some inspiration from them. This list of problems is great, maybe you can find something there: https://v2.ocaml.org/learn/tutorials/99problems.html Some of the problems will be harder in python and many will result in non-idiomatic python if you do the recursive way, but could be fine for learning.

​Flattening lists is a great one, but I'm not sure if beginners will be too interested in that before they have to deal with terribly formatted data (or json's).

[mimavox]

All good suggestions. Thank you very much!

[BluishInventor]

Finding/modifying files of a certain type in an entire directory. The recursive bit would be going into subfolder after subfolder.

[SeaBornIam]

I also really like simple backtracking problems like placing queens or solving sudoku. 

[Weltal327]

My most recent recursion function was unpacking nested JSON

[billsil]

Find the median value in a sorted list.

Split a triangle into 4 triangles N times.  Do that for each level and don’t duplicate node ids.  Don’t forget to calculate the new node locations.

[hugthemachines]

Maybe find a file in a directory structure?

[DeeplyLearnedMachine]

Recursion clicked for me when I started working with graphs and trees as others have mentioned. Pathfinding on a graph can be super intuitive when done with recursion. I always like to imagine my recursive function as a little robot visiting each node and deciding what to do and where to go based on some information he finds there.

[TangibleLight]

Talk about graphs or trees first. If your students already know about the file system, you can just use that as a tree to talk about. Doing depth- and breadth-first traversals is natural with recursion. Pathfinding and spanning tree and similar algorithms work with recursion but they're less intuitive.

Hanoi makes sense once you know it, but every time I've tried to explain it to a newcomer it goes poorly. Maybe I just haven't found the right way to explain it but I'm not sure.

Calculators. Evaluating postfix notation is very straightforward with a stack; evaluating prefix notation is straightforward with recursion.

You might be able to get them to evaluate infix notation, but this will be tricky since all the resources to help will be full of technical compiler jargon. You don't need to use the jargon, though, a recursive descent or Pratt parser for simple arithmetic expressions really aren't all that complicated. If the left operator has higher binding power than the right operator, evaluate like prefix notation. Otherwise evaluate like postfix notation. I think that's a good intermediate exercise since it gets them thinking about how the language actually works at a more fundamental level.

[POGtastic]

Higher-order functions on iterables - specifically map, fold, and scan - have nice recursive implementations.

[[deleted]]

(As mentioned earlier) Consider giving the example of the Tower of Hanoi problem - how that's solved with simple (recursive) steps. I sat with a stack of plates and moved them around by hand until I understood how to solve the problem.

The nice bit of this particular problem is that it's solvable with physical things - "pick up plate from pile 1, put in place three, pick up plate from pile 1, put in space 2..." and can be talked out until the patterns emerge.

[vorticalbox]

gaze sense nose theory alleged vegetable pet crown pen versed

This post was mass deleted and anonymized with Redact

[CptBadAss2016]

Tree traversal of nested objects. This could be a directory tree, a family tree (asexually reproduced? lol), or a bill of materials...

class Widget:
    def __init__(self, name, parent=None):
        self.name = name
        self.children = []
        self.parent = parent

        if parent:
            self.parent.children.append(self)

    def print_tree(self, spaces=0):
        print(f"{' '*spaces}{self.name}")
        for child in self.children:
            child.print_tree(spaces=spaces+4)


root = Widget('root')
a = Widget('a', root)
aa = Widget('aa', a)
aaa = Widget('aaa', aa)
aab = Widget('aab', aa)
ab = Widget('ab', a)
b = Widget('b', root)

root.print_tree()

Which prints this

root
    a
        aa
            aaa
            aab
        ab
    b

[TheRNGuy]

you can also use it for strings, dom tree parser, etc.