How to use recursion to update a locally scoped variable

Question

Forgive me if this is too much of a general question but I seem to run into this problem frequently when I need to develop recursive algorithms which update some value on each recursive call. Please take this example below:

I want to make a recursive algorithm that accumulates the ages of the given profile and all the kids and kids of kids etc that exist within that profile.

Profile structure:

const profile = {
  name: 'peter',
  age: 56,
  kids: [{
    name: 'jill',
    age: 23,
    kids: [{
      name: 'jeter',
      age: 1
    }, {
      name: 'bill',
      age: 2
    }]
  }]
}

If I declare a variable outside of the scope of the function and update that it works. Like so:

let totalage = 0
function getAge(profile) {
  totalage = profile.age + totalage
  if(!profile.kids) return
  for(const kid of profile.kids) {
    getAge(kid)
  }
}
getAge( profile)
console.log(totalage)

By this logic, to make the function more reusable I want to make a shell function that sets up the age variable so it doesn't have to be globally declared any time I want to get all the ages, but this solution returns 0, the original age value:

function getAges(profile) {
  let age = 0
  recurs( profile, age)
  return age
}

function recurs(profile, age) {
  age = profile.age + age
  if(!profile.kids) return
  for(const kid of profile.kids) {
    recurs(kid, age)
  }
}
console.log(getAges(profile))

Any idea what is wrong?

Answer 1

This question has already attracted a nice variety of high-quality answers, and others have explained why your attempt fails.

I'd like to offer a variant of what user Thankyou suggested. We can flatten the nested structure into an array of objects, using a preorder traversal. Then if you need to do something involving all the the nodes, you can work with an array, which is often simpler. The code for that is straightforward:

const flatten = (prop) => (o) => 
  [o, ... (o [prop] ?? []) .flatMap (flatten (prop))]

const sum = (ns) => ns.reduce ((a, b) => a + b, 0)

const totalAges = (xs) =>
  sum (flatten ('kids') (xs) .map (p => p.age))

const profile = {name: 'peter', age: 56, kids: [{name: 'jill', age: 23, kids: [{name: 'jeter', age: 1}, {name: 'bill', age: 2}]}]}

console .log (totalAges (profile))

Here flatten takes a string representing the property name of items' children and returns a function that takes an object and traverses it preorder, collecting all the nodes in an array. We call this in totalAges, then pluck off the age properties of each node, finally passing this array to a simple sum function.

This is a simple enough technique, but we might want to make a generic version that passes a function such as node => node.age to directly collect the ages from our traversal. This turns out to be nearly as simple:

const gather = (prop) => (fn) => (o) => 
  [fn (o), ... (o [prop] ?? []) .flatMap (gather (prop) (fn))]

const sum = (ns) => ns.reduce ((a, b) => a + b, 0)

const totalAges = (xs) =>
  sum (gather ('kids') (p => p.age) (xs))

const profile = {name: 'peter', age: 56, kids: [{name: 'jill', age: 23, kids: [{name: 'jeter', age: 1}, {name: 'bill', age: 2}]}]}

console .log (totalAges (profile))

Here totalAges is slightly simpler as we hand off the application of p => p.age to our gather function. But the general logic is much the same.

---

This technique has one advantage over Thankyou's generator based-technique, and has two disadvantages that I know of. The first disadvantage is that this is subject to recursion depth-limits. Even if we fiddle to make this tail-call optimizable, most engines are still not taking advantage of that, so it could fail on extremely deeply nested object. (This would probably require an object with nodes thousands of levels deep; and if you have such a structure, you probably have other pressing problems too. But it's a valid concern.)

The second disadvantage is that this traversal cannot be cancelled. With a generator-based approach, you can stop early if you decide you're done. Perhaps you want to total the ages only so long as the total does not exceed 1000. That would be trivial in the generator-based approach, but is not really possible here. You could stop summing, but this technique would still traverse the entire tree.

The advantage is one of simplicity. The code to use this is often simpler, partly because there are many more utilities available for working with arrays than for working with iterators. You also get to work with pure expressions, and don't have to fiddle with loop variables and such.

Mind you, this advantage is minor. It's often enough for me to choose this technique over the generator one, but either should work well in practice.

(One minor note: there is no fundamental difference between these two approaches regarding the abstraction of prop and the value of kids. This version could easily be modified to embed kids in the main function, and in fact a partial application will create that, leaving only object -> array. And Thankyou's technique could quite easily be abstracted the way this one is with a prop parameter. That is much more a matter of taste than a fundamental difference.)

Answer 2

I would suggest separating your traverse logic from the sumAges logic. Not only does this simplify the task of each program, but it allows for greater reusability when traversal is needed in other parts of your program -

function* traverse(t)
{ yield t
  if (t.kids)
    for (const k of t.kids)
      yield *traverse(k)
}

function sumAges(t)
{ let sum = 0
  for (const node of traverse(t))
    sum += node.age
  return sum
}

const profile =
  {name: 'peter',age: 56,kids: [{name: 'jill',age: 23,kids:[{name: 'jeter',age: 1}, {name: 'bill',age: 2}]}]}

console.log(sumAges(profile)) // 82

Using the same traverse function we could easily collect all of the names in our tree -

function* traverse(t)
{ yield t
  if (t.kids)
    for (const k of t.kids)
      yield *traverse(k)
}

const profile =
  {name: 'peter',age: 56,kids: [{name: 'jill',age: 23,kids:[{name: 'jeter',age: 1}, {name: 'bill',age: 2}]}]}

const allNames = 
  Array.from(traverse(profile), node => node.name)

console.log(allNames)

[ "peter", "jill", "jeter", "bill" ]

Having traversal separate from makes it easy to write a rich variety of expressions -

function* traverse(t)
{ yield t
  if (t.kids)
    for (const k of t.kids)
      yield *traverse(k)
}

const profile =
  {name: 'peter',age: 56,kids: [{name: 'jill',age: 23,kids:[{name: 'jeter',age: 1}, {name: 'bill',age: 2}]}]}

for (const node of traverse(profile))
  console.log(`I am ${node.name} and I have ${node.kids?.length ?? 0} children`)

I am peter and I have 1 children
I am jill and I have 2 children
I am jeter and I have 0 children
I am bill and I have 0 children

Answer 3

I want to make a shell function that sets up the age variable so it doesn't have to be globally declared any time I want to get all the ages. Any idea what is wrong?

You need to declare the recurse function inside getAges, so that it has access to the age variable through closure. Notice that JS only has pass-by-value semantics for function calls, so when you pass a variable (age) as argument to a function, assigning to the parameter (age) will only update the local variable inside the function.

function getAges(profile) {
  let age = 0
  function recurs(profile, age) {
    age += profile.age
    if (!profile.kids) return
    for (const kid of profile.kids)
      recurse(kid)
  }
  recurse(profile)
  return age
}

console.log(getAges(profile))

But as the other answers mentioned, it is much better for recursion to make use of the return value, like in @Nick's or @ippi's snippets.

Answer 4

Creating a recursive function, you start with the base case, which is when the recursion should stop. (There may be more than one base case.)

Here it is when when the person in question has no kids.

function getAge(parent){
  // base case
  if (!parent.kids) return parent.age;

  // recursive call for each child
  return parent.kids.reduce((a, child) => a + getAge(child), parent.age);
}

I use a reduce to sum up an array of ints to handle more than one kid. (How to find the sum of an array of numbers)

The default is to not use an accumulator (let totalage = 0) to store the value between recursions. Because your function is not pure if it mutates an outside variable. Sure, you can have a wrapping function which stores the accumulator, and that function is pure. So in the end it's all about how anal you want to be.

Answer 5

Firstly, I want to fix your code to make it works.

const profile={name:'peter',age:56,kids:[{name:'jill',age:23,kids:[{name:'jeter',age:1},{name:'bill',age:2}]}]};

function getAges(profile) {
  return recurs(profile)
}

function recurs(profile, age = 0) {
  age += profile.age;
  if(profile.kids){
    for(const kid of profile.kids) {
      age += recurs(kid)
    }
  }
  
  return age;
}
console.log(getAges(profile))

Explanation:

As you can see, the recurs method should return a value. (That's the reason why you get zero value).

Secondly, you can refactor code like this.

const profile={name:'peter',age:56,kids:[{name:'jill',age:23,kids:[{name:'jeter',age:1},{name:'bill',age:2}]}]};

const getAge = (profile) => {
  let totalAge = profile.age;
  if(profile.kids){
    for(const kid of profile.kids){
        totalAge += getAge(kid);
    }
  }
  return totalAge;
}
console.log(getAge(profile));

Answer 6

General Programming languages have Local and global scope global is a scope that is available for every but in case of local it's only accessable within it's block in your code you are making two function first one getAges and second one is recurs age is local variable and only accessable within getAges not in recurs that's why you getting 0 in output. Okay, now move towards Solution one is that you can return a final value from recurs and store it in a variable and return that from getAges . Second one is to make recurs is aynonums function making it aynonums function you can get age directly into recurs due to js lexical environment. I hope this will helpful for you

Answer 7

You can return the age of this person plus all their kids from the recursive function; this can then be summed at the next level up (and so on) to return the total age of the profile:

const profile = {
  name: 'peter',
  age: 56,
  kids: [{
    name: 'jill',
    age: 23,
    kids: [{
      name: 'jeter',
      age: 1
    }, {
      name: 'bill',
      age: 2
    }]
  }]
}

function getAge(profile) {
  let totalage = profile.age;
  if (profile.kids) {
    for (const kid of profile.kids) {
      totalage += getAge(kid);
    }
  }
  return totalage;
}

console.log(getAge(profile));