Как найти число рекурсивных вызовов - Исправление недочетов и поиск решений вместе с Examum.ru

How to track the number of recursive calls without using global variables in Python. For example, how to modify the following function to keep track the number of calls?

def f(n):
    if n == 1:
        return 1
    else:
        return n * f(n-1)

print f(5)

asked Jan 25, 2013 at 1:06

Here’s a neat trick that doesn’t use a global: you can stash the counter in the function itself.

def f(n):
    f.count += 1
    if n == 1:
        return 1
    else:
        return n * f(n-1)

After which:

>>> f.count = 0 # initialize the counter
>>> f(5)
120
>>> f.count
5
>>> f(30)
265252859812191058636308480000000L
>>> f.count
35

This handles the «all calls ever» case, anyhow.

answered Jan 25, 2013 at 1:14

DSMDSM

339k64 gold badges586 silver badges488 bronze badges

As delnan said, if you want all calls ever, it’s impossible without a global, so I’m assuming you just want the call depth, for which you just need to add a return value

def f(n):
    if n == 1:
        return 1,0
    else:
        x, call_depth= f(n-1)
        return n * x, call_depth+1

If you’re dealing with several recursive calls, you can do a max(call_depth1, call_depth2) (depth of longest call tree) or just sum the two (total number of actual calls)

answered Jan 25, 2013 at 1:12

loopbackbeeloopbackbee

21.6k10 gold badges60 silver badges96 bronze badges

This method will give you the total number of times the function has run:

def f(n):
    if hasattr(f,"count"):
        f.count += 1
    else:
        f.count = 1
    if n == 1:
        return 1
    else:
        return n * f(n-1)

answered Jan 25, 2013 at 1:33

Mike VellaMike Vella

10.1k14 gold badges59 silver badges86 bronze badges

Here’s a way that uses the stack instead of global variables. As shown it tallies the number of calls to the function including the initial one, not just the number of recursive calls the function made to itself. To make it do that, just move the ncalls += 1 to the beginning of the else statements.

def f(n, ncalls=0):
    ncalls += 1
    if n == 1:
        return 1, ncalls
    else:
        res, ncalls = f(n-1, ncalls)
        return n * res, ncalls

for n in xrange(1, 6):
    print 'f({}): {:4d} ({} calls)'.format(n, *f(n))

Output:

f(1):    1 (1 calls)
f(2):    2 (2 calls)
f(3):    6 (3 calls)
f(4):   24 (4 calls)
f(5):  120 (5 calls)

answered Jan 25, 2013 at 3:06

martineaumartineau

119k25 gold badges164 silver badges294 bronze badges

You could add an argument to keep count of the calls in (would need to be something mutable), where it gets incremented at the start of the function.

answered Jan 25, 2013 at 1:11

Scott HunterScott Hunter

48.6k12 gold badges57 silver badges100 bronze badges

Источник

Бедел

233 / 29 / 11

Регистрация: 04.06.2010

Сообщений: 293

Рекурсия, ряд Фибоначчи (определить количество рекурсивных вызовов функции)

22.05.2013, 03:20. Показов 6457. Ответов 12

Метки нет (Все метки)

Здравствуйте, уважаемые форумчане !

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

C++

int Fib1(int n)
{
    if ((n==1)||(n==2)) return(1);
    return(Fib1(n-2)+Fib1(n-1));
}

Я вроде сам сделал, но не уверен в правильности решения..
Заранее спасибо за ответ)

Programming Эксперт 94731 / 64177 / 26122 Регистрация: 12.04.2006 Сообщений: 116,782	22.05.2013, 03:20
12

cosmic

34 / 32 / 5

Регистрация: 29.08.2012

Сообщений: 84

Записей в блоге: 1

22.05.2013, 03:33

C++

int counter=0;
int Fib1(int n)
{
    if ((n==1)||(n==2)) return(1);
    {
    counter++;  
    return(Fib1(n-2)+Fib1(n-1));
    }
}
cin >> counter; // выводим число вызовов

что то в этом направлении.

Бедел

233 / 29 / 11

Регистрация: 04.06.2010

Сообщений: 293

22.05.2013, 03:37

[ТС]

Сообщение от cosmic

C++

int counter=0;
int Fib1(int n)
{
    if ((n==1)||(n==2)) return(1);
    {
    counter++;  
    return(Fib1(n-2)+Fib1(n-1));
    }
}
cin >> counter; // выводим число вызовов

что то в этом направлении.

Тут всё понятно, но мне выводить нужно число вызовов в главную функцию.

И вообще, у меня один вопрос:
В формуле Fib1(n-2)+Fib1(n-1) вызов функции происходит ведь два раза ? поэтому, нужно сделать counter+=2 ?

34 / 32 / 5

Регистрация: 29.08.2012

Сообщений: 84

Записей в блоге: 1

22.05.2013, 03:41

если я тебя правильно понял, то можно объявить счетчик статически или глобальным сделать, если нет предрассудков по этому поводу. По второму пункту не могу ответить, мозг переходит в режим сна )

233 / 29 / 11

Регистрация: 04.06.2010

Сообщений: 293

22.05.2013, 03:44

[ТС]

Без разницы, статический или глобальный) Жаль, второй пункт меня как раз-таки интересует больше всего) буду ждать, что ответят другие пользователи форума. Спасибо, что откликнулись)

henecs

18 / 18 / 11

Регистрация: 19.05.2013

Сообщений: 135

22.05.2013, 05:29

C++

int counter=0;
int Fib1(int n)
{  counter++;  // я бы написал так ибо функуия уже вызвана и она выполняеться
    if ((n==1)||(n==2)) return(1);
    else return (Fib1(n-2)+Fib1(n-1));
}
cin >> counter; // выводим число вызовов

как вариант еще можно в функцию передавать вторым параметром ссылку на счетчик

-1 / 1 / 0

Регистрация: 08.12.2019

Сообщений: 177

13.01.2021, 21:06

Вы так сильно парились насчет подсчета рекурсий вызовов ряда Фибоначчи, что даже забыли, что по факту это число является числом n (либо n+1, если учитывать 0)
Не благодарите))

6576 / 4561 / 1843

Регистрация: 07.05.2019

Сообщений: 13,726

13.01.2021, 21:18

Сообщение от nottheprogramer

n здесь не глубина рекурсии, а количество вызовов Fib1. Там вроде на каждой итерации два нерекурсивных вызова.

-1 / 1 / 0

Регистрация: 08.12.2019

Сообщений: 177

13.01.2021, 21:22

Сообщение от oleg-m1973

Там вроде на каждой итерации два нерекурсивных вызова.

То есть, я правильно понимаю, что получается число рекурсий 2(n+1)?

6576 / 4561 / 1843

Регистрация: 07.05.2019

Сообщений: 13,726

13.01.2021, 21:35

Сообщение от nottheprogramer

То есть, я правильно понимаю, что получается число рекурсий 2(n+1)?

Нет. Что-то типа log(N). Не путай количество вызовов функции с глубиной рекурсии. Если функция вызывается два раза подряд, вот так

Сообщение от Бедел

return(Fib1(n-2)+Fib1(n-1));

то глубина рекурсии здесь будет один, а количество вызовов — два. После вызова этих функций глубина рекурсии увеличится на один, а количество вызовов удвоится.

Добавлено через 4 минуты
При входе в функцию глубина рекурсии увеличивается, при выходе — уменьшается. Соответственно, простым суммированием здесь не обойтись, надо искать максимум.

0 / 0 / 0

Регистрация: 22.10.2020

Сообщений: 1

26.07.2021, 13:35

интеллектуальность этого треда(темы) просто зашкаливает

4023 / 3280 / 920

Регистрация: 25.03.2012

Сообщений: 12,263

Записей в блоге: 1

26.07.2021, 16:19

oleg-m1973, он прав, порядок 2 в степени n
каждое новое число фиб-чи считается двумя вызовами подсчёта предыдущего числа, то есть содержит в 2 раза больше вызовов, чем предыдущее, значит число номер n считается за 2 в степени n вызовов.
(пренебрегаем тем фактом, что один из рекурсивных вызовов — Fib1(n-2), а не Fib(n-1) считаем, что оба содержат
2 в степени n-1 вызовов)

2 / 2 / 0

Регистрация: 27.02.2022

Сообщений: 18

03.10.2022, 15:14

Это рабочий вариант, но если будет, допустим, миллиард вызовов, то прога будет долго работать

Источник

Задача такова: у меня есть функция, которая принимает на вход число, мне нужно разбить это число (если оно имеет больше 1 символа) на цифры и перемножить все эти цифры. Данное действие должно повторяться пока аргумент функции не станет одноразрядным числом. Ну и вывести мне нужно количество повторений этого алгоритма. То есть к примеру если функция принимает на вход 39 то нужно вывести 3, так как 3*9 = 27, 2*7 = 14, 1*4=4. Если принимает на вход 999 то 4, так как 9*9*9 = 729, 7*2*9 = 126,1*2*6 = 12,1*2 = 2 и тд. Для этой задачи я написал рекурсивный алгоритм. Вот и он:

static int count;
public static int Persistence(long n)
{
  count++;
  int position = 0;
  int[] array = n.ToString().Select(x => (int)Char.GetNumericValue(x)).ToArray(); //здесь я разделяю число на цифры
  if (n > 10)
      return Persistence(array[position] * array[position + 1]);
  return count;
}

public static void Main()
{
   Console.WriteLine(Persistence(4));
}

Моя проблема такова: алгоритм правильно работает только с двухразрядными числами, но вот если разрядов в числе больше, то алгоритм работает только с первыми двумя цифрами данного числа. Пример: если я введу число 999, то программа умножит первые две цифры, в итоге получится, что n = 81, мне же нужно чтобы все три девятки в этом числе перемножились и число n стало равно 729. Заранее спасибо за помощь.

Источник

Формулировка задачи:

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

#include <conio.h>
#include <stdio.h>
int factoriz (int x)
{
    int i,count=0;
    i=2;
 while (x!=1)    
 {
   while (x%i==0)
     {
      count++;
      printf("%in",i);
      x=factoriz(x/i);
     }
  i++;
 }
 return x;
}
int main(void)
{
 int x,count;
 printf("Vvedite 4islo: nn");
 scanf("%d",&x);
 printf("---------------nn");
 printf("1n");
 factoriz(x);
 printf ("Rekursivnuy funkciy bilo vizvano %i razn", count);
 getch();
 return 0;
}

Код к задаче: «Подсчитать количество вызовов рекурсивной функции»

textual

#include <conio.h>
#include <stdio.h>
int count=0;
int factoriz (int x)
{
    int i=2;
    count++;
 while (x!=1)    
 {
   while (x%i==0)
     {
      printf("%in",i);
      x=factoriz(x/i);
     }
  i++;
 }
 return x;
}
int main(void)
{
 int x;
 printf("Vvedite 4islo: nn");
 scanf("%d",&x);
 printf("---------------nn");
 printf("1n");
 factoriz(x);
 printf ("Rekursivnuy funkciy bilo vizvano %i razn", count);
 getch();
 return 0;
}

Полезно ли:

6 голосов , оценка 4.000 из 5

Источник

5 ответов

Передайте в качестве параметра в свой метод, первоначально заданный в 0 или 1 (в зависимости от ваших предпочтений), а затем увеличивайте его каждый раз, когда вы рекурсивно вызываете метод.

EDIT: Будучи честным, я не тестировал этот код, поэтому не могу понять, как вы должны изменять значения высоты. Такое ощущение будет бесконечно рекурсивным.

Во всяком случае, вот основная идея отслеживания числа рекурсии:

int height(Node root, int lCount, int rCount)
{
    if (root == null){
       return 0;
    }
    else {
        int lheight = height(root.left, lCount + 1, rCount);
        int rheight = height(root.right, lCount, rCount + 1);

        if (lheight > rheight){
            return(lheight);
        }
        else return(rheight); 
    }
}

Вы инициализируете вызов метода с высотой (root, 0, 0), а самое последнее выполнение L и R «ветвей» выполнения должно давать соответствующие итоговые значения.

HomerPlata
15 май 2017, в 08:29

Сделайте что-то вроде этого —

int height(Node root)
{
    if (root == null)
       return 0;
    else
    {
        return 1+ Math.max(height(root.left),height(root.right));
    }
}

Вычислить так называемый высотный вызов

int height = height(root); //this is the height not inside the function

Я не скомпилировал его, но это способ получить высоту дерева (c/c++/java/..)

Deb S
15 май 2017, в 08:16

Возьмите это, например

Во-первых, 1 будет левым [height (root.left)], поэтому назовем 2. Затем 2 пройдет левый так, что будет называться 4. Теперь 4 будет называть его левым.

так как 4 не осталось ни одного, он будет передавать значение null или 0 в lheight. Так что на этот раз код переходит к следующему шагу, т.е. к функции [height (root.right)].

Для права 4 мы имеем null, так что 0 будет возвращено на перемычки. Теперь с помощью [return (rheight + 1); ], значение 1 будет передано вызову функции 2.

так что 2 будет иметь lheight, как 1.Now 2 теперь вызовет его право. И так далее цикл продолжается, и 2 будет иметь два значения l = 1 и r = 1 и вернет 1 + 1 = 2 своей вызывающей функции, то есть 1.

вызывается право на 1, и оно будет возвращать 1 с тем же циклом, что и раньше. И, наконец, имеем l = 2 и r = 1. Поэтому наше окончательное значение будет [lheights + 1] = 3. поэтому высота дерева равна 3

Jay Patel
03 нояб. 2017, в 05:50

Высота дерева — это максимальная высота его левого под дерева и высота правого под дерева. Итак, если вы видите свой код, то он рекурсивно вычисляет высоту левого и правого поддерева и проверяет, что является максимальным. Если вы действительно хотите визуализировать его. создать древовидную структуру вызываемого метода. Вы можете легко визуализировать его.

Swapan Shaw
15 май 2017, в 09:17

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

int i;   //it has to be initialized with 0 


int height(Node root)
{
    if (root == null)
        return 0;
    else
    {
         i++;
         int lheight = height(root.left);
         printf("%d ", lheight);
         i++;
         int rheight = height(root.right);

         if (lheight > rheight)
             return(lheight);
         else return(rheight); 
     }
 }

EmLe49
15 май 2017, в 09:46

Ещё вопросы

1Получить дамп потока в браузере JS?
1Regex извлекает числа всех длин
0Почему мой конструктор копирования не работает с новым вызовом и имеет тот же адрес памяти?
1Почтовый клиент Swing выбрасывает javax.mail.AuthenticationFailedException
0jQuery и AngularJS не работают вместе. Работает ли сборщик даты и времени jQuery или работает угловой расчет
1Javascript document.cookie = «ключ = значение» добавляется вместо замены
0Как получить дочерние данные в Firebase, используя «PUSH» без какого-либо формата шифрования
1Обратная совместимая структура с новыми функциями
1Ошибка DOMException — Javascript play () может быть инициирован только жестом пользователя, но я вызываю его из touchStart
0Angular JS получить вопрос о входном значении
0c ++ читает из файла и совпадает с идентификатором
0Ошибка: «Ответ» не был объявлен в этой области
1Надувной замок: отдельные изменения подписи в конвертах при каждом запуске
1как передать объект коллекции в response.sendRedirect
0Загрузка данных об отдыхе в приложение Android Cordova с помощью AngularJs
0Показать ближе всего со спец. класс
0Отменить и повторить команду на холсте, используя fabric.js
1Преимущество привязки функций к именам в локальных областях?
0AngularJS: как искать текст на столе в угловых js?
1Используя Foreach в iQueryable List, найдите значение, если во втором списке
0Как я могу перефразировать мои сохраненные пароли, которые хранятся в базе данных, используя md5?
1Ошибка совпадения строки со списком строк с использованием extractOne () из fuzzywuzzy в python
0Summarize 3 столбца из 2 разных таблиц в SQL
0проблемы с поиском в базе данных, чтобы соответствовать вводу пользователя
1Ожидание непустой строки для ошибки параметра ‘providerInvariantName’ в приложении c #, имеющем базу данных доступа
1Нажмите на ссылку, используя селен вебдрайвер
1Почему мои темы не заканчиваются
0Создайте и загрузите файл CSV в один скрипт [дубликаты]
1Подтвердить с помощью REGEX alpha с поддержкой на многих языках
0AngularJs обрабатывает несколько флажков
0В пользовательском интерфейсе jQuery не работают вкладки пользовательского интерфейса jQuery (карта Google V3)
1Использование нескольких регулярных выражений в C # web crawler [duplicate]
0Средняя цена по категориям SQL-запрос
0Fitbit oauth регистрация
1Пропустить конвертацию сущностей при загрузке строки yaml (используя PyYAML)
0Проблема с функцией jQuery .click
0Остановить автообновление
0MySQL: выберите только некоторые сгруппированные строки со значениями, связанными с самым высоким ID
0Получить внешний HTML и затемнить / задержать полученные элементы
0Как обращаться с наследованием в реляционной базе данных
0Фон раздела div имеет необъяснимые отступы. Почему?
0Снимите флажок HTML с меткой
0Подсказка Highcharts показывает дополнительные данные
0JQuery обходится, чтобы добавить класс
1Как удалить все неиспользуемые переменные в WebStorm?
1Замена всех элементов, кроме последнего, в определенных строках 2D-массива
1Изменение состояния веб-приложения во время выполнения
0Как объявить класс с 1000000 элементов C ++
1Нажмите для удаленного хранилища

Источник