how to count within recursions:
using return recursion() + 1
using global variable and adding up
------------------------------
3. not counting, printing each step within recursion (just to help differentiate)
import sys
sys.setrecursionlimit(1000000000)
c = 0
nn = int(input())
'''
# 1 = rrain
def rrain(nn): # rrain(nn) nn의 우박수 길이
if nn == 1:
return 1
elif nn % 2 == 1:
return rrain(3 * nn + 1) + 1
else:
return rrain(nn//2)+1
print(rrain(nn))
'''
'''
# 2 = rrrain
def rrrain(nn):
global c
if nn == 1:
c += 1
return
elif nn % 2 == 1:
c += 1
rrrain(3 * nn + 1)
else:
c += 1
rrrain(nn//2)
rrrain(nn)
print(c)
'''
'''
- rrain and rrrain (the two code blocks above): both counting how many recursions done
=> rrain (the first code block): the harder one, uses recursion + 1
=> rrrain (the second code block above): the easier one, using global variable
- rrrrain (the code block below): printing each recursion step result
1) for rrain, the "return recursion()+1" counts recursion layers because:
it is equal to ((((recursion()+1)+1)+1)+1)
so it stacks up 1 every time on the later-returned recursion, working as a count
2) for rrrain, the "global c" takes c=0 variable from the start and enters it into the recursion
by doing c += 1 every step/recursion, it counts up.
also, because it doesn't have "return recursion", we ask for the recursion after defining it
and take the c that was counting up during the recursion to print it.
3) for rrrrain, not much is different except it doesn't "return recursion".
instead, it prints nn within the recursion (printing each step outcome)
so print(rrrrain(nn)) lets the print(nn) inside the recursion to go wild
'''
'''
# 3 = rrrrain
def rrrrain(nn):
print(nn)
if nn == 1:
return
elif nn % 2 == 1:
rrrrain(3 * nn + 1)
else:
rrrrain(nn//2)
print(rrrrain(nn))
'''
WRONG answer (my first try)
import sys sys.setrecursionlimit(1000000000) cowrainwater = [0] * 10000000 a, b = map(int, input().split()) c = 0 d = 0 def rain(n): global cowrainwater global c print(c,n) if cowrainwater[n] != 0: c += 1 return cowrainwater[n] elif n == 1: cowrainwater[n] = 1 c += 1 return 1 elif n % 2 == 1: cowrainwater[n] = rain(3*n+1) c += 1 return cowrainwater[n] else: cowrainwater[n] = rain(n//2) c += 1 return cowrainwater[n] for i in range(a, b+1): c = 0 n = i rain(n) if c > d: d = c print(n, d)
referred question:
Q 3733
우박수 길이 (3n+1) (large)