Как сделать счетчик в рекурсивной функции python

Отслеживать
ответ дан 24 сен 2019 в 10:39
16.4k 2 2 золотых знака 15 15 серебряных знаков 24 24 бронзовых знака

Можно не глобальную переменную делать, а например, через список count = [0] , а внутри функции count[0] += 1

24 сен 2019 в 10:40
Да, можно так. я просто, чтоб очевидней было
24 сен 2019 в 10:41

@gil9red, это все еще будет использованием глобальной переменной, несмотря на отсутствие ключевого слова global . Лучше уж как сейчас ("явное лучше неявного").

24 сен 2019 в 13:10

@insolor, если тот count = [0] передавать вторым параметром, это не будет глобальным использованием 🙂

Как сделать счетчик в рекурсивной функции python

Напомним, что в математике факториал числа n определяется как Например, Ясно, что факториал можно легко посчитать, воспользовавшись циклом for. Представим, что нам нужно в нашей программе вычислять факториал разных чисел несколько раз (или в разных местах кода). Конечно, можно написать вычисление факториала один раз, а затем используя Copy-Paste вставить его везде, где это будет нужно.

# вычислим 3! res = 1 for i in range(1, 4): res *= i print(res) # вычислим 5! res = 1 for i in range(1, 6): res *= i print(res)

Однако, если мы ошибёмся один раз в начальном коде, то потом эта ошибка попадёт в код во все места, куда мы скопировали вычисление факториала. Да и вообще, код занимает больше места, чем мог бы. Чтобы избежать повторного написания одной и той же логики, в языках программирования существуют функции.

Функции — это такие участки кода, которые изолированы от остальный программы и выполняются только тогда, когда вызываются. Вы уже встречались с функциями sqrt(), len() и print(). Они все обладают общим свойством: они могут принимать параметры (ноль, один или несколько), и они могут возвращать значение (хотя могут и не возвращать). Например, функция sqrt() принимает один параметр и возвращает значение (корень числа). Функция print() принимает переменное число параметров и ничего не возвращает.

Покажем, как написать функцию factorial(), которая принимает один параметр — число, и возвращает значение — факториал этого числа.

def factorial(n): res = 1 for i in range(1, n + 1): res *= i return res print(factorial(3)) print(factorial(5))

Дадим несколько объяснений. Во-первых, код функции должен размещаться в начале программы, вернее, до того места, где мы захотим воспользоваться функцией factorial(). Первая строчка этого примера является описанием нашей функции. factorial — идентификатор, то есть имя нашей функции. После идентификатора в круглых скобках идет список параметров, которые получает наша функция. Список состоит из перечисленных через запятую идентификаторов параметров. В нашем случае список состоит из одной величины n. В конце строки ставится двоеточие.

Далее идет тело функции, оформленное в виде блока, то есть с отступом. Внутри функции вычисляется значение факториала числа n и оно сохраняется в переменной res. Функция завершается инструкцией return res, которая завершает работу функции и возвращает значение переменной res.

Инструкция return может встречаться в произвольном месте функции, ее исполнение завершает работу функции и возвращает указанное значение в место вызова. Если функция не возвращает значения, то инструкция return используется без возвращаемого значения. В функциях, которым не нужно возвращать значения, инструкция return может отсутствовать.

Приведём ещё один пример. Напишем функцию max(), которая принимает два числа и возвращает максимальное из них (на самом деле, такая функция уже встроена в Питон).

10 20

def max(a, b): if a > b: return a else: return b print(max(3, 5)) print(max(5, 3)) print(max(int(input()), int(input())))

Теперь можно написать функцию max3(), которая принимает три числа и возвращает максимальное их них.

def max(a, b): if a > b: return a else: return b def max3(a, b, c): return max(max(a, b), c) print(max3(3, 5, 4))

Встроенная функция max() в Питоне может принимать переменное число аргументов и возвращать максимум из них. Приведём пример того, как такая функция может быть написана.

def max(*a): res = a[0] for val in a[1:]: if val > res: res = val return res print(max(3, 5, 4))

Все переданные в эту функцию параметры соберутся в один кортеж с именем a, на что указывает звёздочка в строке объявления функции.

2. Локальные и глобальные переменные

Внутри функции можно использовать переменные, объявленные вне этой функции

def f(): print(a) a = 1 f()

Здесь переменной a присваивается значение 1, и функция f() печатает это значение, несмотря на то, что до объявления функции f эта переменная не инициализируется. В момент вызова функции f() переменной a уже присвоено значение, поэтому функция f() может вывести его на экран.

Такие переменные (объявленные вне функции, но доступные внутри функции) называются глобальными.

Но если инициализировать какую-то переменную внутри функции, использовать эту переменную вне функции не удастся. Например:

def f(): a = 1 f() print(a)

Получим ошибку NameError: name 'a' is not defined . Такие переменные, объявленные внутри функции, называются локальными. Эти переменные становятся недоступными после выхода из функции.

Интересным получится результат, если попробовать изменить значение глобальной переменной внутри функции:

def f(): a = 1 print(a) a = 0 f() print(a)

Будут выведены числа 1 и 0. Несмотря на то, что значение переменной a изменилось внутри функции, вне функции оно осталось прежним! Это сделано в целях “защиты” глобальных переменных от случайного изменения из функции. Например, если функция будет вызвана из цикла по переменной i , а в этой функции будет использована переменная i также для организации цикла, то эти переменные должны быть различными. Если вы не поняли последнее предложение, то посмотрите на следующий код и подумайте, как бы он работал, если бы внутри функции изменялась переменная i.

def factorial(n): res = 1 for i in range(1, n + 1): res *= i return res for i in range(1, 6): print(i, '! = ', factorial(i), sep='')

Если бы глобальная переменная i изменялась внутри функции, то мы бы получили вот что:

5! = 1 5! = 2 5! = 6 5! = 24 5! = 120

Итак, если внутри функции модифицируется значение некоторой переменной, то переменная с таким именем становится локальной переменной, и ее модификация не приведет к изменению глобальной переменной с таким же именем.

Более формально: интерпретатор Питон считает переменную локальной для данной функции, если в её коде есть хотя бы одна инструкция, модифицирующая значение переменной, то эта переменная считается локальной и не может быть использована до инициализации. Инструкция, модифицирующая значение переменной — это операторы = , += , а также использование переменной в качестве параметра цикла for . При этом даже если инструкция, модицифицирующая переменную никогда не будет выполнена, интерпретатор это проверить не может, и переменная все равно считается локальной. Пример:

def f(): print(a) if False: a = 0 a = 1 f()

Возникает ошибка: UnboundLocalError: local variable 'a' referenced before assignment . А именно, в функции f() идентификатор a становится локальной переменной, т.к. в функции есть команда, модифицирующая переменную a , пусть даже никогда и не выполняющийся (но интерпретатор не может это отследить). Поэтому вывод переменной a приводит к обращению к неинициализированной локальной переменной.

Чтобы функция могла изменить значение глобальной переменной, необходимо объявить эту переменную внутри функции, как глобальную, при помощи ключевого слова global :

def f(): global a a = 1 print(a) a = 0 f() print(a)

В этом примере на экран будет выведено 1 1, так как переменная a объявлена, как глобальная, и ее изменение внутри функции приводит к тому, что и вне функции переменная будет доступна.

Тем не менее, лучше не изменять значения глобальных переменных внутри функции. Если ваша функция должна поменять какую-то переменную, пусть лучше она вернёт это значением, и вы сами при вызове функции явно присвоите в переменную это значение. Если следовать этим правилам, то функции получаются независимыми от кода, и их можно легко копировать из одной программы в другую.

Например, пусть ваша программа должна посчитать факториал вводимого числа, который вы потом захотите сохранить в переменной f. Вот как это не стоит делать:

def factorial(n): global f res = 1 for i in range(2, n + 1): res *= i f = res n = int(input()) factorial(n) # дальше всякие действия с переменной f

Этот код написан плохо, потому что его трудно использовать ещё один раз. Если вам завтра понадобится в другой программе использовать функцию «факториал», то вы не сможете просто скопировать эту функцию отсюда и вставить в вашу новую программу. Вам придётся поменять то, как она возвращает посчитанное значение.

Гораздо лучше переписать этот пример так:

# начало куска кода, который можно копировать из программы в программу def factorial(n): res = 1 for i in range(2, n + 1): res *= i return res # конец куска кода n = int(input()) f = factorial(n) # дальше всякие действия с переменной f

Если нужно, чтобы функция вернула не одно значение, а два или более, то для этого функция может вернуть список из двух или нескольких значений:

return [a, b]

Тогда результат вызова функции можно будет использовать во множественном присваивании:

Вычислить количество элементов списка с использованием рекурсивной функции

Вычислить сумму элементов списка с использованием рекурсивной функции
def rec_linear_sum(arr): if len(arr) == 0: return 0 else: Помогите дописать функцию.

Вычислить с использованием рекурсивной функции произведение элементов
Привествую, друзья. Помогите пожалуйста дойти до решения этой программы. Успешно сделать это не.

Дано натуральное число N. С использованием рекурсивной функции вычислить количество его цифр
Разработать алгоритм и программу, содержащую рекурсивную подпрограмму Дано натуральное число N.

Вычислить с использованием рекурсивной функции факториал
Вычислить с использованием рекурсивной функции факториала S = 1! + 4! + 7! +… + n! (число n.

36000 / 20115 / 4197
Регистрация: 12.02.2012
Сообщений: 33,307
Записей в блоге: 13

Сообщение было отмечено polinazarkov как решение

Решение

1 2 3 4 5

def size_list(a): if a==[]: return 0 else: return 1+size_list(a[1:])

691 / 474 / 204
Регистрация: 22.03.2020
Сообщений: 1,052

Сообщение было отмечено polinazarkov как решение

Решение

1 2 3 4

def foo(lst): if not lst: return 0 return 1 + foo(lst[1:])

87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
Помогаю со студенческими работами здесь

С использованием рекурсивной функции вычислить сумму
Помогите плиз)) Нужно составить программу с использованием рекурсивной функции вычислить сумму.

Произведение элементов одномерного массива с использованием рекурсивной функции
Пожалуйста помогите решите задачу: Произведение элементов одномерного массива с помощью рекурсивной.

С использованием рекурсивной функции осуществить вывод на экран элементов одномерного массива
Задание: С использованием рекурсивной функции осуществить вывод на экран элементов одномерного.

С помощью рекурсивной функции вычислить сумму элементов одномерного массива
С помощью рекурсивной функции вычислить сумму элементов одномерного массива,помогите.

С помощью рекурсивной функции вычислить сумму элементов одномерного массива
С помощью рекурсивной функции вычислить сумму элементов одномерного массива. Есть примеры но.

Или воспользуйтесь поиском по форуму:

Рекурсия в Python. Примеры решения задач

Рекурсия — это способ организации циклического процесса путем вызова рекурсивной функции. Рекурсивная функция — это функция, которая содержит код вызова самой себя с целью организации циклического процесса. С помощью рекурсивных функций можно с минимальным объемом кода решать некоторые задачи, обойдя использование (объявление) лишних структур данных. Рекурсию можно рассматривать как альтернативу циклам и итерациям.

2. Примеры решения задач на рекурсию

2.1. Функция CalcSumNumbers() . Вычислить сумму элементов набора чисел

В примере реализована рекурсивная функция CalcSumNumbers() , которая осуществляет суммирование чисел во входящем списке. В работе функции входящий список A разделяется на 2 части:

• первый элемент списка A[0] ;
• все остальные элементы списка кроме первого. Эти элементы выделяются при помощи среза A[1:] .

Вытащив первый элемент из списка с помощью среза, можно передать этот новосозданный список в следующий рекурсивный вызов функции.

# Рекурсивная функция - возвращает сумму чисел во входящем наборе def CalcSumNumbers(A): if A == []: # если набор пуст, возвратить 0 return 0 else: # Вычислить сумму - прибавить первый элемент набора summ = CalcSumNumbers(A[1:]) # рекурсивный вызов этой же функции # Прибавить к общей сумме первый элемент summ = summ + A[0] return summ # Демонстрация использования функции CalcSumNumbers() # 1. Создать набор чисел L = [ 2, 3, 8, 11, 4, 6 ] # 2. Вызвать функцию summ = CalcSumNumbers(L) # 3. Распечатать сумму print("summ color: #333300;">⇑ 
2.2. Функция CalcSumNegativeNumbers(). Вычислить количество отрицательных чисел в наборе
 
По предыдущим примеру (п. 4.1) реализуется функция CalcSumNegativeNumbers(), которая вычисляет количество отрицательных чисел в списке (наборе). Опять же, из входного списка выделяется первый элемент и все другие элементы.
 
# Рекурсивная функция - возвращает количество отрицательных чисел в списке def CalcSumNegativeNumbers(A): if A == []: # если набор пуст, вернуть 0 return 0 else: # Вычислить количество, перейти к дальнейшей обработке # без без первого элемента count = CalcSumNegativeNumbers(A[1:]) # рекурсивный вызов этой же функции # Увеличить на 1 при условии, что текущее число отрицательно if A[0]return count # Демонстрация использования функции CalcSumNumbers() # 1. Создать набор чисел L = [ -2, 3, 8, -11, -4, 6 ] # 2. Вызвать функцию n = CalcSumNegativeNumbers(L) # 3. Распечатать сумму print("n color: #333300;">⇑ 
2.3. Функция CalcSumNumbers(). Вычисление суммы чисел с поддержкой вложенных списков
 
Если нужно, чтобы рекурсивная функция обрабатывала вложенные списки, то в теле функции нужно реализовать цикл обхода элементов списка. Затем этот элемент нужно проверять, является ли он списком по образцу
 
if not isinstance(t, list): .
здесь t – элемент, который проверяется с помощью функции isinstance() .
# Рекурсивная функция - возвращает сумму чисел, обрабатывает вложенные списки def CalcSumNumbers(A): summ = 0 # здесь нужно реализовать обход в цикле for t in A: # Обрабатывается элемент t if not isinstance(t, list): # проверить, есть ли t списком summ = summ + t # если t - не список, то прибавить его к сумме else: # получить сумму из следующих рекурсивных вызовов summ = summ + CalcSumNumbers(t) return summ # Демонстрация использования функции CalcSumNumbers() # 1. Создать набор чисел L = [ -2, 3, 8, 11, [-4, 6, [ 2, [-5, 4] ] ] ] # 2. Вызвать функцию summ = CalcSumNumbers(L) # 3. Распечатать сумму print("summ color: #333300;">⇑ 
2.4. Функция GetFibonacciList(). Возврат ряда Фибоначчи
 
Ряд Фибоначчи содержит числа, в которых следующее число определяется как сумма двух предыдущих чисел:
 
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, .
Нижеприведенная рекурсивная функция формирует ряд Фибоначчи в виде списка для заданного максимального значения в списке.
2.5. Функция ReverseNumber() . Реверсирование числа
В примере приводится функция ReverseNumber() представления числа в обратном порядке. Например, для числа 12345 результат будет 54321.
Функция получает входным параметром целое число number . Функция возвращает целое реверсированное число.
# Рекурсия. Реверсирование числа import math # Рекурсивная Функция def ReverseNumber (num): # 1. Проверка, корректно ли число if num0), то обработать его # 3.1. Определить порядок числа (количество цифр в числе) n_digit = 0 # порядок числа num2 = num # копия num while num2>0: n_digit = n_digit+1 num2 = num2//10 # 3.2. Взять последнюю цифру из числа t = num%10 # 123456 => 6 # 3.3. Умножить последнюю цифру на 10^n_digit res = t * int (math.pow(10, n_digit-1)) # 3.4. Вернуть сумму с вызовом рекурсивной функции return res + ReverseNumber(num//10) # Демонстрация использования функции num = 1234000567 rnum = ReverseNumber(num) # rnum = 7650004321 print ( "rnum color: #333300;">⇑ 

2.6. Функция Power(x, y) . Возведение числа x в степень y
Рекурсивная функция Power(x, y) возвращает результат возведения действительного числа x в целую степень y . Предварительно предполагается, что значение y>0 .
# Рекурсия. Возведение числа x в степень y # Рекурсивная функция def Power (x, y): if y>0: return x * Power(x, y-1) else : return 1 # Демонстрация использования функции Power() x = 3 y = 4 res = Power(x, y) print ( "res color: #333300;">⇑ 

2.7. Функция GetMaxList() . Определение максимального элемента списка
В примере реализована функция GetMaxList() , которая вычисляет максимальный элемент списка. Вся работа функции разделена на 2 части:

выполнение действий, если в списке два и более чисел;
выполнение действий, если список заканчивается, то есть рассматривается последний элемент.

Каждый рекурсивный вызов функции рассматривает список как две составляющие:

первый элемент списка (элемент с индексом 0);
следующие за первым элементы списка (элементы с индексами 1, 2, и т.д.).

# Рекурсивная функция. Определить максимальный элемент списка def GetMaxList (L): if len (L)>1: # Получить максимум из следующих рекурсивных вызовов Max = GetMaxList(L[1:]) # Сравнить максимум с первым элементом списка if L[0]⇑ 

2.8. Функция Convert_10_to_2() . Перевод из десятичной системи исчисления в двоичную
В данном примере, с целью сравнения, реализованы 2 функции, которые конвертируют целое число из десятичной системы исчисления в его аналог в двоичной системе исчисления:

Convert_10_to_2_R() — это рекурсивная функция конвертирования числа;
Convert_10_to_2() — не рекурсивная функция.

Для обеспечения решении задачи, в нерекурсивной версии Convert_10_to_2() вводится дополнительная переменная k , которая определяет порядок полученного двоичного числа. Для того, чтобы сохранять этот порядок k в рекурсивной версии функции Convert_10_to_2_R() , нужно его передавать в эту функцию вторым параметром.
import math # Рекурсивная функция. Перевод числа из 10-й системы исчисления в двоичную. # Функция возвращает результат в виде числа: 13 => 1101. # Параметры: # - n - число в десятичной системе исчисления; # - k - текущий порядок (количество цифр) числа в двоичной системе. def Convert_10_to_2_R (n, k): if n>0: t = n%2 return Convert_10_to_2_R(n//2, k+1) + int (t*math.pow(10,k)) else : return 0 # Не рекусивная функция перевода def Convert_10_to_2 (n): summ = 0 # сумма чисел: 5 => 100 + 0 + 1 => 101 k = 0 # порядок числа в двоичной системе исчисления while n>0: t = n%2 summ = summ + int (t*math.pow(10,k)) k = k+1 n = n//2 return summ # Демонстрация использования функций res1 = Convert_10_to_2_R(126, 0) # Вызов рекурсивной функции res2 = Convert_10_to_2(126) # Вызов нерекурсивной функции print ( "res1 color: #800080;">print ( "res2 color: #333300;">⇑ 

Связанные темы

Понятие функции. Общая форма. Примеры объявления и использования функций
Передача аргументов в функцию. Изменение аргументов в теле функции



Похожие публикации:

Как отключить обновление телеграмм через гугл
Как привязать фейсбук к пабг мобайл
Как сохранить файл excel в формате dbf
Как тестируют в google купить