I am having a bit of trouble understanding recursion, so any help/understanding would be much appreciated. I am trying to write a code where two non-numbers will multiply. Sounds simple, although there is to be NO ( *, +, or - ) operators used except within two initial functions as seen below. These are used to add 1 too n by n_2 times up until the value of n_2.
Ex: 3 + 4 > 3 + 1 + 1 + 1 + 1 = 7
n = int(input())
n_2 = int(input())
def inc(n):
return n + 1
def dec(n):
return n - 1
There then needs to be an add function that calls back onto the two previous functions, again you cannot use ( *, +, or - ). Then using this add function to "multiply" the numbers in a seperate function by basically adding n by n_2 number of times using the add function.
Thank you!
Update: People are commenting that I am asking this to get homework answers/cheat. I am asking this to understand recursion and to get help on a difficult problem. You do not need answer the problem with the full code, I am just asking for a helping hand to guide me on understanding the topic. Specifically how recursion works in general, with a little bit of guidance on the problem. The problem is and example of what I am looking to solve using recursion.
If you're not used to recursion as a concept, it might help to start with an iterative solution using the tools you have. You've already realised that you can express 3+4 as 3+1+1+1+1, and one way to write that in Python is to use a loop:
def iterative_add(n, n_2):
for _ in range(n_2):
n = inc(n)
return n
Now, we need to turn this into a recursive solution. The defining characteristic of a recursive solution is that instead of figuring out how many times to repeat something, you do a little bit of the problem and call yourself again to do the rest of it. Here, the obvious little bit we can do is to call inc once, and then we call the same function again to do the next inc - so we start with something like this:
def recursive_add(n, n_2):
return recursive_add(inc(n), n_2)
This will obviously keep going forever, and so we need to think about how we tell it to stop. In the iterative version, we stop when we've called inc exactly n_2 times, but here we don't have any obvious way to keep track of how many times we've called it. One nice way is to think about the breakdown 3+4 = 3+1+1+1+1 and realise that once we've added the first 1, the remaining problem is (3+1)+(1+1+1) = 4+3. So we decrement n_2 each time, effectively moving a '1' from the right-hand brackets over to the left at each step, so that next one will be ((3+1)+1) + (1+1). We can stop when the right hand brackets are empty.
In Python, we can write this as:
def recursive_add(n, n_2):
if n_2 == 0:
return n
return recursive_add(inc(n), dec(n_2))
It is worth noting that the way recursion works is to "build up" the expression ((((3+1)+1)+1)+1) in this step-by-step way, and then starts evaluating it from the innermost brackets out. If you can wrap your head around that concept, you should be able to easily write a recursive multiplication solution the same way.