runtime error - Python, several callings of function containing recursions cause "RuntimeError: maximum recursion depth exceeded" -

runtime error - Python, several callings of function containing recursions cause "RuntimeError: maximum recursion depth exceeded" -

i taking online course of study in coursera "algorithms: design , analysis, part 1", , completed sec homework. during doing it, cannot explain phenomenon caused python runtime error.

i not supposed distribute solution code... write excerpts.

def quick_sort_count (arr, index, median=false): # operations ...... # termination if len(arr)==0 or len(arr)==1: homecoming arr, 0 ........ arr[:i-1], t1 = quick_sort_count(arr[:i-1], index, median) arr[i:], t2 = quick_sort_count(arr[i:], index, median) homecoming arr, len(arr)+t1+t2-1

the programme should analyze info file 10,000 unique number , calculate how many "comparisons" there in quicksort. question contains 3 part: using 1st element pivot of comparison; using lastly one; , using "median" one.

the weird part is, can have right reply via separately running either of question. cannot run 3 of them altogether in function, such as

def main(): # reading file ...... _,result1 = quick_sort_count(arr1, 0) _,result2 = quick_sort_count(arr2, -1) _,result3 = quick_sort_count(arr3, 0, true)

if did, there "runtimeerror: maximum recursion depth exceeded". likes

.... arr[:i-1], t1 = quick_sort_count(arr[:i-1], index, median) file "/users/c/algorithm/quick_sort.py", line 43, in quick_sort_count arr[:i-1], t1 = quick_sort_count(arr[:i-1], index, median) file "/users/c/algorithm/quick_sort.py", line 43, in quick_sort_count arr[:i-1], t1 = quick_sort_count(arr[:i-1], index, median) file "/users/c/algorithm/quick_sort.py", line 43, in quick_sort_count arr[:i-1], t1 = quick_sort_count(arr[:i-1], index, median) file "/users/c/algorithm/quick_sort.py", line 43, in quick_sort_count arr[:i-1], t1 = quick_sort_count(arr[:i-1], index, median) file "/users/c/algorithm/quick_sort.py", line 33, in quick_sort_count arr = swap(arr, index, 0) runtimeerror: maximum recursion depth exceeded

the "swap" simple operation changes locations of arr[index] , arr[0], requirement 2nd question--"use final element pivot element , swap first element before sorting".

and if farther increment recursion limit via

import sys sys.setrecursionlimit(100000)

then 2nd , 3rd question have wrong answers.

can tell me why happen? lot!

as haven't posted finish code, here's bit of general advice on how overcome python's recursion limit.

a generic recursive function has next structure:

def foo: if termination-condition homecoming value else new-value = some-calculations homecoming foo(new-value)

the first step create function tail-recursive, is, eliminate calculations in else branch , bring form

def foo: if termination-condition homecoming value else homecoming foo(some-calculations)

in language supports tail-recursion optimization enough, in python have go 1 step further. instead of making immediate recursive phone call return foo(...), let's homecoming "thunk", description or promise of intend do. in python, thunk can written anonymous lambda function:

def foo: if termination-condition homecoming value else homecoming lambda: foo(some-calculations)

of course, you'll need intermediate function consume values returned foo , if thunk given, carries out until terminal (non-function) value returned:

def foo-interface: # thunk or terminal t = foo() # while it's thunk... while callable(t): t = t() # ...carry out # homecoming terminal homecoming t example

let's have next naive implementation of factorial, fails on big arguments:

def fac(n): homecoming 1 if n < 2 else n * fac(n - 1) > fac(3000) > runtimeerror: maximum recursion depth exceeded

convert tail-recursive...

def f(n, acc=1): homecoming acc if n < 2 else f(n - 1, acc * n)

...apply thunk transformation...

def f(n, acc): homecoming acc if n < 2 else lambda: f(n - 1, acc * n)

...and wrap in interface function (consumer)...

def fac(n): def f(n, acc): homecoming acc if n < 2 else lambda: f(n - 1, acc * n) t = f(n, 1) while callable(t): t = t() homecoming t

it works!

> fac(3000) > 41493596034....

this technique called "trampolining". don't know if helpful in particular case (hence cw), guess know (and impress prof, chance)).

decorator

this kind of tail recursion can written decorator. nice explanation using classes instead of lambda given here.

python runtime-error