Python Recursion Behavior

Question

I have studied recursion, especially in Python, and think I get it. I have learned this form:

def f_Listsum(numList):
   if len(numList) == 1:
       return numList[0] ## Triggers the unwinding of the recursion stack
   else:
       return numList[0] + f_Listsum(numList[1:]) ## Winds up the recursion stack with a shorter and shorter slice of org. list.

I get it. The recursive calls sort of "wind" things up, and then a stop or "trigger" causes the recursion to collapse into itself and consume the resulting values.

However I ran into this today:

def f_DecToBinary(v_Num):
    if v_Num > 1:
        f_DecToBinary(v_Num // 2)
    print(v_Num % 2,end = '')

I wanted to substitute the function's "print" with a return of a string, or even a list of INTs, but I can't get it to work, as I don't understand how this recursion is operating. I see that it calls itself each time, and then initiates a collapse when v_Num == 1 or less, but it collapses to outside the "if" statement and then I get lost. When I try to assemble a STR or LIST from the collapse instead of just printing it, I errors or just the last digit returned.

My questions are: How does f_DecToBinary work/function, and how can I capture the output into a string?

Some examples:

print(f_Listsum([1,3,5,7,9])) ## 25
print()
f_DecToBinary(15) ## 1111

Thanks

// , The way that you worded "The recursive calls sort of "wind" things up, and then a stop or "trigger" causes the recursion to collapse into itself and consume the resulting values." suggests that you have had the chance to look at where and how recursive functions break. How did you go about inspecting their values, @JayJay123? — Nathan Basanese
– Nathan Basanese, Commented Jun 27, 2015 at 21:02

dlask · Accepted Answer · 2015-06-01 20:03:37Z

3

def DecToBinary(n):
    if n >= 2:
        return DecToBinary(n // 2) + str(n % 2)
    else:
        return str(n)

answered Jun 1, 2015 at 20:03

dlask

9,0321 gold badge29 silver badges31 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

dlask Over a year ago

I appreciate your question. It's useful to understand recursion.

Mark Ransom · Accepted Answer · 2015-06-01 20:05:04Z

3

Follow the typical flow through the function. It will call itself, which causes some output, then it prints a single digit. So the single digit comes at the end of the previous ones. To return the result instead of printing it, you need to take the result of the recursive call and add the current result to the end of it.

answered Jun 1, 2015 at 20:05

Mark Ransom

310k44 gold badges423 silver badges660 bronze badges

1 Comment

JayJay123 Over a year ago

Thank you that was of some assistance.

bterwijn · Accepted Answer · 2025-03-08 12:25:32Z

You can use package invocation_tree to visualize program execution which is especially helpful with recursion. Here I use the suggestion by dlask:

import invocation_tree as ivt # see above link for install instruction

def DecToBinary(n):
    if n >= 2:
        return DecToBinary(n // 2) + str(n % 2)
    else:
        return str(n)

tree = ivt.blocking()
result = tree(DecToBinary, 27) # show invocation tree of DecToBinary(27)
print('result:', result)

That after pressing <Enter> a number of times to step through the program, results in:

I hope this visualization will help you with program understanding and debugging.

Full disclosure: I am the developer of invocation_tree.

Collectives™ on Stack Overflow

Python Recursion Behavior

3 Answers 3

1 Comment

1 Comment

Comments

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

1 Comment

Comments

Related