A recursive function can replace while and for?

Question

If so, how could I, for example, create a recursive function equivalent to the code below?

lista = list(range(1000))
for i in lista:
       print(i)

Answer 1

First I’ll answer the title ("A recursive function can replace while and for?") in general, we will then talk about the specific code of the question.

---

A recursive function can replace while and for?

By and large, any iterative algorithm can be converted to a recursive and vice versa. But only because can, doesn’t mean that you must do so. Recursion can hide some "traps", and even when it seems a good idea, it may be that the iterative version is better.

A classic example is the calculation of Fibonacci numbers, which should be one of the most commonly used to teach recursion. Its definition is recursive:

fib(1) = fib(2) = 1
fib(n) = fib(n - 1) + fib(n - 2)

So it’s "natural" to implement it like this:

def fib(n):
    if n == 1 or n == 2:
        return 1
    return fib(n - 1) + fib(n - 2)

But there is a "hidden" problem, which is not so obvious at first glance. If we call fib(10), the following recursive calls will occur:

• fib(10) flame fib(9) + fib(8)
  • fib(9) flame fib(8) + fib(7)
    • fib(8) flame fib(7) + fib(6)
      • fib(7) flame fib(6) + fib(5)
      • fib(6) flame fib(5) + fib(4)
      • ...
    • fib(7) flame fib(6) + fib(5)
      • fib(6) flame fib(5) + fib(4)
      • fib(5) flame fib(4) + fib(3)
      • ...
  • fib(8) flame fib(7) + fib(6)
    • fib(7) flame fib(6) + fib(5)
      • fib(6) flame fib(5) + fib(4)
      • fib(5) flame fib(4) + fib(3)
      • ...
    • fib(6) flame fib(5) + fib(4)
      • fib(5) flame fib(4) + fib(3)
      • fib(4) flame fib(3) + fib(2)
      • ...

Note that there are several repeated calls (fib(8) is called twice, fib(7) three times, fib(6) four, etc.), that is, the same value can be calculated several times, unnecessarily. The number of calls grows exponentially and this makes this algorithm very inefficient. Of course you can use techniques of memoization to store already computed results in a cache (yet, there will be a call to check whether or not the result is in the cache), but in fact you are only solving a problem you created yourself by using recursion in a case where it is not the best solution. An iterative algorithm like the one below:

def fib_iterativo(n):
    a, b = 1, 1
    for i in range(1, n):
        a, b = b, a + b
    return a

It’s much more efficient: there are no recursive calls whose amount grows exponentially and so is much faster.

---

Another problem that may occur is the pile burst. Using another example (quoted in the comments), the factorial calculation (another much used to teach recursion):

def fat(n):
    if n <= 1:
        return 1
    return n * fat(n - 1)

If I call fat(5), he’ll call 5 * fat(4). That is, it needs the return of fat(4) to calculate the final result. Only fat(4) will call 4 * fat(3), then she needs to wait fat(3) end (which in turn will call 3 * fat(2) and so on).

There is a limit to all this amount of "hang" calls waiting for the others to finish, and when this is popped, there is a RecursionError (see here an example).

Already using an iterative version does not occur this problem:

def fat(n):
    res = 1
    for i in range(2, n + 1):
        res *= i
    return res

'Cause now it’s just a call with a loop simple. In addition to not blow up the pile, is also faster.

So I repeat: although it is possible to convert any iterative algorithm to recursive and vice versa, it does not mean that you should necessarily do it. There are cases and cases, and to go deeper, I suggest you read here and here (and follow the links you have in the answers too).

---

On the specific code of the question

Your code creates a list containing the numbers from 0 to 999 and prints them out. But what would be the "equivalent" of this code: a function that prints numbers within a certain range, or a function that takes a list and prints out all its values? It may look like the same thing, but it doesn’t. For the first case, the recursive function wouldn’t even need a list:

def imprime_intervalo(inicio, fim):
    if inicio <= fim:
        print(inicio)
        imprime_intervalo(inicio + 1, fim)

import sys
sys.setrecursionlimit(2000)
imprime_intervalo(0, 999)

The detail is that in this case I had to increase the recursion limit using sys.setrecursionlimit, since the limit default was being blown up. This is the problem of the stack overflow (already mentioned above and also in the another answer): there is a much lower limit to the amount of recursive calls. When calling imprime_intervalo(0, 999), the first call needs to wait for all other 999 calls to return, and all of them are "pending" waiting for the last call to end. The number of pending calls is controlled by recursion limit, which can be consulted by sys.getrecursionlimit.

Therefore, the same problem occurs if we have a recursive algorithm to print the values of a list:

def imprime_lista(lista, i=0):
    if i < len(lista):
        print(lista[i])
        imprime_lista(lista, i + 1)

imprime_lista([ 'a', 'b', 'c' ])

import sys
# para uma lista com mais de 1000 elementos, precisa aumentar o limite de recursão
sys.setrecursionlimit(2000)
imprime_lista(list(range(1000)))

There is another alternative, which is to print the first element of the list and call the recursive function by passing the rest of the list (a sub-list containing the second element onwards):

def imprime_lista(lista):
    if lista: # se a lista não é vazia
        print(lista[0])
        imprime_lista(lista[1:])

imprime_lista([ 'a', 'b', 'c' ])

import sys
# para uma lista com mais de 1000 elementos, precisa aumentar o limite de recursão
sys.setrecursionlimit(2000)
imprime_lista(list(range(1000)))

But in addition to having the stack overflow problem, this version is even more inefficient, by having to create multiple sub-lists (a new sub-list at each recursive call).

---

So once again reinforcement: just because it is possible to convert an iterative algorithm to a recursive doesn’t mean you should do it.

Answer 2

If you implement recursiveness for high values, with a thousand for example will return an error:

recursion error Maximum recursion Depth exceeded

It is a protection against stack overflow, yes. Python (or rather, the implementation of Cpython) does not optimize recursion, and unbridled recursion causes this problem. You can check the limit allowed by recursion with sys.getrecursionlimit and change the recursion limit with sys.setrecursionlimit, but doing so is dangerous - the default limit is a bit conservative, but Python stack frames can be quite large. Python is not a functional language and recursion is not a particularly efficient technique. Rewriting the algorithm iteratively is usually a better idea.

However. Here’s an example:

list = [1,2,3,4,5]

def load(i, arr):
  if i < len(arr):
    print(arr[i])
    i += 1
    load(i, arr)

load(0, list)