递归问题

递归的分析

实例:

汉罗塔(A,B,C三个点位,要求把A位完全移动到C位,只允许小的在大的上面)
汉罗塔

def move(n, a, b, c):
    if n ==1:
        print a, '-->', c,  a,'_',b,'_',c
        return
    move(n-1, a, c, b)
    print a, '-->', c, a,'_',b,'_',c
    move(n-1, b, a, c)
move(4, 'A', 'B', 'C')

分析:

  递归,算法编程中常见的一种方法,函数调用自身,一种十分优雅的解决问题的方法。主要构成分为基线条件和递归条件两种。
  基线条件(base case):规定函数自何时起不能再调用自身,防止出现死循环。
  递归条件(recursive case):函数调用自身
  在实例函数中,if条件引导的就是基线条件,当n=1时,函数终止调用自身,并跳过下面的步骤,直接返回调用该函数的那一层。
  汉罗塔的递归思想的源头在于,他的拆分逻辑,要想把上面N个从A移到C,要经过三步:
  1、把上面N-1个从A移到B
  2、把第N个从A移到C
  3、把B上的那N-1个从B移到C
  这个例子就完美的使用了这儿方法,函数所有的移动都是以a位移向c位,引用时只需要把移动前的位置值传给a变量,把移动后的位置值传给c变量,就可以做到完美的递归引用。再从其中嵌入基线条件,确定当只存在一个需要移位时,直接移动,并且,直接跳过下面的步骤返回调用函数的那一层。
(PS:其实写这个东西就是为了从例子开始,做反推联系,读懂代码并不意味着能够构造出相同思路的代码)


附录:

例子的整个流程
从上到下分别为1,2,3,4

4ABC{               //主要目的,把1234从A移到C
    3ACB{               //主要目的,把123从A移到B
        2ABC{               //主要目的,把12从A移到C
            1ACB{               //主要目的,把1从A移到B
                P-AB                    //把1,从A移到B
            }
                P-AC                //把2,从A移到C
            1BAC{               //主要目的,把1从B移到C
                P-BC                    //把1,从B移到C
            }
        }
                P-AB            //把3,从A移到B
        2CAB{               //主要目的,把12从C移到B
            1CBA{               //主要目的,把1从C移到A
                P-CA                    //把1,从C移到A
            }
                P-CB                //把2,从C移到B
            1ACB{               //主要目的,把1从A移到B
                P-AB                    //把1,从A移到B
            }
        }
    }
P-AC        //把4,从A移到C
    3BAC{               //主要目的,把123从B移到C
        2BCA{               //主要目的,把12从B移到A
            1BAC{               //主要目的,把1从B移到Chttps://youthliuxi.cn/wp-admin/media-upload.php?post_id=557&type=image&TB_iframe=1
                P-BC
            }
                P-BA                //把2,从B移到A
            1CBA{               //主要目的,把1从C移到A
                P-CA
            }
        }
                P-BC            //把3从B移到C
        2ABC{               //主要目的,把12从A移到C
            1ACB{               //主要目的,把1从A移到B
                P-AB
            }
                P-AC                //把2,从A移到C
            1BAC{               //主要目的,把1从B移到C
                P-BC
            }
        }
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注