FAQ: Recursion: Python - Recursion and Big O

This community-built FAQ covers the “Recursion and Big O” exercise from the lesson “Recursion: Python”.

Paths and Courses
This exercise can be found in the following Codecademy content:

Learn Recursion: Python

FAQs on the exercise Recursion and Big O

There are currently no frequently asked questions associated with this exercise – that’s where you come in! You can contribute to this section by offering your own questions, answers, or clarifications on this exercise. Ask or answer a question by clicking reply (reply) below.

If you’ve had an “aha” moment about the concepts, formatting, syntax, or anything else with this exercise, consider sharing those insights! Teaching others and answering their questions is one of the best ways to learn and stay sharp.

Join the Discussion. Help a fellow learner on their journey.

Ask or answer a question about this exercise by clicking reply (reply) below!

Agree with a comment or answer? Like (like) to up-vote the contribution!

Need broader help or resources? Head here.

Looking for motivation to keep learning? Join our wider discussions.

Learn more about how to use this guide.

Found a bug? Report it!

Have a question about your account or billing? Reach out to our customer support team!

None of the above? Find out where to ask other questions here!

The highest number that works seems to be 998! On My computer it’s 999…
What? Why?

EDIT
I wrote a iterative factorial function to check if it has the same limitations… and no, it doesn’t! That is feels a little strange :smiley: .

def ifact(n):
 result = 0
 for i in range(n, 0, -1):
  if result == 0:
   result = 1
  result = result*i
 return result

I’ve managed to run this function with really high values as an argument, the only limit seems to be the time it takes for computing.
And this gave me an idea, to use this function as a benchmarking tool!

Check out this code:

from datetime import datetime as dt

def ifact(n):
	if n == 0:
		result = 1
	else:
		result = 1
		for i in range(n, 1, -1):
			result = result * i
	print(result)
	return result

def ibenchmark(n, dbf=False):
	s = dt.now()
	if dbf == False:
		print('calculating iterative factorial of {}'.format(n))
		r = ifact(n)
	if dbf == True:
		print('calculating double iterative factorial of {}'.format(n))
		r = ifact(ifact(n))
	f = dt.now()
	print('result has {} digits.'.format(len(str(r))))
	tt = f - s
	print('took: {}'.format(tt))

ibenchmark(9,True)

I’ve got the output:

result has 1859934 digits.
took: 0:05:05.567477

It took over 5 minutes to compute!!! If you try ibenchmark(8,True) instead - it’s a matter of seconds!

2 Likes

Tired of the dreaded RecursionError? It is possible to increase the system limit on number of recursive calls like so:

import sys
sys.setrecursionlimit(1337)
3 Likes