Несколько рекурсии в одном операторе

Question

У меня есть вопрос, который спрашивает, сколько раз «1» печатается, если ниже код выполняется:

#!/usr/local/bin/python2.7 


def rec(n): 
    count = 1 
    if n > 0: 
     count += rec(n - 1) + rec(n - 1) 
    print '1' 
    return count   

rec(5) 

ответа = 63

При попытке решить выше проблемы, показанной выше, я был смущен определенными понятиями рекурсии.

1> Как подойти к проблемам с несколькими рекурсивными вызовами в одном утверждении. В вопросе, в каком порядке происходит рекурсия, одновременно или один за другим.

2> Я узнал (в C), что в рекурсивной функции всегда должно быть условие, которое определяет количество рекурсий, я не могу найти такое условие, поэтому как узнать количество уровни.

Answer 1

Давайте посмотрим его уровень на уровне:

rec(5) - you call once, print 1 once 
rec(4) - you call twice ONE AFTER ANOTHER (not in parallel). Print 1 twice. 
rec(3) - you call 4 times (called twice from the two rec(4)-s), print 1 four times. 
rec(2) - call 8 times, print 1 eight times 
rec(1) - call 16 times, print 1 sixteen times. 
rec(0) - call 32 times, print 1 32 times, but no further recursion called because n==0 

32 + 16 + 8 + 4 + 2 + 1 = 63

Как и в рекурсии, выполнение в исполнении снизу вверх, так что ваша рекомендация (0) из них будут напечатаны первые:

напечатанных из них:

rec(0) - 32 
rec(1) - 16 
rec(2) - 8 
rec(3) - 4 
rec(4) - 2 
rec(5) - 1 

Как вы можете видеть, вы можете легко обобщают т его случай для любого п в виде суммы рядов. В принципе, эта рекурсия двойного вызова ничем не отличается от простой рекурсии, за исключением того, что вы не называете уровни один раз, но 2^n раз.

Answer 2

над кодом, количество раз будет выдано заявление о печати для ввода 5, это верно. Давайте посмотрим, используя дерево. Каждый узел имеет 2 дочерних элемента, потому что функция вызывается 2 раза в рекурсии.

5 ----> 1

4 4 ----> 2 (дочерние узлы 5)

3 3 3 3 ---> 4 (дочерние узлы 4 и 4 (второй)) и аналогично

2 2 2 2 2 2 2 2 -----> 8

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ---> 16

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ---> 32

все сложить 1 + 2 + 4 + 8 + 16 + 32 = 63

так несколько раз печать будет выполняться, 63.