#!/usr/bin/env python
# coding:utf-8

"""
递归
    recurse / recursion
    程序调用自身.

    递归是逆向思维，他假设我们已经得到了部分结果，从尾部追溯到头部，从而让问题简化；
"""


# ================================================================================
"""
递归代码模板
"""


def recursion(level, *params):
    """
    递归代码模板
    """
    # ============================== 递归终止条件
    # recursion terminator
    """
    if level > MAX_LEVEL:
        print_result
        return
    """

    # ============================== 当前层级的处理逻辑
    # process logic in current level
    """
    process_data(level, data, ...)
    """

    # ============================== 递归调用
    # drill down
    """
    recursion(level + 1, p1, ...)
    """

    # ============================== 收尾工作
    # reverse the current level status if needed
    """
    reverse_state(level)
    """

# ================================================================================
"""
斐波那契数列
"""
"""
有的时候，使用递归不一定是效率最佳的。
特别是当问题包含重复的子问题时，例如 fibonacci。
"""


def fibonacci(n):
    # 递归终止条件
    if n == 0 or n == 1:
        return 1
    # 当前层级的处理逻辑
    # 递归调用
    return fibonacci(n-1) + fibonacci(n-2)
# ================================================================================
# ================================================================================
# ================================================================================
# ================================================================================


print fibonacci(10)
# 89
