Convert double for loop into recursion func

Question

I work with two 3D arrays, which the second arr changes according to the first arr.

I try to turn double for loop into a recursive function, but the same error is repeated, RecursionErroe: maximum recursion depth exceeded in comparison.

The for loops i'm trying to convert:

def to_rec(arr):
    new = arr.copy()
    row_max = len(arr) 
    col_max = len(arr[0])

    for  i in range(row_max):
        for j in range(col_max):
            new[i, j, :] = 255- arr[i, j, :]

    return new

RECURSIVE

def rec2(img, row_max, col_max, i, j, new):
if j == col_mac:
    return new
else:
    new[i, j, :] = 255 - img[i, j, :]
    return rec2(img, row_max, col_max, i, j+1, new)

****************************************************
def rec1(img, row_max, col_max, i, j, new):
    if i == row_max:
        return new
    else:
        rec2(img, row_max, col_max, i, j, new)
        return rec1(img, row_max, col_max, i+1, 0, new)

********************************************************
def to_rec(arr):
    ......
     # The same data as in to_rac func with the for loop
    ......
    new = rec1(arr, row_max, col_max, 0, 0, new)
    return new

I can't figure out what is wrong

Possible duplicate of [What is the maximum recursion depth in Python, and how to increase it?](https://stackoverflow.com/questions/3323001/what-is-the-maximum-recursion-depth-in-python-and-how-to-increase-it) — Patrick Artner, Jan 04 '19 at 08:31
Friendly advise: If possible, don't use recursive functions. It might seem fancy when taught in school/college/university, but in real world, the iterative versions are usually faster and less problematic. — kushy, Jan 04 '19 at 08:39

score 1 · Accepted Answer · answered Jan 04 '19 at 08:37

While this doesn't answer your question about recursion depth, I think the solution is quite simple. It seems you want to invert an image (new[i, j, 0] = 255- arr[i, j, 0]) by looping over all pixels in the image, and then manipulating the pixel value. This can be done highly efficiently using NumPy:

import numpy as np
img = load_img_data()  # Replace this by your own data
new_img = 255 - np.array(img)

When your data is stored in a NumPy array, you can trivially perform scalar arithmetics (addition, multiplication, etc.) on matrices. This way you don't have to perform nested loops (or recursive operations).

Patrick Artner · Answer 2 · 2019-01-04T08:48:57.817

The search term RecursionError: maximum recursion depth exceeded has plenty of answers on SO - the reason is simple:

you try to recuse but your function/data does not allow it:
- data too big so that you would need to recurse max_depth+n times to solve it
- your data (or method) will never reach the end-condition of your recursion
- your function has no end condition

Your recursion is flawed and you never reach the end - hence you dive deeper and deeper and put callstack upon callstack until python raises the error to avoid a Stackoverflow from accumulated stack frames due to thousands of function calls.

Ex:

# recurses crashes every time (no end condition)
def no_end_1(k = True):
     no_end_1(not k)

# recursion works if you call it with some data but not with other data
def no_end_2(i):
    if i == 0:
        return "Done"
    no_end_2(i-1)

no_end(25) # works
no_end(-3) # crashes

def flawed_collatz_testmethod(a):
    # collatz conjectur holds for numbers up to 
    #  2.361.183.346.958.000.000.001 (wikipedia), they converge on 1
    if a%2 == 0:
        new_a = a//2
    else:
        new_a = 3*a+1

    if new_a < 1:
        print ("Collatz was wrong")
    else:
        # will eventually end in a loop of 4-2-1-4-2-1-4-2-1-... and crash
        flawed_method(new_a)

In any case .. you need to fix your function. Best way to do it is to take a small datasample, a pen and paper and draw/calculate what the function does to see why it recurses endlessly.

Convert double for loop into recursion func

2 Answers2