Why is the function returning value of stack as None

Question

I'm not able to figure out why the path variable on last line of the code is being printed out as None. As you can see the second last line of the code is calling the DFS function to find the path between two nodes in a tree (I'm giving a tree as input). I've printed out the value of the stack also before returning it to make sure that it is not None and while being printed inside DFS function it is not None. But I'm not able to understand why it is None when it is returned and stored in path variable. I gave this as input
1
6 1
4 2 1 3 5 2
1 2
2 3
2 4
1 5
5 6
And the out put came as
{0: [1, 4], 1: [0, 2, 3], 2: [1], 3: [1], 4: [0, 5], 5: [4]}
[0, 1, 3]
None
Here is the code for reference

def DFS(adj,x, y,stack,vis):
    stack.append(x)
    if (x == y):
        print(stack)
        return stack
    vis[x] = 1

    if (len(adj[x])>0):
        for j in adj[x]:
            if (vis[j]==0):
                DFS(adj,j,y,stack,vis)
    del stack[-1]
T = int(input())
for a in range(T):
    N,Q = input().split()
    N = int(N)
    Q = int(Q)
    wt = [int(num) for num in input().split(" ")]
    adj = {}
    for i in range(N):
        adj[i] = []
    for b in range(N-1):
        u,v = input().split()
        u = int(u) - 1
        v = int(v) - 1
        adj[u].append(v)
        adj[v].append(u)
    print(adj)
    vis = [0]*N
    stack = []
    path = DFS(adj,0,3,stack,vis)
    print(path)

Your function ```DFS()``` isn't returning any values for certain conditions. — ewokx, Apr 11 '22 at 05:25
@BeRT2me can you tell me how would you modify the code so that I get the path at the end of executing the above code with the given input ? — Partha Thakuria, Apr 11 '22 at 06:02
@ewong can you tell me how would you modify the code so that I get the path at the end of executing the above code with the given input ? — Partha Thakuria, Apr 11 '22 at 06:03
As @BeRT2me mentioned, ```if x != y```, then you have a None return. You need to include other possible conditions in your ```DFS``` function. — ewokx, Apr 11 '22 at 06:07
Does this answer your question? [Why does my recursive function return None?](https://stackoverflow.com/questions/17778372/why-does-my-recursive-function-return-none) — VLAZ, Apr 11 '22 at 06:13
@ewong as the input to the code is a tree and the condition (x == y) is executed only once and executes for sure, it should return the value of the stack = [0,1,3] as evident from the output and that is the only return statement and returns for sure. So [0,1,3] should be assigned to the value of the variable "path". Can you tell me what is the logical flaw in this ? The function returns value for all arguments as all the inputs for the program will be tree and a path exists for all nodes in a tree. — Partha Thakuria, Apr 11 '22 at 06:59
@VLAZ no. Can you tell me which line of my code should I change so that I don't get None as output ? I want [0,1,3] as output. Which is actually the value of stack before it is returned when it is printed out on line no 4 of the code. — Partha Thakuria, Apr 11 '22 at 08:15
`DFS(adj,j,y,stack,vis)` -> `return DFS(adj,j,y,stack,vis)` - exactly like the duplicate says: you're not returning the value of the recursive call. — VLAZ, Apr 11 '22 at 08:19
@VLAZ but after doing this when I print the stack, that also comes as None. Before atleast when I printed out the stack I knew that it was same as the output i wanted. — Partha Thakuria, Apr 11 '22 at 12:24

score -1 · Answer 1 · answered Apr 11 '22 at 16:34

Simple equivalent of your code:

def recursive_func(x):
    if x > 0:
        return x
    else:
        x += 1
        recursive_func(x)

x = 5
x = recursive_func(x)
print(x)

x = 0
x = recursive_func(x)
print(x)

Output:

5
None

What's happening here?

x, with a value of 5 is sent to recursive_func.
x is greater than 0, so 5 is returned. This is seen in the output.
x, with a value of -5 is sent to recursive_func.
x is not greater than 0, so 1 is added to x.
x, with a value of 1, is then sent to a different recursive_func.
This recursive_func returns 1 because 1 > 0.
This response gets passed to the first recursive_func where the line recursive_func(x) becomes 1, but we don't do anything with it.
recursive_function hits the end of its code, without returning a value. By default None is returned to our main body.
x = recursive_func(x) has become x = None
None is output.

Given this information, why does the following code perform differently?

Simple modification of your code:

def recursive_func_v2(x):
    if x > 0:
        return x
    else:
        x += 1
        return recursive_func_v2(x)

x = 5
x = recursive_func_v2(x)
print(x)

x = 0
x = recursive_func_v2(x)
print(x)

Output:

5
1

Why is the function returning value of stack as None

1 Answers1

Simple equivalent of your code:

Given this information, why does the following code perform differently?