下面这段代码会被认为是尾递归吗?
Will the following piece of code be considered as tail recursion?
下面这个函数是尾递归吗?以及如何写得更高效更清晰。
基于这个问题:
我们构建了一个 table 的 n 行(1 索引)。我们首先在第一行写入 0。现在,在接下来的每一行中,我们查看前一行并将每次出现的 0 替换为 01,将每次出现的 1 替换为 10。
比如n=3,第一行是0,第二行是01,第三行是0110。
给定两个整数 n 和 k,return n 行的 table 的第 n 行中的第 k 个(1 索引)符号。
def kthGrammar(self, n: int, k: int) -> int:
def getKvalue(k, predecessor):
digit_place = k%2
if predecessor == 0:
return 1 if digit_place == 0 else 0
elif predecessor == 1:
return 0 if digit_place == 0 else 1
def helper(n,k):
if n==1:
return 0
prevK = int((k+1)/2)
return getKvalue(k, helper(n-1,prevK))
return helper(n,k)
Is your function currently tail recursive? No. The recursive call is then followed by a call to getValue
.
Your function can be cleaned up dramatically, however. We will begin by replacing 0 and 1 with False and True.
def kthGrammar(n: int, k: int) -> int:
def getKvalue(k : int, predecessor : bool) -> bool:
return (k % 2 == 0) != predecessor
def helper(n : int, k : int) -> bool
if n==1:
return False
prevK = (k+1) // 2
return getKvalue(k, helper(n-1,prevK))
return int(helper(n,k))
Let us further rewrite:
def kthGrammar(n: int, k: int) -> int:
def helper(n : int, k : int) -> bool
if n==1:
return False
prevK = (k+1) // 2
return (k % 2 == 0) != helper(n-1,prevK))
return int(helper(n,k))
Now, we try something rather clever. We define helper2(n : int, k : int, b : bool) = (b != helper(n, k))
. How can we implement helper2
recursively?
Clearly, if n = 1
, then helper2(n, k, b) = (b != False) = b
. Otherwise, we have helper2(n, k, b) = (b != helper(n, k)) = (b != ((k%2 == 0) != helper(n - 1, (k + 1) // 2)) = ((b != (k % 2 == 0)) != helper(n - 1, (k + 1) // 2)) = helper2(n - 1, (k + 1) // 2, b != (k % 2 == 0))
.
Note that I used the fact that for Booleans, a != (b != c)
is identical to (a != b) != c
.
Finally, note that helper(n, k) = (False != helper(n, k) = helper2(n, k, False)
.
So we define
def kthGrammar(n: int, k: int) -> int:
def helper2(n : int, k : int, b : bool) -> bool
if n==1:
return b
prevK = (k+1) // 2
return helper2(n - 1, prevK, b != (k % 2 == 0))
return int(helper2(n, k, False))
Now, we have a tail recursive function. Tail recursion is just another way to express iteration, so we can easily rewrite this to use a while
loop as follows:
def kthGrammar(n : int, k : int) -> int:
b = False
while n != 1:
n, k, b = n - 1, (k + 1) // 2, b != (k % 2 == 0)
return int(b)
Which can again be replaced by
def kthGrammar(n : int, k : int) -> int:
b = False
for _n in range(n, 1, -1):
k, b = (k + 1) // 2, b != (k % 2 == 0)
return int(b)
Of course, there's no reason to start at n
and count down to 1
. So the final form is
def kthGrammar(n : int, k : int) -> int:
b = False
for _n in range(1, n):
k, b = (k + 1) // 2, b != (k % 2 == 0)
return int(b)
Note that we can actually perform one further optimisation. Once it is the case that k = 1
, we see that the line
k, b = (k + 1) // 2, b != (k % 2 == 0)
is a no-op. So the final form is
def kthGrammar(n : int, k : int) -> int:
b = False
for _n in range(1, n):
if k == 1:
break
k, b = (k + 1) // 2, b != (k % 2 == 0)
return int(b)
This will be much more efficient in the case that k <= n
- the runtime is O(min(n, log k))
as opposed to O(n)
.
下面这个函数是尾递归吗?以及如何写得更高效更清晰。
基于这个问题: 我们构建了一个 table 的 n 行(1 索引)。我们首先在第一行写入 0。现在,在接下来的每一行中,我们查看前一行并将每次出现的 0 替换为 01,将每次出现的 1 替换为 10。
比如n=3,第一行是0,第二行是01,第三行是0110。 给定两个整数 n 和 k,return n 行的 table 的第 n 行中的第 k 个(1 索引)符号。
def kthGrammar(self, n: int, k: int) -> int:
def getKvalue(k, predecessor):
digit_place = k%2
if predecessor == 0:
return 1 if digit_place == 0 else 0
elif predecessor == 1:
return 0 if digit_place == 0 else 1
def helper(n,k):
if n==1:
return 0
prevK = int((k+1)/2)
return getKvalue(k, helper(n-1,prevK))
return helper(n,k)
Is your function currently tail recursive? No. The recursive call is then followed by a call to getValue
.
Your function can be cleaned up dramatically, however. We will begin by replacing 0 and 1 with False and True.
def kthGrammar(n: int, k: int) -> int:
def getKvalue(k : int, predecessor : bool) -> bool:
return (k % 2 == 0) != predecessor
def helper(n : int, k : int) -> bool
if n==1:
return False
prevK = (k+1) // 2
return getKvalue(k, helper(n-1,prevK))
return int(helper(n,k))
Let us further rewrite:
def kthGrammar(n: int, k: int) -> int:
def helper(n : int, k : int) -> bool
if n==1:
return False
prevK = (k+1) // 2
return (k % 2 == 0) != helper(n-1,prevK))
return int(helper(n,k))
Now, we try something rather clever. We define helper2(n : int, k : int, b : bool) = (b != helper(n, k))
. How can we implement helper2
recursively?
Clearly, if n = 1
, then helper2(n, k, b) = (b != False) = b
. Otherwise, we have helper2(n, k, b) = (b != helper(n, k)) = (b != ((k%2 == 0) != helper(n - 1, (k + 1) // 2)) = ((b != (k % 2 == 0)) != helper(n - 1, (k + 1) // 2)) = helper2(n - 1, (k + 1) // 2, b != (k % 2 == 0))
.
Note that I used the fact that for Booleans, a != (b != c)
is identical to (a != b) != c
.
Finally, note that helper(n, k) = (False != helper(n, k) = helper2(n, k, False)
.
So we define
def kthGrammar(n: int, k: int) -> int:
def helper2(n : int, k : int, b : bool) -> bool
if n==1:
return b
prevK = (k+1) // 2
return helper2(n - 1, prevK, b != (k % 2 == 0))
return int(helper2(n, k, False))
Now, we have a tail recursive function. Tail recursion is just another way to express iteration, so we can easily rewrite this to use a while
loop as follows:
def kthGrammar(n : int, k : int) -> int:
b = False
while n != 1:
n, k, b = n - 1, (k + 1) // 2, b != (k % 2 == 0)
return int(b)
Which can again be replaced by
def kthGrammar(n : int, k : int) -> int:
b = False
for _n in range(n, 1, -1):
k, b = (k + 1) // 2, b != (k % 2 == 0)
return int(b)
Of course, there's no reason to start at n
and count down to 1
. So the final form is
def kthGrammar(n : int, k : int) -> int:
b = False
for _n in range(1, n):
k, b = (k + 1) // 2, b != (k % 2 == 0)
return int(b)
Note that we can actually perform one further optimisation. Once it is the case that k = 1
, we see that the line
k, b = (k + 1) // 2, b != (k % 2 == 0)
is a no-op. So the final form is
def kthGrammar(n : int, k : int) -> int:
b = False
for _n in range(1, n):
if k == 1:
break
k, b = (k + 1) // 2, b != (k % 2 == 0)
return int(b)
This will be much more efficient in the case that k <= n
- the runtime is O(min(n, log k))
as opposed to O(n)
.