Why is it dangerous to use ref in a recursive method?

Question

I was solving the following problem on leetcode:

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

Following is the specific problem I was solving:

And following is the code I wrote, that solves this specific problem - where the targetSum=22 (and this solution is Accepted by leetcode) :

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
 }



namespace BinaryTree
{
    internal class Program
    {
        static void Main(string[] args)
        {
            TreeNode root = new TreeNode(5);
            TreeNode a = new TreeNode(4);
            TreeNode b = new TreeNode(11);
            TreeNode c = new TreeNode(7);
            TreeNode d = new TreeNode(2);
            TreeNode e = new TreeNode(8);
            TreeNode f = new TreeNode(13);
            TreeNode g = new TreeNode(4);
            TreeNode h = new TreeNode(1);
            root.left = a;
            root.left.left= b;
            root.left.left.left = c;
            root.left.left.right= d;
            root.right = e;
            root.right.left= f;
            root.right.right= g;
            root.right.right.right= h;
            int targetSum = 22;
            bool hasPathSum = HasPathSum(root, targetSum);
        }

        static bool HasPathSum(TreeNode root, int targetSum)
        {
            if (root == null)
                return false;
            int currentSum = 0;
            return PathSum(root, targetSum, currentSum);
        }

        static bool PathSum(TreeNode root, int targetSum, int currentSum)
        {
            if (root == null)
                return false;
            currentSum += root.val;
            bool lPath = PathSum(root.left, targetSum, currentSum);
            bool rPath = PathSum(root.right, targetSum, currentSum);
            if (root.left == null && root.right == null && currentSum == targetSum)
                return true;
            else if (lPath == true || rPath == true)
                return true;
            return false;
        }
     }
  }

The code works fine because currentSum is a local variable on the stack, and as each stack frame is popped out of the stack, the current value of currentSum is also popped out of the stack and currentSum restores to its previous value (I drew this on paper). And at the end of all recursive calls to PathSum, the currentSum=5 (that is, the value of the original root that we started with).

But a problem arises when we pass currentSum as ref into the method PathSum (the same code above where currentSum is passed by ref is below):

static bool HasPathSum(TreeNode root, int targetSum)
{
    if (root == null)
        return false;
    int currentSum = 0;
    return PathSum(root, targetSum, ref currentSum);
}

static bool PathSum(TreeNode root, int targetSum, ref int currentSum)
{
    if (root == null)
        return false;
    currentSum += root.val;
    bool lPath = PathSum(root.left, targetSum, ref currentSum);
    bool rPath = PathSum(root.right, targetSum, ref currentSum);
    if (root.left == null && root.right == null && currentSum == targetSum)
        return true;
    else if (lPath == true || rPath == true)
        return true;
    return false;
}

I also drew what is happening on the stack here and, as we visit each node in the Binary Tree recursively, the line currentSum+=root.val in the method PathSum adds up all the values of the roots that we have visited till now. And at the end of all the recursive calls to PathSum, currentSum=55 (sum of all the values of all the nodes in the binary tree).

I believe this is happening because when we pass currentSum by ref, we are infact passing the address of currentSum (similar to &currentSum in C/C++). And since the Argument and Parameter of PathSum is the address of currentSum, currentSum+=root.val keeps on adding the values of all visited roots to currentSum. Is my assumption correct?

Any further light on this will be much appreciated.

Answer 1

Why is it dangerous to use ref in a recursive methods?

It is not.

I believe this is happening because when we pass currentSum by ref, we are in fact passing the address of currentSum ...

That is basically what is written in the docs for ref keyword in Passing an argument by reference section:

When used in a method's parameter list, the ref keyword indicates that an argument is passed by reference, not by value. The ref keyword makes the formal parameter an alias for the argument, which must be a variable. In other words, any operation on the parameter is made on the argument.

For example, suppose the caller passes a local variable expression or an array element access expression. The called method can then replace the object to which the ref parameter refers. In that case, the caller's local variable or the array element refers to the new object when the method returns.

Which is neatly demonstrated by the code snippet from the same doc:

void Method(ref int refArgument)
{
    refArgument = refArgument + 44;
}

int number = 1;
Method(ref number);
Console.WriteLine(number); // Output: 45

So yes, in your case the result will be that all recursive calls will modify the same "root" currentSum variable (which can be what you need in some cases, but not always).

Read also:

• Method Parameters:

  In C#, arguments can be passed to parameters either by value or by reference. Remember that C# types can be either reference types (class) or value types (struct):

  • Pass by value means passing a copy of the variable to the method.
  • Pass by reference means passing access to the variable to the method.
  • A variable of a reference type contains a reference to its data.
  • A variable of a value type contains its data directly.

• C# pass by value vs. pass by reference