递归
什么是函数递归
函数的递归就是函数的嵌套，之前讲的函数的嵌套是嵌套的别的函数，而递归则是嵌套函数本身
def f1():
print('from f1')
f1()
f1() # 会进入死循环
以上的函数是一个递归函数，但是这是一个死循环，所以我们需要定一个规则来终止这个函数
def f1(num):
if num < 3:
f1(num+1)
print(num) # 先调用，再进行打印
f1(1)
2
1
def f1(num):
if num < 3:
print(num) # 先打印再进行调用
f1(num+1)
f1(1)
1
2
直接调用
def f1(num):
if num < 3:
print(num) # 先打印再进行调用
f1(num+1)
f1(1)
1
2
以上的函数就是直接调用，函数本身调用本身
间接调用
间接调用指的是不在原来的函数体内调用函数本身，而是通过其他方式进行调用
def bar(num):
if num > 0:
print(num,'from bar')
foo(num)
def foo(num):
print(num,'from foo')
bar(num-1)
bar(5)
print('*'*50)
foo(5)
5 from bar
5 from foo
4 from bar
4 from foo
3 from bar
3 from foo
2 from bar
2 from foo
1 from bar
1 from foo
**************************************************
5 from foo
4 from bar
4 from foo
3 from bar
3 from foo
2 from bar
2 from foo
1 from bar
1 from foo
递归的两个阶段
- 递推：一层一层递归调用下去，进入下一层递归的问题规模将会缩小
- 回溯：递归必须要m有一个明确的结束条件，在满足该条件时，开始一层一层回溯
line = [1,2,3,4,5,6]
def howmanyin(lst):
if lst[1:]:
print(lst)
print('me and the guys behind')
return 1+ howmanyin(lst[1:])
else:
print('just me')
return 1
print(howmanyin(line))
[1, 2, 3, 4, 5, 6]
me and the guys behind
[2, 3, 4, 5, 6]
me and the guys behind
[3, 4, 5, 6]
me and the guys behind
[4, 5, 6]
me and the guys behind
[5, 6]
me and the guys behind
just me
6
二分法
从一个从小到大排列的数组中，我们需要判断某一个数是否在列表里面
nums = [1, 3, 7, 11, 22, 34, 55, 78, 111, 115]
for item in nums:
if item == 10:
print('find it')
break
else:
print('not exists')
not exists
对于上面的代码，我们可以通过foe循环进行实现，但如果我们有一个10000个元素的列表，我们需要找到某一个元素，通过for循环无疑需要很久，这时我们就需要换一个更快的方法了，比如二分法
# 随机生成一个长度为1000的列表
from random import randint
lis = [randint(1,1000) for i in range(1000)]
lis.sort()
print(lis)
[1, 1, 2, 2, 2, 2, 3, 4, 4, 4, 5, 6, 8, 8, 9, 9, 10, 10, 11, 15, 15, 16, 19, 19, 20, 21, 21, 21, 22, 22, 24, 24, 26, 26, 29, 29, 33, 35, 36, 36, 37, 37, 39, 40, 40, 42, 42, 43, 43, 44, 44, 45, 45, 45, 46, 46, 47, 47, 49, 50, 52, 52, 53, 56, 56, 60, 61, 61, 63, 65, 66, 69, 70, 72, 72, 73, 75, 75, 76, 80, 80, 81, 83, 83, 85, 86, 86, 87, 89, 90, 90, 90, 92, 93, 93, 94, 95, 97, 97, 98, 98, 99, 101, 103, 104, 105, 105, 106, 108, 108, 110, 110, 110, 111, 112, 112, 114, 117, 117, 117, 118, 118, 119, 119, 119, 121, 125, 126, 126, 126, 130, 130, 131, 132, 132, 132, 132, 134, 137, 137, 138, 138, 139, 139, 140, 140, 140, 141, 142, 146, 147, 148, 149, 149, 150, 155, 155, 155, 156, 157, 157, 159, 160, 162, 162, 163, 164, 164, 167, 167, 168, 170, 170, 174, 175, 175, 175, 176, 176, 177, 177, 177, 178, 179, 179, 180, 181, 182, 184, 186, 192, 193, 193, 195, 196, 197, 197, 201, 201, 202, 202, 204, 204, 206, 206, 206, 207, 210, 210, 211, 211, 213, 214, 215, 215, 219, 220, 220, 221, 222, 222, 223, 225, 225, 225, 226, 226, 226, 227, 227, 227, 230, 233, 234, 235, 237, 238, 238, 239, 241, 241, 242, 244, 246, 246, 249, 251, 251, 252, 253, 253, 254, 254, 254, 254, 255, 256, 256, 257, 257, 257, 258, 259, 262, 262, 262, 263, 264, 264, 266, 267, 268, 268, 271, 272, 273, 274, 275, 276, 278, 279, 281, 281, 282, 284, 286, 287, 287, 288, 289, 289, 290, 290, 293, 294, 295, 296, 298, 303, 305, 306, 306, 309, 309, 310, 313, 314, 315, 316, 317, 319, 320, 321, 321, 322, 325, 325, 325, 327, 327, 328, 328, 328, 331, 331, 331, 331, 332, 334, 336, 336, 338, 339, 340, 340, 341, 343, 343, 347, 347, 349, 349, 350, 351, 352, 352, 354, 354, 357, 357, 358, 359, 359, 359, 359, 361, 361, 362, 364, 364, 365, 366, 367, 368, 369, 370, 371, 371, 373, 375, 375, 377, 378, 378, 379, 379, 380, 381, 383, 385, 385, 386, 386, 387, 387, 388, 388, 389, 390, 397, 398, 399, 400, 401, 402, 403, 403, 405, 407, 407, 407, 408, 408, 409, 409, 410, 410, 411, 413, 414, 418, 418, 420, 421, 421, 423, 423, 424, 426, 429, 432, 432, 432, 435, 435, 436, 436, 437, 439, 441, 443, 444, 444, 445, 446, 446, 447, 447, 448, 448, 449, 451, 455, 457, 457, 458, 458, 458, 459, 462, 463, 463, 463, 464, 464, 466, 466, 467, 469, 469, 470, 471, 471, 471, 472, 472, 475, 476, 477, 478, 479, 480, 482, 482, 485, 485, 486, 486, 488, 491, 492, 492, 493, 493, 496, 497, 497, 497, 501, 502, 504, 505, 506, 506, 506, 507, 507, 508, 510, 513, 515, 516, 517, 518, 518, 519, 520, 523, 523, 523, 528, 529, 529, 530, 530, 534, 535, 536, 537, 538, 538, 538, 538, 539, 539, 540, 541, 541, 542, 542, 543, 543, 544, 545, 546, 546, 547, 547, 548, 548, 549, 549, 549, 550, 550, 550, 551, 551, 553, 554, 558, 558, 560, 561, 561, 564, 566, 567, 569, 573, 573, 573, 574, 575, 575, 575, 575, 576, 578, 579, 579, 579, 580, 580, 580, 580, 583, 585, 586, 589, 593, 593, 594, 596, 597, 598, 598, 601, 601, 603, 603, 603, 605, 605, 606, 606, 607, 608, 609, 609, 611, 614, 614, 616, 616, 616, 617, 617, 617, 618, 619, 620, 621, 623, 623, 627, 629, 629, 629, 630, 630, 630, 631, 631, 631, 632, 636, 637, 637, 637, 639, 639, 642, 642, 643, 644, 645, 646, 648, 649, 649, 651, 652, 652, 653, 654, 657, 658, 659, 661, 662, 663, 663, 664, 665, 665, 665, 669, 670, 673, 674, 674, 676, 677, 678, 678, 680, 680, 681, 682, 682, 683, 686, 688, 688, 688, 688, 689, 689, 690, 690, 691, 692, 692, 693, 693, 693, 694, 697, 698, 700, 701, 701, 702, 703, 703, 704, 704, 705, 707, 708, 710, 712, 712, 712, 713, 714, 717, 720, 721, 723, 723, 725, 725, 726, 726, 727, 728, 728, 729, 729, 730, 731, 731, 732, 732, 733, 733, 733, 734, 736, 736, 737, 738, 738, 738, 739, 739, 739, 740, 742, 743, 744, 745, 748, 749, 752, 752, 754, 755, 757, 759, 760, 760, 762, 765, 765, 766, 766, 767, 767, 767, 770, 770, 770, 771, 775, 776, 776, 776, 777, 777, 779, 780, 781, 782, 783, 783, 784, 785, 787, 787, 787, 787, 788, 789, 790, 790, 790, 790, 792, 793, 794, 795, 797, 799, 799, 802, 802, 805, 806, 809, 809, 809, 810, 811, 812, 813, 815, 817, 819, 821, 821, 822, 824, 824, 825, 825, 825, 826, 826, 828, 828, 828, 830, 831, 831, 833, 834, 834, 835, 835, 836, 837, 837, 839, 839, 846, 847, 847, 847, 847, 850, 851, 852, 852, 852, 855, 855, 856, 856, 857, 858, 859, 860, 861, 861, 862, 864, 865, 866, 866, 866, 866, 867, 869, 872, 876, 878, 880, 881, 881, 882, 883, 884, 884, 885, 886, 886, 886, 887, 890, 892, 894, 895, 897, 898, 899, 899, 899, 899, 900, 902, 902, 903, 903, 905, 906, 908, 910, 910, 913, 913, 913, 915, 916, 916, 917, 919, 919, 920, 920, 920, 921, 922, 923, 926, 926, 928, 928, 930, 930, 931, 933, 934, 935, 935, 937, 937, 938, 942, 943, 943, 944, 944, 945, 945, 947, 947, 947, 948, 948, 951, 951, 952, 952, 952, 953, 953, 956, 957, 957, 958, 958, 960, 961, 962, 962, 962, 962, 962, 964, 965, 966, 966, 967, 970, 970, 971, 971, 971, 971, 971, 972, 972, 972, 973, 974, 975, 976, 977, 977, 979, 980, 981, 981, 982, 984, 985, 985, 987, 987, 988, 991, 992, 993, 994, 996, 996, 998]
def search(num,lis):
half = len(lis)//2
if not lis:
print('exsits')
return
if num > lis[half]:
lis = lis[half+1:]
search(num,lis)
elif num < lis[half]:
lis = lis[:half]
search(num,lis)
else:
print('find it')
search(695,lis)
exsits