How to recursively add 1 to number 1000000 times without recursion limit change?

Question

Lets say I have such naive implementation of program which recursively adds ones to a given number.

s=lambda n, i: i>0 and s(n+1, i-1) or n

However it won't add more than recursion limit. Such call with default recursion limit would fail:

s(0, 1000000)

Is there a way, how to solve it with recursion but without limit change?

I thought about the way where I call this function 900 times, if number still greater than 0, I add those 900 to some number, reduce added number by 900 and call this function once more. But can't handle how to write such lambdas.

Even if you set the recursion limit higher you will almost certainly get a segfault, why do you need recursion? — Padraic Cunningham, May 12 '16 at 18:58
@PadraicCunningham Actually among all vowels I can use only "a", so I assume it should be only "lambda" — Viacheslav Kondratiuk, May 12 '16 at 19:05
@viakondratiuk The best way is to use memoisation and _store_ previously computed values somewhere and look them up when needed to reduce recursion overhead. Lambda functions don't have state, though, so it's not something you can implement with a lambda. — Akshat Mahajan, May 12 '16 at 19:05
Ah ok, I have seen something similar before, do you have a link to the challenge description? — Padraic Cunningham, May 12 '16 at 19:07
@PadraicCunningham Don't want to give. To make challenge for others. — Viacheslav Kondratiuk, May 12 '16 at 19:08
@viakondratiuk, sorry for misinterpretation of `s=lambda n, i: i>0 and s(n+1, i-1) or n` — SparkAndShine, May 12 '16 at 19:13
I'm pretty sure the answer here is "no" Every recursive call adds a frame to the stack, and the size of the stack is limited. If you could trick one of the C implemented functions to do this recursively then it might work since that does not contribute to the stack limit but I don't see the point. — Tadhg McDonald-Jensen, May 12 '16 at 19:42
_"of all the vowels I can use only 'a'"_ But you use `i` as a variable and an `o` in the `or`.... — Tadhg McDonald-Jensen, May 12 '16 at 20:01
@TadhgMcDonald-Jensen yes, you are right. it was just naive lambda, don't thought that it would be necessary to expose those details — Viacheslav Kondratiuk, May 12 '16 at 20:04

aghast · Accepted Answer · 2016-05-13T01:50:42.117

3

Try making it logn:

s=lambda n,lim=1000000: 1 if lim==1 else n+s(0,lim//2)+s(0,lim-(lim//2))

print(s(0))

Or, without vowels other than 'a':

t=lambda n,l: 1
v=lambda n,l: n+s(0,l//2)+s(0,l-(l//2))
s=lambda n,l=1000000: (t,v)[l!=1](n,l)

edited May 13 '16 at 01:50

answered May 12 '16 at 19:33

aghast

14,785
3
24
56

1

Note that in the question's comments it was specified that the only permitted vowel is "a," which would rule out `if` and `else` (`lim` could be renamed). I would've suggested `lim==1 or n+s(...`, but `or` isn't allowed either. – TigerhawkT3 May 12 '16 at 20:55

score -1 · Answer 2 · answered May 12 '16 at 19:31

-1

Use divide and conquer:

add = lambda n,l: l > 1 and add(n,l//2) + add(n+l//2, l-l//2) or n

PS: this solution is released under the license, that it is not allowed to use it in any competition or challenge. Any derived work must be released under the same license. For any other usage, its free without the need to mention the author.

answered May 12 '16 at 19:31

Daniel

42,087
4
55
81

when you say "the author" are you referring to yourself? If not then **you** are not referencing the author. – Tadhg McDonald-Jensen May 12 '16 at 20:33
@TadhgMcDonald-Jensen - Is that a problem? "For any other usage, its free without the need to mention the author." Posting on SO isn't participating in a competition or challenge. – TigerhawkT3 May 12 '16 at 20:51
@TigerhawkT3 well no but how is anyone able to reference the author if we have no idea who the author is? – Tadhg McDonald-Jensen May 13 '16 at 02:56
My guess is that it's Daniel. – TigerhawkT3 May 13 '16 at 03:00

How to recursively add 1 to number 1000000 times without recursion limit change?

2 Answers2