【算法】递归_代码007(未授权)

本文介绍: 在degree有限的情况下，degree=n的三角形，由3个degree=n-1的三角形按品字形拼叠而成，边长均为degree=n的三角形的一半（规模减小）递归是一种解决问题的方法，其精髓在于将问题分解为规模更小的相同问题，持续分解，直到问题规模小到可以用飞常简单直接的方式来解决。分形：一个粗糙或零碎的几何形状，可以分成数个部分，且每一部分都（至少近似地）是整体缩小后的形状，即具有自相似的性质。比10大的整数，拆成一系列比10小的整数，逐个查表，如769，拆成7、6、9。

递归是一种解决问题的方法，其精髓在于将问题分解为规模更小的相同问题，持续分解，直到问题规模小到可以用飞常简单直接的方式来解决。
递归的问题分解方式非常独特，其算法方面的明显特征就是：在算法流程中调用自身。
递归为我们提供了一种对复杂问题的优雅解决方案。

函数自己调用自己，形如：

int f(int x){
	xxxxx
	xxxxx
	xxxxx
	return f(x-1);
}

问题：给定一个列表，返回所有数的和
列表中数的个数不定，需要一个循环和一个累加变量来迭代求和

既不能用for，也不能用while，对不确定长度的列表求和

def listsum(numList):
	theSum=0
	for i in numList:
		theSum=theSum+i
	return theSum

print(listsum([1,3,5,7,9]))

求和实际上由一次次的加法实现，而加法恰有2个操作数

整数转换为任意进制
十进制有10个不同符号：convString=“0123456789”
比10小的整数转换成十进制，直接查表：convString[n]
比10大的整数，拆成一系列比10小的整数，逐个查表，如769，拆成7、6、9
递归三定律里，基本结束条件为：小于10的整数；拆解整数的过程就是向“基本结束条件”演进的过程
用整数除，和求余数两个计算将整数一步步拆开
除以“进制基base”：//base
对“进制基”求余数：%base
问题分解为：余数总小于“进制基base”，是基本结束条件，可直接进行查表转换
整数商成为“更小规模”问题，通过递归调用自身解决

def toStr(n,base):
	convertString="0123456789ABCDEF"
	if n<base:
		return convertString[n]
	else:
	return toStr(n//base,base)+convertString[n%base]

print(toStr(1453,16))

def tell_story():

import turtle
t=turtle.Turtle()
# 作图开始
for i in range(4):
	t

import turtle

t=turtle.Turtle()

def drawSpiral(t,lineLen):
	if lineLen

import turtle
def sierpinski(degree,points):
	colormap=['blue','red','green','white','yellow']

def moveTower(height,fromPole,withPole,toPole):
    if height>=1:
        moveTower(height-1,fromPole,toPole,withPole)
        moveDisk(height,fromPole,toPole)
        moveTower(height-1,withPole,fromPole,toPole)

def moveTower(height,fromPole,withPole,toPole):
    if height>=1:
        moveTower(height-1,fromPole,toPole,withPole)
        moveDisk(height,fromPole,toPole)
        moveTower(height-1,withPole,fromPole,toPole)

def moveDisk(disk,fromPole,toPole):
    print(f"Moving disk[{disk}] from {fromPole} to {toPole}")

moveTower(3,"#1","#2","#3")

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
const int N=20;
int n;
//用一个长度为n的数组记录每个数选择/不选
int state[N];	//0表示尚未考虑，1表示选择，2表示不选

void dfs(int x){	//x表示当前枚举到了哪个整数
	state[x]=1
int main(){
	scanf("%d",&n);
	dfs(1);
	return 0

class Maze:
    def __init__(self,mazeFileName):
        rowsInMaze=0
        columnsInMaze=0
        self.mazelist=[]
        mazeFile=open(mazeFileName,'r')
        rowsInMaze=0
        for line in mazeFile:
            rowList=[]
            col=0
            for ch in line[:-1]:
                rowList append(ch)
                if ch=='S':
                    self.startRow=rowsInMaze
                    self.startCol=col
                col=col+1
            rowsInMaze=rowsInMaze+1
            self.mazelist.append(rowList)
            columnsInMaze=len(rowList)

def carpet(N,C):
    def check(n,x,y):
        if n<=1:
            return True
        n2=n//3
        if n2<=x<n2*2 and n2<=y<n2*2:
            return False
        return check(n2,x%n2,y%n2)

    for y in range(N):
        for x in range(N):
            if check(N,x,y):
                print(C,end='')
            else:
                print(' '*len(C),end='')
            print('')
#test
carpet(27,'[]')