我关于递归的一些小思路

18813034116

我觉得递归思路就是逆向思维，即只考虑结果不考虑过程
0. 使用递归编写一个十进制转换为二进制的函数（要求采用“除2取余”的方式，结果与调用bin()一样返回字符串形式）。  
  十进制转二进制，以11转二进制为例：
         11//2=5 ;11%2=1。即11除以2，商为5，余数为1→1
                    ↓
         5//2=2;5%2=1→1
                    ↓
         2//2=1;2%2=0→0
                    ↓
         1//2=0;1%2=1→1
                    ↓
         当商为0的时候就结束了，因为0除以2，商永远为0，余数永远为0。将所得余数拼接起来就是二进制数：1101
                                   1011=1*2^3+0*2^2+1*2^1+1*2^0=8+0+2+1=11
         这里可以看出，编写十进制转二进制的递归函数思路就是：
               1.将十进制数作为参数
               2.下一个参数是上个参数除2的商
               3.所得二进制就是每个参数除2所得余数的拼接，并且要将最后的二进制数作为开头
               4.当参数为0就是函数执行的终点
         除此之外，python的bin函数执行后的二进制数都以'0b'开头，那么我们就当参数为0时，返回的二进制数为'0b'，但是这样并不严谨，因为当一开始参数就为0的时候，即bin(0)得到的是0b0，而这样写得到就是0b。可以通过判断一开始的数是否为0，如果是，返回'0b0'；如果不是，执行递归
         以下是代码：

1. def bin_s(n):
   
2.     def fun(x):#这个函数用于递归计算二进制数   
   
3.         if x==0:
   
4.             return '0b'
   
5.         else:
   
6.             return fun(x//2)+str(x%2)
   
7.     if n==0:#判断初始参数是否为0
   
8.         return '0b0'
   
9.     else:
   
10.         return fun(n)

复制代码

                               
登录/注册后可看大图

1. 写一个函数get_digits(n)，将参数n分解出每个位的数字并按顺序存放到列表中。举例：get_digits(12345) ==> [1, 2, 3, 4, 5]
  我的思路就是依次读取参数中的每个数字，并把它们放入一个数组内，如果你获得的参数是纯数字，是无法利用索引获取其中字符的，可以利用str函数将其转换。
  假设获取的参数为s，第一个数字为str(s)[0],下一个数字就是str(s)[0+1],str(s)[0+1+1]......最后一个数字自然是str(s)[len(s-1)]。
  函数执行结果为数组，所以需要初始化一个数组，可是不能在递归函数初始化数组，这样每次递归，数组都会被重置为空，可以采用上题将递归函数作为内置函数，在外包函数初始化数组，以0为递归函数初始参数，以数字串最后一个数字为终点，得到以下函数：

1. def fun(x):
   
2.     arr=[]
   
3.     def get_digits(n):
   
4.         arr.append(int(str(x)[n]))
   
5.         if n==len(str(x))-1:
   
6.             return arr
   
7.         else:
   
8.             return get_digits(n+1)
   
9.     print get_digits(0)

复制代码

                               
登录/注册后可看大图

2.求回文字符串
  一个回文字符串反转后还是一样的，这意味着，如果有一个字符串s，s[0]==s[-(0+1)],s[1]==s[-(1+1)]...s[n]==s[-(n+1)],那么这个字符串s就是回文字符串，并且无论s的长度是奇数还是偶数，只要判断到(len(s)//2)-1,就可以了，因为无论它是否中间加着一个单独的字符，只要两边字符对应相等就可以了。
  以0为递归函数的起始参数，以(len(s)//2)-1为递归终点，并且设置一个变量，如果所有的都相等就为True，否则为False，同理将这个变量放在外包函数初始化。
  此外如果用的是python2，还需要将获取的字符串解码为Unicode类型的，因为如果你的字符串包含了中文，单个获取字符得到的是乱码
  代码如下：

1. # coding=utf-8
   
2. def check_str():
   
3.     check=False
   
4.     s=raw_input('请输入一个字符串：')
   
5.     try:#两种解码方式二选一
   
6.         s=s.decode('gbk')
   
7.     except:
   
8.         s=s.decode('utf8')
   
9.     def fun(x):
   
10.         if s[x]==s[-(x+1)]:
    
11.             check=True
    
12.         else:
    
13.             check=False
    
14.         if x==(len(s)//2)-1:
    
15.             return check
    
16.         else:
    
17.             return fun(x+1)  
    
18.     if fun(0):#这里输出的中文也要以Unicode形式，具体原因还不清楚
    
19.         print u'这是回文联！'
    
20.     else:
    
21.         print u'这不是回文联！'

复制代码

  

                               
登录/注册后可看大图

3.有5个人坐在一起，问第五个人多少岁？他说比第4个人大2岁。问第4个人岁数，他说比第3个人大2岁。问第三个人，又说比第2人大两岁。问第2个人，说比第一个人大两岁。最后问第一个人，他说是10岁。请问第五个人多大？
可以从中得到两个信息：
  1、第一个人多少岁
  2、后一个人比前一个大2岁
  如果第一个人岁数为n，则下一个人岁数就为n+2，n+2+2.。。。。。编写这个函数需要两个参数，第一个人的岁数，需要知道第几个人的岁数
  代码如下：

1. #coding=utf-8
   
2. def count_age():
   
3.     age=input('请输入第一个人的年龄：')
   
4.     n=input('请输入需要知道第几个人的年龄：')
   
5.     def fun(x):
   
6.         if x==1:
   
7.             return age
   
8.         else:
   
9.             return fun(x-1)+2
   
10.     print '第'+str(n)+'个人的年龄是'+str(fun(n))

复制代码

大部分循环能解决的问题递归能解决，甚至循环难以解决的问题递归也能解决，但递归不是第一选择，比起迭代，递归消耗的内存资源和时间更多，如最后一个问题，如果第一个人年龄是n，那么第m个人年龄就是n+(m-1)*2,直接解决，更便捷