递归编程思想 深度剖析

https://blog.csdn.net/sinat_38052999/article/details/73303111 这个为递归的一篇好文，可与本文结合的看。

递归最主要的有三点：形参、返回值、basecase和更新，递归调用

汉诺塔问题

折纸问题

请把一段纸条竖着放在桌子上， 然后从纸条的下边向上方对折1次， 压出折痕后展开。此时折痕是凹下去的， 即折痕突起的方向指向纸条的背面。如果从纸条的下边向上方连续对折2次， 压出折痕后展开， 此时有三条折痕， 从上到下依次是下折痕、 下折痕和上折痕。给定一个输入参数N， 代表纸条都从下边向上方连续对折N次。请从上到下打印所有折痕的方向。

例如:N=1时， 打印: down N=2时， 打印: down down up

左树头结点都是凹，右树都是凸

【因为自己不知道是左还是右，所以加入了判断，通过down来记录本身是左节点还是右节点，如果down==‘down’打印凹】

开始的时候#第一次带入##因为根部是凹，所以从‘down’开始，这里打印的就是根节点。

def print_all(N):
    print_every(1,N,down='down')#因为根部是凹，所以从‘down’开始，这里打印的就是根节点。
def print_every(i,N,down):
    if i>N:
        return 
    print_every(i+1,N,'down')
    
    if down=='down':
        print "凹"
    if down=='up':
        print "凸"
        
    print_every(i+1,N,'up')

print_all(3)
           

中序遍历，左中右，当前节点函数，先遍历左边，遍历当前，打印，遍历右边。

用了N个空间，遍历了2^n-1的功能