[Brewer]

I was fooling around with a bit of recursion today, using an example that was posted by (I think) baagavi.

def sumSeries(n):
    if n == 1:
        return 1
    else:
        return n**n + sumSeries(n-1)

print(sumSeries(994))

This piece of code wont go past print(sumSeries(994)), after this it returns an infinite number of errors. However, this is what I get when I return sumSeries(994):

Quote

25247997241201808760750089331498786541744857186534655905410027051131096746253683
086109154633360299793288345985661514601427710775651711046979413301635289812977679955669
385821633216151870372784762521302164768135740826413552631410098052801369188378152948558
053737127391957727607920045612959797511703227309097079564165783013252797968808256301173
347508079061000674155188288434265950997465022110979412113076913184886751297075614167402
792804403083269256796436625746935980381999671923791435609141944215789401126229843946671
010199964966557043379832626173103982583299796603348158856045838381636239064223509100838
902336553369804962128099941300019057908216675351643024877691873117427307947503521843300
451653571723694867199291397841724056491005029503939873477159164565226951393164080730319
336021186758999951621032235408791189779171496178195931709983823868807856261980264227768
607118182174580563830097196979926230441113160308510929196546263792730102512729909052409
565402687773598288327511444714118911106355764472575990557576899626968729474654200535369
629215073285875978811870877994794328155007960751313919108093276021289162499593008355890
950514685440559243734159493303960535037941950574703105043223923883092409478046735386789
897509754806416068131218375889798399489393819385299950404170118330023458401945401952574
572978706942126061863325175806276333598903831507143492404080846415962430623515227880718
590233598260879632547357914126613420444705799491540467388983245557435182516183192856033
265024583783190239668088859347462809073181883531142483132311047376794415192469723924151
096523437737374940020441079006482690903513450844378515785920731714172034240875577695746
951241652504790023835233857265482505726223372845466300313786931312009603345080433867464
847780840829354459503129162994230939793056678650024197540231843781008976757057740291352
600993092119278779380139502716366748480760420026365374364104796128032723794313252444691
124802293547436806973699234277257485627678627937049390661156724719403902936528938097674
038353071371707804129521453393777688847340171187796727856931674850843183397104696667720
397699885869277305074146499961044389380901005352691320141445001384835569298934905785669
684704686809427825258121311021879321757542337508033735890740992061585947501387291341698
611554297922753518208584642285435796959445599635430008040390338130026993302462546732900
895503978496461324691108733588348284238809386348401654992447964764092732435136058547623
501304900515358129791682908456169717267786881954056885663061153499435781029258531580806
341419520372567435193396362780211240097380391218515333550594929154745150795186993267633
103874503955899091807407534544936957522396687464038945459502138104049022371186789010846
411618528055616380221320893320096465608361356652936005427125996356767976415870574247723
933737595100724043810526561018589810597550789766911312923803825395787094222138252402297
655532776885811165486413945130526255857513201346835338630591983723254259742615263364279
85732135729036788632892028549

Is there a reason for this? Is the number simply too large?

This post has been edited by Jambr: 06 October 2010 - 06:57 AM

[Motoma]

Works for me. The errors would be helpful diagnosing your problem. Also, what version of Python are you using?

[Nallo]

Numbers are never too big in Python (unless the are so big that the don't fit into memory anymore)

The problem here is that there is a limit on how deep recursion can go. I am actually surprised that 994 worked I had expected the recursion limit to be reached earlier. Recusion depth limit is one of the reasons to avoid recursion unless it is clearly the natural solution to a problem.

[Brewer]

Then the recursion depth limit is 994 for Python. Don't know if that will be of use to anyone.

I am using 3.1.2, and the errors were all the same, tracing back to this:

return n ** n + sumSeries(n-1)

[Motoma]

Jambr, on 06 October 2010 - 08:07 AM, said:

I am using 3.1.2, and the errors were all the same, tracing back to this:

return n ** n + sumSeries(n-1)

What is the error message?

[baavgai]

Yep, recursion has a depth limit in Python. The reason is that each call has a little over head. You're essentially creating a new variable n with each call of sumSeries, along with some internal stack entries to return.

So, for fun, let's go non recursive...

def sumSeries(n):
	total = 0
	for i in range(1,n+1):
		total += i**i
	return total

Now you're ready for those monster numbers.

Recursion offers an elegant solution to some problems. Traversing heirarchies is a big one; seaching for a file in a directory tree. However, it's not usually the fastest, unless the complexity of maintaining your own stack is out weighted by the simplicity of a function call.

Here's something that's beastly difficult to do without recursion. Find all letter combination of a given sequence.

Recursive solution:

def permute(s, result = ''):
	size = len(s)
	if size==0:
		print(result)
	else:
		for i in range(size):
			# this bit is actuall extra easy in python
			permute(s[:i]+s[i+1:], result + s[i])

permute('abc')

Hmm, non recursive solution... understand that in recursion we use the magic of the stack to do work of us. Python makes dynamic lists very simple. It also makes anonymous sets easy. So, in Python, this mightn't be that hard.

def permute(str):
	q = [(str,'')]
	while len(q[0][0])>0:
		(s, result) = q.pop(0)
		for i in range(len(s)):
			q.append((s[:i]+s[i+1:], result + s[i]))
	
	for (s, result) in q:
		print(result)

permute('abc')

The above isn't so bad because of Python, honestly. Both versions will be pretty fugly is C, but the non recursive much more so.

[Brewer]

There is no message, it just traces back to that and eventually it says the traceback limit has been exceeded. It was trying to recurse too many time.

[Dogstopper]

import sys
sys.setrecursionlimit(20000)

You can always change that number and better to make it as small as possible, but that should change the limit.

[Brewer]

Dogstopper, on 06 October 2010 - 03:06 PM, said:

import sys
sys.setrecursionlimit(20000)

You can always change that number and better to make it as small as possible, but that should change the limit.

Yep! That worked. I raised the number to 2000, and received a number. However, I didn't receive anything when I put in 20,000. I think it was still calculating.

+Rep!

[baavgai]

Jambr, on 06 October 2010 - 09:54 AM, said:

There is no message

Odd, if I simply run sumSeries(1000) I get a screen full of 'File "<stdin>", line 5, in sumSeries' ending with 'RuntimeError: maximum recursion depth exceeded'.

To see it in a program, this should work:

>>> try:
...     print(sumSeries(1000))
... except Exception as ex:
...     print(ex)
... 
maximum recursion depth exceeded

[Brewer]

baavgai, on 07 October 2010 - 11:09 AM, said:

Jambr, on 06 October 2010 - 09:54 AM, said:

There is no message

Odd, if I simply run sumSeries(1000) I get a screen full of 'File "<stdin>", line 5, in sumSeries' ending with 'RuntimeError: maximum recursion depth exceeded'.

To see it in a program, this should work:

>>> try:
...     print(sumSeries(1000))
... except Exception as ex:
...     print(ex)
... 
maximum recursion depth exceeded

Sorry, that is what I should have said. What I meant is that there is no message telling me where the error is. I understand what happened though.