# Understanding how recursive functions work

As the title explains I have a very fundamental programming question which I have just not been able to grok yet. Filtering out all of the (extremely clever) "In order to understand recursion, you must first understand recursion." replies from various online threads I still am not quite getting it.

Understanding that when faced with not knowing what we don't know, we can tend to ask the wrong questions or ask the right questions incorrectly I will share what I "think" my question is in hopes that someone with a similar outlook can share some bit of knowledge that will help turn on the recursive light bulb for me!

Here is the function (the syntax is written in Swift):

``````func sumInts(a: Int, b: Int) -> Int {
if (a > b) {
return 0
} else {
return a + sumInts(a: a + 1, b: b)
}
}
``````

We'll use 2 and 5 as our arguments:

``````println(sumInts(a: 2, b: 5))
``````

Obviously the answer is 14. But I'm not clear on how that value is achieved.

These are my 2 hangups:

1. The function is called recursively until a condition is met. That condition is a > b. When this condition is met, return 0. At first glance, I would expect the return value to be 0 which is obviously incorrect.

2. Printing out the value of 'a' on each iteration yields a value which I would expect: 2, 3, 4, 5 (at which point 5+1 > b which meets the first condition: a > b) but I still don't see how the value of 14 is achieved.

My first thought is that something similar to the following is happening magically:

``````var answer = a;
answer += a+1 until a > b;
``````

So ruling out magic, I'm just not getting something. I would love to understand what's happening more than just implicitly.

If someone could kindly explain what technically happens during this kind of function and why the result isn't 0 and how, eventually, `a + sumInts(a: a + 1, b: b) = 14`, I would be forever in your debt.

89

I think the confusion is stemming from thinking of it as "the same function" being called many times. If you think of it as "many copies of the same function being called", then it may be clearer:

Only one copy of the function ever returns 0, and it's not the first one (it's the last one). So the result of calling the first one is not 0.

For the second bit of confusion, I think it will be easier to spell out the recursion in English. Read this line:

``````return a + sumInts(a + 1, b: b)
``````

as "return the value of 'a' plus (the return value of another copy of the function, which is the copy's value of 'a' plus (the return value of another copy of the function, which is the second copy's value of 'a' plus (...", with each copy of the function spawning a new copy of itself with a increased by 1, until the a > b condition is met.

By the time you reach the the a > b condition being true, you have a (potentially arbitrarily) long stack of copies of the function all in the middle of being run, all waiting on the result of the next copy to find out what they should add to 'a'.

(edit: also, something to be aware of is that the stack of copies of the function I mention is a real thing that takes up real memory, and will crash your program if it gets too large. The compiler can optimize it out in some cases, but exhausting stack space is a significant and unfortunate limitation of recursive functions in many languages)

Tuesday, June 1, 2021

60

In a pure functional style, you'll never overwrite any variable.

An analogy would be to spacetime in physics. If you consider the world as 3d, then objects don't have fixed positions - they move over time. To bring math to bear on the physical world, we therefore add a time dimension and consider the values of various properties at particular times. In doing so, we've made the objects of our study into constants. Similarly, in programming, there is a conceptual simplicity to be had by working with immutable values. Objects with an identity in the real world can be modeled as a sequence of immutable values (the states of the object at increasing times) rather than as a single value that changes.

Of course the details of how to associate the sequence of values to an "object identity" can be a little hairy. Haskell has Monads that let you model state. Functional Reactive Programming is a more literal attempt at modeling objects in the world with pure functional updates, that I think is a very promising direction for programming.

I will note that Clojure, unlike Haskell, isn't pure, and you can update variables as you suggested. If you're only updating a few variables at a high level, you'll still probably enjoy many of the conceptual simplicity benefits of functional programming.

Sunday, August 1, 2021

92

I want a user to be able to select a rule from the dropdownlist, and depending upon which rule was selected, I would like a label on the page to show the rule name (without posting)

You will need javascript here. jQuery would be perfect for the job. I would start by providing a deterministic id for the dropdown because if you run this view inside a template there could be prefixes added to the id which would ruin our javascript id selectors (see below):

``````@Html.DropDownListFor(
x => x.D1K2N3CARules,
new SelectList(Model.D1K2N3CARules, "ID", "Rule"),
new { id = "ruleDdl" }
)
``````

then provide some container which will receive the selected value:

``````<div id="ruleValue" />
``````

and finally in a separate javascript file subscribe for the change event of the dropdown list and update the container with the selected value/text:

``````\$(function() {
// subscribe for the change event of the dropdown
\$('#ruleDdl').change(function() {
// get the selected text from the dropdown
var selectedText = \$(this).find('option:selected').text();

// if you wanted the selected value you could:
// var selectedValue = \$(this).val();

// show the value inside the container
\$('#ruleValue').html(selectedText);
});
});
``````

I also need to be able to send the selected rule onto the next page.

You could put your dropdown inside a form

``````@using (Html.BeginForm("NextPage", "Foo"))
{
@Html.DropDownListFor(
x => x.D1K2N3CARules,
new SelectList(Model.D1K2N3CARules, "ID","Rule")
)
<input type="submit" value="Go to the next page" />
}
``````

and the NextPage controller action will receive the selected value.

Wednesday, August 18, 2021

56

`panel1` - the control on your form
`.controls` - the list of controls added to `panel1`
`.OfType<UserControl1>()` - only controls that are of type `UserControl1`
`.Select(uc => uc.combobox2)` - the `combobox2` property (of each `UserControl1` (in `panel1`))
`.Any(cb => cb.Text == String.Empty)` - evaluates to true if any of those comboxbox's `Text` property is an empty string.

So basically if any of the `Text` property of the `combobox2` property of the `UserControl1`'s added to your `panel1` control is empty, then return `true`, otherwise `false`.

Some explanation about `.Select(uc => uc.comboxbox2)`.

This is saying call each item in the collection `uc`. For each `uc` return the value created on the right of the `=>`. In that case it's `uc.combobox2`. Imagine doing that to a single one, well you'd get a variable of type `ComboBox` (i'd guess). Because this is in the context of the `Select` method, we will do that for each item. Doing it for all of them means you get a collection of them, based on your collection of `UserControl1`'s.

Regarding `.Any(cb => cb.Text == String.Empty)` The parameter to the `Any` method is the same thing as above, however it might be confusing as the part "on the right of the `=>`" is in this case something that evaluates to `true` or `false`. The `Any` method expects something that transforms each item in a collection (a `ComboBox` in this case) into a true or false. It will then return true if any of those transform into `true`, and if not then it'll return `false`.

Friday, September 3, 2021

21

Here is the fastest purely functional solution I can think of:

``````def isUniqueList(l: List[T]) = isUniqueList1(l, new HashSet[T])

@tailrec
def isUniqueList1(l: List[T], s: Set[T]) = l match {
case Nil => true
case (h :: t) => if (s(h)) false else isUniqueList1(t, s + h)
}
``````

This should be faster, but uses mutable data structure (based on the `distinct` implementation given by Vasil Remeniuk):

``````def isUniqueList(l: List[T]): Boolean = {
val seen = mutable.HashSet[A]()
for (x <- this) {
if (seen(x)) {
return false
}
else {
seen += x
}
}
true
}
``````

And here is the simplest (equivalent to yours):

``````def isUniqueList(l: List[T]) = l.toSet.size == l.size
``````
Tuesday, September 28, 2021

Not the answer you're looking for? Browse other questions tagged :
Share