FAQ: Recursion vs. Iteration - Coding Throwdown - Multiplication? Schmultiplication!

This community-built FAQ covers the “Multiplication? Schmultiplication!” exercise from the lesson “Recursion vs. Iteration - Coding Throwdown”.

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

Learn Recursion: Python

FAQs on the exercise Multiplication? Schmultiplication!

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!

def multiplication(num_1, num_2):
result = 0
for count in range(0, num_2):
result += num_1
return result

multiplication(3, 7)

21

multiplication(5, 5)

25

multiplication(0, 4)

0

Is the big O runtime for the above code quadratic because depending on how large your numbers are the for loop will execute more times and then each time the for loop has to execute a linear operation?

Well, as beginners, at least, we generally see computational complexity expressed in terms of a single variable, O(n), O(log(n)), etc.

But your function has two variables! Now, if we hold, for instance, num_1 constant, say 9, and then increase num_2, it would (I think) be linear in num_2, the evaluation of multiplication(9, 1000), taking (more or less) ten times as long as multiplication(9, 100), which in turn takes ten times as long as multiplication(9, 10).

But I don’t think that’s what you are getting at! if you are increasing both num_1 and num_2, I would guess that you would see O(num_1 * num_2), although I don’t know how to derive it.

1 Like

Is it a good way to avoid to do too many recursion, using the minimum value for it?

def multiplication(num_1, num_2):
  if not num_1 or not num_2:
    return 0
  return max(num_1, num_2) + multiplication((min(num_1, num_2) - 1), max(num_1, num_2))

It is cleaner assigning them to variable:

def multiplication(num_1, num_2):
  lowest = min(num_1, num_2) 
  highest = max(num_1, num_2)
  return 0 if not lowest else highest + multiplication(lowest - 1, highest)

Hi all.

I would like to share my thoughts on the runtime with you guys.
There are many ways to do it I guess and I really liked the idea to get the min and max value.

Here is my code for the recursive function without min and max:

print("\nThis is the recursiv Version:")
print("°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°\n\n")

def multiplication_rec(n1,n2,result = 0):
	if n1 == 0 or n2 == 0:
		print("************BASE CASE*******************\n")
		return 0
	if n1 == 1:
		print("************BASE CASE*******************\n")
		return n2 + result
	if n2 == 1:
		print("************BASE CASE*******************\n")
		return n1 + result
	print("++++++++++++++++Recursive Step++++++++++++++++++++")
	print("Adding the secound input number to the result...")
	result += n2
	return multiplication_rec(n1 -1,n2,result)

n1 = 3
n2 = 7
print("\nThe multiplication of the numbers {0} * {1} = {2}.".format(n1,n2,multiplication_rec(n1,n2)))
print("\n\nThe is multiplication rec function has a linear Runtime of O((N)).")
print("N being the first number.")
print("°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°")
print("°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°\n\n")

output:
image

Here is my code with the min and max value:

print("\nThis is the NONE recursiv Version:")
print("°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°\n\n")

def multiplication(n1,n2):
	result = 0
	runtime_count = 0
	if n1 == 0 or n2 == 0:
		print("Runtime count = 1")
		return 0
	if n1 == 1:
		print("Runtime count = 1")
		return n2 
	if n2 == 1:
		print("Runtime count = 1")
		return n1 
	samller_number = min(n1,n2)
	bigger_number = max(n1,n2)
	while samller_number != 0:
		runtime_count += 1
		result += bigger_number 
		samller_number -=1
	print("Runtime count = {0}".format(runtime_count))
	return result


n1 = 7
n2 = 3
print("\nThe multiplication of the numbers {0} * {1} = {2}.".format(n1,n2,multiplication(n1,n2)))
print("\n\nThe is multiplication function has a linear Runtime of O((N = (min(n1,n2)))).")
print("N being the smaller number.")
print("°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°")
print("°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°\n\n")

output:
image

As you can see the Runtime itself is the same, but N is different.
In the recursive function N = the value of the first number (n1)
In min,max function N = the value of the smaller input number

I guess it helps a lot to define N to evaluate the runtime.

Here’s my code. I made it as simple at possible.

def multiplication(n, m):
  if m == 0 or n == 0:
    return 0
  return n + multiplication(n, m - 1)

In this case, I think runtime is O(m) because it only depends on the variable m.

This code doesn’t work. There is a RecursionError:

def multiplication(num_1, num_2):
  if (num_1 or num_2) == 0:
    return 0

  return num_1 + multiplication(num_1, num_2 - 1)

# test cases
print(multiplication(3, 7) == 21)
print(multiplication(5, 5) == 25)
print(multiplication(0, 4) == 0)
# test cases
print(multiplication(3, 7) == 21)
print(multiplication(5, 5) == 25)
print(multiplication(0, 4) == 0)

What is wrong here(some people to reply: someone, @mtf)?
Edit:
The solution works.

What you have there will be evaluated as a relational expression. Only if the yield is False will it equate to zero. In Python 0 and False are equal. What you want would be,

if num_1 == 0 or num_2 == 0:

Can you tell me it so that I understand?

We cannot lump variables together to make a comparison. They have to be one value compared to another value. In a logical expression, each operand is a comparison, hence the corrected example I gave above.

So will this code be evaluated to this if num1 is True or num_2 == 0?

No. It will evaluate to True if both num_1 and num_2 are either falsy or zero.

This is strange; there is an or not a and.

I thought this would evaulate to True if either num_1 or num_2 was equal to zero.

Why do you include falsy, == checks if some data’s value is equal to another’s?
Maybe because the expression before calls bool() on 0.

There are two expressions, not one. The first expression, num_1 or num_2 is the first to be evaluated. If either (or both) of the values is non-zero, the outcome will be True. It will only be False if neither of them is non-zero. The second expression is, if (True === 0) which is False, or if (False === 0) which is True.

Study up on or and and logical operators to get a clearer picture of how they work.

I think it’s the opposite:
If either(or both) of the variables values are 0(

, that says it has to include all falsy values because in boolean terms 0's value is True). There is a bit of opposite stuff between you and me.

Why is there such operator(===)? I only knew = and == not ===. What does it do? Is it the same as ==?

Really? Did you sketch it out on paper, or with logical expressions before you came to that conclusion?

>>> (0 or 0) and True
0
>>> (0 or 1) and True
True
>>> (1 or 0) and True
True
>>> (1 or 1) and True
True
>>> 

My mistake. There is no such operator in Python. Common mistake since I work between languages every day and sometimes forget which language I’m talking about. OG stuff.

In Python, and other languages, 0 equates to False, and 1 equates to True.

>>> 1 == True
True
>>> 0 == False
True
>>> 

Note how in the logic example that AND short-circuits on falsy, and that OR short-circuits on truthy.

I didn’t sketch it out; what is the really the difference between this:

and this:

(you think this is the proper way)
Why are they not the same?

A lot.

A or B

vs.

(A or B) == 0

Given that A and B are expressions with discernable truth value.

Then one suggests you do. Find a few sheets of paper and a sharp pencil and create truth tables for AND, for OR, and for NOT. We can help, but it really will mean more if you do this from your own intuition.

1 Like

Can you make it so that it is more clearer like this:
(a or b) == 0
a == 0 or b == 0
I don’t understand.

A = 0
B = 0
print( (A or B) == 0)
# True