Why does the following executes such that the print statement is called as often as it recursed but the count variable, count, when x == 1 is never reached.

def count_bits(n, count = 0):
  x = n % 2
  if n == 1:
    return count   1
  
  if n < 1:
    return count

  if x == 1:
    count  = 1 # when x == 1
  
  count_bits(int(n/2), count)
  print("counter")

  return count
  

why is it necessary to recurse with the return statement? Because if the recursive call is above the return statement the code returns the wrong output but with the recursive call called with return keyword, everything works well. Typically, the print statement prints 'counter' as often as it recursed showing that the recursive call works.

On the other hand, if "return" follows after the recursive call, it returns the count from the base condition, correctly.

def count_bits(n, count = 0):
  x = n % 2
  if n == 1:
    return count   1
  
  if n < 1:
    return count

  if x == 1:
    count  = 1

  return count_bits(int(n/2), count)

CodePudding user response：

You have to return recursion result, as reccurent function meaning is to count current step you have to get result of previous step

F_k = F_k-1 * a   b  # simple example

Means that you have to get result of F_k-1 from F_k and count current result using it.

CodePudding user response：

I advised you to use snoop package to debug your code more efficient , by this package you can track the executing step by step. to install it run:

Pip install snoop

Import snoop

add snoop decorator to count_bits()

for about the package see this link https://pypi.org/project/snoop/

CodePudding user response：

the difference in the output between the two methods is because of the way in which python handles fundamental data types. Fundamental data types such as float, ints, strings etc are passed by value, whereas complex data types such as dict, list, tuple etc are passed by reference. changes made to fundamental data types within a function will therefore only be changed within the local scope of the function, however changes made to a complex data type will change the original object. See below for an example:

x = 5

def test_sum(i : int):
  print(i)
  i  = 5
  print(i)

# the integer value in the global scope is not changed, changes in test_sum() are only applied within the function scope
test_sum(x)
print(x)

y = [1,2,3,4]

def test_append(l : list):
  print(l)
  l.append(10)
  print(l)

# the list in the global scope has '10' appended after being passed to test_append by reference
test_append(y)
print(y)

This happens because it's far cheaper computationally to pass a reference to a large object in memory than to copy it into the local scope of the function. For more information on the difference, there are thousands of resources available by searching "what is the difference between by reference and by value in programming".

As for your code, it seems to me the only difference is you should alter your first snippet as follows:

def count_bits(n, count = 0):
  x = n % 2
  if n == 1:
    return count   1
  
  if n < 1:
    return count

  if x == 1:
    count  = 1 # when x == 1
  
  # assign the returned count to the count variable in this function scope
  count = count_bits(int(n/2), count)
  print("counter")

  return count

The second code snippet you wrote is almost identical, it just doesn't assign the new value to the 'count' variable. Does this answer your question?