Python Recursion

Here are some questions that a newbie Python user has organized. Most of the topics are examples and exercises from the usual classes and are organized here for review purposes.

Related course: Complete Python Programming Course & Exercises

1. Dichotomies to find the specified value of an ordered array.

Write a program binary_search(x, y), enter a list x (you can assume the data in it is already in ascending order) and enter the data y you want to find, so that the function returns the index of y, or "Not found" when y is not x.

def binary_search(x,y):
    a = 0
    b = len(x) #If it's 'len(x)-1' here, then it's a dead loop to find the last number
    c = (a+b)//2
    if y not in x. return 'Not found'
        return 'Not found'
    while x[c] ! = y:
        if x[c] < y:
            a = c
        elif x[c] > y:
            b = c
        c = (a+b)//2
    return c

python recursion

This question can only be written as a function of LOOP if it is asked in terms of the question, but it can also be solved by recursion.

def binary_search(min, max, d, n): '''initial mid=0, max=len(d)'''
    mid = (min+max)//2
    if n not in d. return 'Not found'
        return 'Not found'
    elif d[mid] < n:
        return binary_search(mid, max, d, n)
    elif d[mid] > n:
        return binary_search(min, mid, d, n)
        return mid

2. String (non-duplicate) full alignment

def permutation(array):
    if len(array) <= 1:
        return [array]
    res = []
    for i in range(len(array)):
        s = array[:i] + array[i+1:] # Take out one element at a time
        p = permutation(s) # Arrange the remaining elements in full
        for x in p:
            res.append(array[i:i+1]+x) #insert this element behind the remaining element

(Or it's as simple as writing a function to get rid of the duplicates.)

3. The stair climbing problem.

(####### 1) Assuming there are n steps, one or three steps at a time, how many possibilities are there to complete this section of steps?

(can be seen as a Fibonacci series)

def func(n):
    if n <= 2:
        return 1
    elif n == 3:
        return 2
    elif n > 3:
        return func(n-1) + func(n-3)

(###### 2) Assuming there are n steps, 1 or 3 steps at a time, list all the possible steps to complete this section

def func(n):
    res = []
    if n == 1:
        return '1'
    elif n == 2:
        return '11'
    elif n == 3:
        return ['111', '3']
    elif n > 3:
        for i in func(n-1):
            res.append(i + '1')
        for i in func(n-3):
            res.append(i + '3')
        return res

4. Tower of Hanoi

(####### 1) Suppose there are n discs in total, how many times do you need to move them?

def han(n):
    k = 0
    if n == 1:
        k += 1
    elif n > 1:
        k += 2*han(n-1) + 1
    return k

(##### 2) Assuming there are n discs in total, find the steps for each movement

def han(disc, frm, to, temp):
    if disc == 1:
        print('move disc' , 1, 'from', frm, 'to', to)
    elif disc > 1:
        han(disc-1, frm, temp, to)
        print('move disc' , disc, 'from', frm, 'to', to)
        han(disc-1, temp, to, frm)

5. List each letter in a string in full case

Write a program to read a string input and then output a list of all possible case permutations of the string.

def case_permutation(array):
    res = []
    if len(array) <= 1:
        return res
        s = array[0]
        array = array[1:]
        p = case_permutation(array)
        for x in p:
    return res

6. Judgment return.

def is_pal(line):
    n = len(line)
    if n <= 1:
        return True
    elif n <= 3:
        if linr[0] == line[n-1]:
            return True
        return False
            return False
    elif n > 3:
        if line[0] == line[n-1]:
            return is_pal(line[1:n-1]) '''Delete the first and last characters ''''
        return False
            return False

7. Looking for a power set.

(Here I've automatically defaulted the set to a list)

def power(s):
    res = []
    if len(s) == 1:
    elif len(s) > 1:
        for i in power(s[1:]):
    return res

So far I've sorted out so much, but once you've figured it out, you'll see that all the recursion core ideas are basically the same