Using recursion instead of for loops / list comprehension

[Drone4four]

So I’ve been learning about symmetric differences between lists which can be accomplished in a number of different ways using for loops, list comprehension, sets the exclusive or carat. Pretty neat stuff. 

Now I am exploring recursion. Wrapping my head around this programming concept is difficult because it’s like a whole different paradigm. Haskell apparently doesn’t have any loops. If you need to iterate over a list, Haskell programmers call a function from within a function. w3schools address function recursion in Python and so does programiz using factorials as an example but the sample code in both tutorials escape my understanding.

Could someone here re-write the for loops (below) but using recursion?

Say I want to create a list of multiples of 2 up to 16. Here is the desired output: 

[0, 4, 8, 12, 16]

There are many ways of doing this in Python. Here are two:

>>> S = [2*n for n in range(0,9) if ( (n % 2) == 0)]
>>>print(S)

And:

>>> def multiples_of_four(n):
...     newlist = []
...     for n in range(0,n*2):
...         if n % 4 == 0:
...              newlist.append(n)
...     return newlist
...
>>> multiples_of_four(9)

That’s great. But how might experienced Python developers such as all of you achieve the same output but by using recursion?

[ndc85430]

I wouldn't use recursion for this particular problem as a list comprehension is easier to understand. Recursion is a good fit for problems that can be expressed in terms of smaller and smaller versions of the same problem, until you get to one that can be solved directly (the so called base case). That's precisely why computing n! is one example that's typically used.

[ndc85430]

Haskell programmers call a function from within a function.

To be clear, it's not calling a function in general, recursion is about one function calling itself.

[deanhystad]

multiples_of_two = list(range(2, max_value, 2))
or
multiples_of_two = [x for x in range(2, max_value, 2)]

These are not the kind of problems where I would use recursion.

This is a recursive function that solves a Sudoku puzzle.

def solve(puzzle):
    for r in range(9):
        for c in range(9):
            ## If cell is open
            if puzzle[r][c] == 0:
                ## Try available numbers
                choices = puzzle.available(r, c)
                for value in choices:
                    puzzle[r][c] = value
                    if solve(puzzle):
                        ## Puzzle is solved!
                        return True
                ## No solution. Unwind recursion
                puzzle[r][c] = 0
                return False
    return True

It is a very simple approach to solving the puzzle. Find an open cell. Fill the cell with number that does not appear in the same row, column or square (3x3 group of cells). Find the next open cell and repeat until all cells are filled, or you find an open cell with no available numbers. If you find an open cell with no available numbers, clear the cell, go back to the previous cell and try the next available number.

Though simple, this algorithm is difficult to implement without recursion. The main thing the program does is maintain a list of partial solutions. This is easy to do using recursion because the Python saves the information automatically. To "flatten" this algorithm I would have to save the boards and the cell and the numbers I have tried in some sort of data structure, and I would have to write code to add a board to the structure and remove a board and my program is going to be a lot longer than 12 lines.

I avoid using recursion. There is no problem you can solve using recursion that cannot be solved without using recursion, and the non-recursive solutions are generally faster. There are often limits on recursion. My Sudoku solver does not bump into these limits, but anyone using a "multiples_of_two" program that used recursion would crash the program if they wanted a list of even numbers from 2 to 5000.

[ndc85430]

There is another thing to mention. Even though in Haskell, you don't have loops, that doesn't necessarily mean you'd always write something recursively. I'm not a Haskell programmer, but I do work in functional languages and your particular example is really just naturally expressed using map (in fact, your list comprehension is pretty much Python's equivalent of calling map in other languages. Well, it would be if you used the step argument to range instead of filtering in the even values). Whether that is done iteratively or recursively likely isn't your concern. Your example implemented in Clojure for example would look like

 
user=> (range 0 10 2)
(0 2 4 6 8)
user=> (defn double-it [x] (* 2 x))
#'user/double-it
user=> (map double-it (range 0 10 2))
(0 4 8 12 16)