Python recursive algorithm doesn't work for large values - C program works -

i wanted write backtracking solution this question, asks find distinct odd numbers sum given n.

i hacked python code:

import sys sys.setrecursionlimit(10000)    stop = false def solve(n, used, current_sum):     global stop     if stop:         return      if current_sum == n:         print(used)         stop = true         return      start = 1 if len(used) == 0 else (used[-1] + 2)     in range(start, n + 1, 2):         if current_sum + <= n , not stop:             used.append(i)             solve(n, used, current_sum + i)             used.pop()         else:             return  solve(100000000, [], 0) 

which, unfortunately, not print me. far can tell, never gets if condition. if print current_sum @ each step, seems stop @ around 16000000 when entire program quits no error.

i tried increasing recursion limit, no luck.

i tested on idle , eclipse, in python 3.4, 64 bit, under windows 8.1. have 16 gb of ram.

if reduce n, solution (remove 0 example).

this did not make sense me, wanted see if maybe have better luck in c. hacked in c:

int sol[100000]; bool done = false; void solve(int n, int k, int sum) {     if (done)         return;      if (sum == n)     {         done = true;         (int = 0; < k; ++i)         {             printf("%d ", sol[i]);         }         printf("\n");         return;     }      int start = 1;     if (k > 0)         start = sol[k - 1] + 2;     (int = start; <= n; += 2)         if (sum + <= n && !done)         {             sol[k] = i;             solve(n, k + 1, sum + i);         }         else             return; }  int main() {     solve(100000000, 0, 0);      return 0; } 

which works great if add zero!

what deal python , how can working large values well?

the execution time lower values comparable c code, quits on me higher values.

what deal python , how can working large values well?

i rewrote code make work. need adapt recursion depth when increase n parameter. used python 2.7.6. idea same way c code wrote, second parameter passed integer , not list.

import sys sys.setrecursionlimit(100000)   sol = [] stop = false  def solve(n, k, current_sum):     global stop      if stop:         return      if current_sum == n:     stop = true     in xrange(0, k, 1):             print(sol[i]),     print         return      start = 1 if len(sol) == 0 else (sol[k-1] + 2)     in xrange(start, n + 1, 2):         if current_sum + <= n , not stop:         sol.append(0)         sol[k] =             solve(n, k + 1, current_sum + i)         else:             return  solve(100000000, 0, 0) 

---

discussion of issue

i tried read memory usage of python code wrote. had set n = 100.000 in order result of 370 mb. adding 0 made operating system kill program. (on mac os x received memory error).

here code used on linux:

import os import sys  sys.setrecursionlimit(100000)   _proc_status = '/proc/%d/status' % os.getpid()  _scale = {'kb': 1024.0, 'mb': 1024.0*1024.0,           'kb': 1024.0, 'mb': 1024.0*1024.0}  def _vmb(vmkey):     '''private.     '''     global _proc_status, _scale      # pseudo file  /proc/<pid>/status     try:         t = open(_proc_status)         v = t.read()         t.close()     except:         return 0.0  # non-linux?      # vmkey line e.g. 'vmrss:  9999  kb\n ...'     = v.index(vmkey)     v = v[i:].split(none, 3)  # whitespace     if len(v) < 3:         return 0.0  # invalid format?      # convert vm value bytes     return float(v[1]) * _scale[v[2]]  def memory(since=0.0):     '''return memory usage in bytes.     '''     return _vmb('vmsize:') - since   stop = false def solve(n, used, current_sum):     global stop      if stop:         return      if current_sum == n:         print(used)         stop = true         return      start = 1 if len(used) == 0 else (used[-1] + 2)     in range(start, n + 1, 2):         if current_sum + <= n , not stop:             used.append(i)             solve(n, used, current_sum + i)             used.pop()         else:             return  m0 = memory() solve(100000, [], 0) m1 = memory(m0) print(m1/(1024*1024)) 

in comparison result improved (corrected) code wrote uses 4 mb parameter n set 100.000.000. that's huge difference indeed.

i not sure why is. in particular have loop contains recursive call (so call recursively several times same branch).

if insist on using recursive calls, maybe you'd want redesign program. recursive calls memorization can faster loops in cases. see this link example.