рекурсия

Факториалы

def test(n):
    if n<1: return
    n=n-1
    print("туда")
    test(n)
    print("обратно")
    
test(5);
#простейшая рекурсия




def test(m,n):

    while n>0:
        print("m: ",m);
        print("n: ",n);
        
        m=m*n;
        print("m*n=",m,"\n");
        n=n-1;

test(1,5);
#цикл факториал 5(единицу менять нельзя)
# m - это итоговая переменная



def test(n,result):
    if n<1: return
    result=result*n
    print("счетчик=",n," результат=",result,"\n")
    n=n-1
    test(n,result)
test(5,1);
#рекурсия факториал 5(единицу менять нельзя)
# (n,result): - это итоговая переменная





def test(m,n):
    final=m;
    while n>m:
        print("m: ",m);
        print("счетчик n: ",n);
        print("final: ",final);
        print("final*n=",final,"*",n,"=",final*n);
        final=final*n;
        print("final: ",final,"\n");
        
        n=n-1;

test(3,6);
#цикл факториал нужного диапазона
# final - это итоговая переменная





def test(n):
    if n==1:
        return "stop!"
    print("Начали! n =",n)
    n=n-1
    print("n =",n)
    print("печать ",test(n))
    return n
test(4);
# рекурсия с возвратом значения функции




def test(n):
    if n==2:
        print("стоп! возвращаю 2 \n")
        return 2
    print("Начали! n =",n,", n-1=",n-1,"\n")
    n=n-1
    res_test=test(n)
    fact=res_test*(n+1)
    print("возврат: n =",n,", n+1 =",n+1,", res_test =",res_test)
    print("fact=res_test*(n+1)=",fact,"\n")
    return fact

qq=test(5);
print("финальный результат=",qq)
# неуклюжая рекурсия-факториал с возвратом значения функции



def test(n):
    if n==1:
        print("стоп! возвращаю 1 \n")
        return 1
    print("Начали! n =",n,", n-1=",n-1,"\n")
    
    fact=test(n-1)*n
    print("возврат test(n-1)*n =",fact)
    return fact

qq=test(4);
print("QQ=",qq)
# рекурсия-факториал с возвратом значения функции



def test(n):
    if n==1:
        return 1
    fact=test(n-1)*n
    return test(n-1)*n

print(test(4))
# изящная рекурсия-факториал с возвратом значения функции
# тут функция возвращается сразу с формулой

---

Фибоначчи

a=0
b=1
result=a+b
print("a =",a,", b =",b,", result =",a+b)
#преобразование фибоначчи



a=0
b=1

result=a+b
a=b
b=result
result=a+b
print("a =",a,", b =",b,", result =",a+b)

result=a+b
a=b
b=result
result=a+b
print("a =",a,", b =",b,", result =",a+b)
#преобразование фибоначчи (можно повторять)



a=0
b=1
for i in range(7):
    result=a+b
    a=b
    b=result
    result=a+b
    print("a =",a,", b =",b,", result =",a+b)
#цикл фибоначчи



def test(n):
    if n==0: return ("Фома","Ерёма")#возврат кортежа
    
    print("вглубь",n)
    a,b=test(n-1) #распаковка кортежа
    print("принт",a,b)
    return (a,b)
    
test(5)
#возврат нескольких значений в виде кортежа





def test(n):
    if n==0: return (0,1)#изначальные значения Фибоначчи
    
    print("вглубь",n)
    a,b=test(n-1) #распаковка кортежа
    print("a:",a,", b:",b)
    result=a+b;
    print("result:",result,"\n")
    return (b,result)#всякое число Фибоначчи - это сумма предыдущего результата и бОльшего из его слагаемых

test(8)
#рекурсия фибоначчи (с кортежем)




def test(n):
    if n<=0: return (0)

    print("вглубь",n)
    test(n-1)
    test(n-2)

    print("обратно",n)
test(4)
#непростая рекурсия с двойным вызовом




def test(n):
    if n==1: return (0)
    if n==2: return (1)
    
    print("вглубь",n)
    
    a=test(n-1)
    b=test(n-2)
    print("a:",a,", b:",b)
    result=a+b;
    print("result =",result)
    return (result)

print("Финал!",test(5))

#рекурсия Фибоначчи  с двойным вызовом
#выводится только одно значение из всего ряда

---

Число в степени

def test(a,n):
    etalon=a
    x=1
    while x<n:
        print("a:",a)
        a=a*etalon
        print("a в степени:",a)
        x=x+1
    return a

print(test(2,6))
# цикл. число в степени



def test(a,n):
    etalon=a
    if n==1:
        return a
    print ("a=",a," ,n=",n)
    a=a*(test(a,n-1))
    print ("сборка a=",a)
    return a

print(test(2,6))
# рекурсия. число в степени (только положительные степени)



def test(a,n):
    etalon=a
    if n==0:
        print ("a=",a," ,n=",n)
        return 1
    if n==1:
        print ("a=",a," ,n=",n)
        return a
    print ("a=",a," ,n=",n)
    a=a*(test(a,n-1))
    print ("сборка a=",a)
    return a

print(test(2,0))
# рекурсия. число в степени (только положительные степени и ноль)



def test(a,n):
    if n==0:
        print ("a=",a," ,n=",n)
        return 1
    else:
        print ("a=",a," ,n=",n)
        return a*(test(a,n-1))
    
    print ("сборка a=",a)

# изящная рекурсия. число в степени (только положительные степени и ноль)

---

Число через пробелы

def test(n):
    if n//10==0:
        print("n=",n, ", n%10=",n%10,", n//10=",n//10," STOP!")
        return n%10
    
    print("n=",n, ", n%10=",n%10,", n//10=",n//10)
    

    res=str(test(n//10))+" "
    print(res)
    return res+str(n%10)

print(test(573))
# неуклюжая рекурсия. запись числа через пробелы

---

Сумма цифр

result=0
n=643
while n>0:
    print("результат =",result," , n =",n," , младший разряд n =",n%10)
    result=result+n%10
    n=n//10
    print("результат =",result," , n =",n,"\n")

#цикл сумма цифр числа



def test(n):
    print("n =",n)

    if n==0:
        print("стоп. Тут нет больше цифр.\n")
        return 0
    print("n>0, OK. нацело =",n//10," , остаток =",n%10,"\n")
    

    res=n%10+test(n//10)
    print("res=",res," \n")
    return res
    
test(375)

#рекурсия сумма цифр числа

---

Двойка в степени

def test(n):
    print("n =",n)

    if n==1:
        print("Это двойка в степени!")
        return
    elif n<1:
        print("неверное число")
        return
    else:
        test(n/2)
    
test(512)

# неуклюжая рекурсия (двойка ли это в n-степени?)



def test(n):
    if n==1:
        print("n=1, n =",n)
        return "Это двойка в степени!"
    if n<1:
        print("n<1, n =",n)
        return "неверное число"

    if n>1:
        print("n>1, n =",n)
        return test(n/2)

print(test(16))

# ещё одна неуклюжая рекурсия (двойка ли это в n-степени?)




def test(n):
    if n<1:
        print("n =",n, " , это не двойка...")
        return 0
    if n==1:
        print("n =",n, " , это 2 в степени!")
        print("\n2 в степени 0")
        return 0
    print("n =",n)
    exponent=1+test(n/2)
    print("степень",exponent)
    return exponent 
    
print(test(9))

# ещё одна неуклюжая рекурсия
#(показывает ещё и степень двойки)

---

Палиндром

n="abcdef"
print("всё слово: ",n)
print("последняя буква: ",n[len(n)-1])
n=n[: - 1]
print("урезанное слово: ",n)

#учимся обращаться с строкой




def test(n):
    if len(n)<1: return
    print("всё слово: ",n)
    print("последняя буква: ",n[len(n)-1],"\n")
    test(n[: - 1])
    print("обратно: ",n)
    
test("abcdef")

#"прогоняем" слово через рекурсию




n="abcdef"
x=1

while x<=len(n):
    print(n[x-1])
    print(n[len(n)-x],"\n")
    x+=1

#цикл: "прогоняем" слово через напрямую и задом наперёд




n="abcdbf"
x=1

while x<=len(n):
    
    front=n[x-1]
    print(front)
    
    back=n[len(n)-x]
    print(back)
    
    if front==back:
        print("равенство!","\n")
    else:
        print("нет равенства...","\n")
        
    x+=1

#цикл: определяем равенство/неравенство




n="abcdcba"
x=1
is_palindrom="это не палиндром... ~_~"
while x<=len(n):
    
    front=n[x-1]
    print(front)
    
    back=n[len(n)-x]
    print(back)
    
    if front==back:
        print("равенство!","\n")
        is_palindrom="палиндром! ^_^"
    else:
        print("нет равенства...","\n")
        is_palindrom="это не палиндром... ~_~"
        break
        
    x+=1

print(is_palindrom)

#цикл: палиндром





def test(n):
    if len(n)<1: return
    
    print("всё слово: ",n)
    print("1-я буква: ",n[0])
    print("последняя буква: ",n[len(n)-1])
    
    if n[0]==n[len(n)-1]:
        print("равно!","\n")
    else:
        print("не равно...","\n")
        return
    
    n=n[1:]
    test(n[: - 1])
    print("ЭТО ПАЛИНДРОМ!!!")
test("qwerttrewq")
# очень неуклюжая рекурсия-палиндром




def test(n):
    if len(n)<1: return True
    
    print("всё слово: ",n)
    print("1-я буква: ",n[0])
    print("последняя буква: ",n[len(n)-1])
    
    if n[0]==n[len(n)-1]:
        print("равно!","\n")
    else:
        print("не равно...","\n")
        return False
    
    n=n[1:]
    return test(n[: - 1])
    
print(test("252"))
# изящная рекурсия-палиндром. Тут всегда по цепочке возвращается TRUE, кроме случаев неравенства.
# Тогда всё прерывается и выводится FALSE

---

ханойские башни

Неуклюжее, но работающее решение.
Тут аж 4 вспомогательные функции! :-(

axes=[[4,3,2,1,0],[],[]]

#нахождение промежуточной оси
def transitive_axis(a,b):
    print(" \n функция \"transitive_axis\", элементы",a,"и",b)
    if a+b==1: return 2
    if a+b==2: return 1
    if a+b==3: return 0




#перемещение элемента с оси на ось
def move(element,start,finish):
    print(" \n функция \"move\", элемент",element,"с",start,"на",finish)
    print("было: ",axes)
    axes[start].remove(element)
    axes[finish].append(element)
    print("стало:",axes,"\n")

#поиск элемента. возвращается номер оси и позиция (списком)
def search_element(element):
    print(" \n функция \"search_element\", элемент",element,":")
    for q in range(3):
        if axes[q].count(element)>0:
            return (q,axes[q].index(element))


#есть ли гнет над элементом? Если есть - возврат элемента гнёта, если нет - возврат False
def pressure(element):
    print(" \n функция \"pressure\", элемент",element,":")
    
    search=search_element(element)
    element_axes=search[0]
    print(" ось элемента",element_axes)
    element_position=search[1]
    print(" позиция элемента",element_position)
    
    last_element_position=len(axes[element_axes])-1
    print(" позиция последнего элемента:",last_element_position)
    
    if last_element_position>element_position:
        print(" гнёт присутствует \n")
        return axes[element_axes][element_position+1]
    else:
        print(" гнёта нету \n")
        return False
    


    
    

# основная функция. элемент, начало и конец перемещения
def hanoi(element,start,finish):
    print("\n Функция \"HANOI\":",element,"с",start,"на",finish)
    
    #вариант 1: отрицательное значение
    if element<0:
        print("element<0 ! возврат! \n")
        return
    
    #вариант 2: 0 (т.е., это вершина пирамиды)
    if element==0:
        print("element=0 !")
        move(element,start,finish)
        return
    
    #вариант 3: >0 (т.е., это любой элемент, кроме вершины)
    press=pressure(element)

    if type(press)==int:
        print("есть гнет. Кто угнетает? ",press)
        print("рекурсия hanoi(press) на transitive_axis")
        hanoi(press,start,transitive_axis(start,finish))

        
    if type(press)==bool:
        print("нету гнета. Это ",press)
        print("ПРОПУСК")
    
    print("ПЕРЕМЕЩЕНИЕ")
    move(element,start,finish)
    
    print("ХАНОЙ (element-1,НЕ_СТАРТ_И_НЕ_ФИНИШ,ФИНИШ)")
    hanoi(element-1,transitive_axis(start,finish),finish)
    
    
    
    

    
    
hanoi(4,0,2)