024 递归:汉诺塔 课后作业问题?

自然水

0. 使用递归编写一个十进制转换为二进制的函数（要求采用“取2取余”的方式，结果与调用bin()一样返回字符串形式）。

答案是：

1. def Dec2Bin(dec):
   
2.       result = ''         
   
3.       if dec:                      #dec地板除结果不为0
   
4.             result = Dec2Bin(dec//2)       #递归关系我倒是理解了，问题在于下一步
   
5.             return result + str(dec%2)          #将所得 余数 添加到字符串内       如果没有上一步 对 result的 “赋值操作”我完全理解这个函数
   
6.       else:
   
7.             return result
   
8.       

复制代码

然后我尝试这样：



以及这样：



以上确实证明了 result 没有被 “赋值”影响，才可以在 空字符串状态拼接 余数进去。

但是，我依然不明白， result = Dec2Bin(dec//2)  这个赋值为什么没影响到 result ?
水平有限，我无法摆脱这个思维：
result = Dec2Bin(dec//2)   执行后， result 分成若干分支 ---即： '22'   '11'    '5'    '2'    '1'   '0'
然后 分别进行 %2 运算，再将余数拼接到 result 的空字符串内。   但是，result 不是被重新赋值过了么！ 并不是空的字符串了啊？  

ButcherRabbit

1. def Dec2Bin(dec):
   
2.       result = ''         
   
3.       if dec:                      #dec地板除结果不为0
   
4.             result = Dec2Bin(dec//2)       #递归关系我倒是理解了，问题在于下一步
   
5.             return result + str(dec%2)          #将所得 余数 添加到字符串内       如果没有上一步 对 result的 “赋值操作”我完全理解这个函数
   
6.       else:
   
7.             return result
   
8.       

复制代码

我们用这个代码分析最简单的吧 Dec2Bin(3),转换为2进制是不是11
dec = 3  result =''  if dec: 条件成立， result=Dec2Bin(1)，然后返回 "Dec2Bin(1)+1"对吧

Dec2Bin(1)等于多少呢：
dec = 1 result =''  if dec: 条件成立， result=Dec2Bin(0)，然后返回 "Dec2Bin(0)+1"对吧

Dec2Bin(0)等于多少呢：
dec = 0  result =''  if dec: 条件不成立， 直接返回 ""对吧

逆推回去，Dec2Bin(3)  返回的是不是"'' + 1 + 1"  就是返回'11'呢

你自己试着逆推一下喽，一直result都是空的

yongxi

楼主请看：
def Dec2Bin(dec):
      result = ''
这里定义了 result 为空字符串。
接下来 。 if dec:  成立的话(地板除不为0)：
result = Dec2Bin(dec//2)      
return result + str(dec%2)
在这里 result 这个变量名字重新被定义成 Dec2Bin(dec//2)
所以return result + str(dec%2) 实际上就是 return Dec2Bin(dec//2) + str(dec%2)
在递归过程中 Dec2Bin(dec//2) 函数每一次被调用
def Dec2Bin(dec):
      result = ''
result 这个变量名都重新定义成空字符串，如果if  dec成立 那么又重新定义成Dec2Bin(dec//2)
知道 if dec 不成立 直接返回result  请注意！ 最后一次递归， result被定义为空字符串后 if dec 不成立
返回的是 空字符串， 空的字符串 加上每一次递归的str(dec%2)
最后就得到了结果 。

这里小甲鱼下了一个套、
不明白的人， 都在追究  result = ''  result = Dec2Bin(dec//2)       return result + str(dec%2)
弄明白实质的东西， 不就是 把result这个变量名多次重复赋值么。 他就是一个变量名字而已

关于递归  一定要学会逆推。 抽象思维不好用文字解释。 就和楼上说的一样，你举一个简单一点的例子，先顺着一步步走完， 然后一点点把返回值结合起来  就懂了

我修改了一下：

1. def Dec2Bin(dec):
   
2.     result = ''   
   
3.     if dec:
   
4.         return Dec2Bin(dec//2) + str(dec%2)
   
5.     else:
   
6.         return result
   
7. 
   
8. print(Dec2Bin(62))
   

复制代码

楼主运行一下 再结合我说的  你就明白了

自然水

yongxi 发表于 2017-5-20 02:18
楼主请看：
def Dec2Bin(dec):
      result = ''

Dec2Bin (45)

Dec2Bin(22) + str(1)
Dec2Bin(11) + str(0)
Dec2Bin(5)   + str(1)
Dec2Bin(2)   + str(0)
Dec2Bin(1)   + str(1)
Dec2Bin(0)   retrun ''

return  '' + 1 +0 +1 +1 +0 +1  (由下至上)

pow (2,3):

2 * pow(x,2)
2 * pow(x,1)
2 * pow(x,0)  == 2 * 1

2 *2*2*pow(x,0)
2*2*2*1
--------------------------------------
大概是明白了，我对比了以前对pow的理解- -

自然水

ButcherRabbit 发表于 2017-5-20 01:22
我们用这个代码分析最简单的吧 Dec2Bin(3),转换为2进制是不是11
dec = 3  result =''  if dec: 条件成 ...

也谢谢你~

HUMMER军

yongxi 发表于 2017-5-20 02:18
楼主请看：
def Dec2Bin(dec):
      result = ''

好像你理解错了。。。

喜欢吃菠菜

1. def dec2bin(dec):
   
2.         if dec==0:   
   
3.                 return '0b'  #dec为0是递归退出条件
   
4.         return dec2bin(dec//2)+str(dec % 2)
   
5. #最后一个return  可以让每次余数（0或则1)往右走一位
   

复制代码

用一个简单的dec走一下就很清楚了：
dec=6
第一步.6>0: dec2bin(3)+'0'
第二步.3>0: dec2bin(1)+'1'+'0'
第三步.1>0:dec2bin(0)+'1'+'1'+'0'
第四步.0==0:'0b'+'1'+'1'+'0' 返回退出
结果：0b110