EzDevInfo.com

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;
return answer;   

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.

What is recursion and when should I use it?

One of the topics that seems to come up regularly on mailing lists and online discussions is the merits (or lack thereof) of doing a Computer Science Degree. An argument that seems to come up time and again for the negative party is that they have been coding for some number of years and they have never used recursion.

So the question is:

1. What is recursion?
2. When would I use recursion?
3. Why don't people use recursion?

How can I find all matches to a regular expression in Python?

In a program I'm writing i have python use the re.search() function to find matches in a block of text and print the results. However, once the program finds the first match in the block of text, it exits. How do i do this repeatedly where the program doesn't stop until ALL matches have been found? Is there a separate function to do this? Thanks in advance!

How to search a string in multiple files and return the names of files in Powershell?

I have started learning powershell a couple of days ago, and I couldn't find anything on google that does what I need so please bear with my question.

I have been asked to replace some text strings into a Jboss application running on windows. I do not necessarily know the extension of the possible target files and I don't know their location either. So far I have managed to recursively browse into the directory (get-ChildItem -recurse) and find the string I was looking for with get-content and select-string:

Get-ChildItem -recurse | Get-Content | Select-String -pattern "dummy"

The problem is, I can see the occurences of the text I am looking for, but I don't know how to tell PS to return the path and the name for every matching files as well.

How can I get the name and location of the files that contains the expression I am looking for?

Recursively list files in Java

How do I recursively list all files under a directory in Java? Does the framework provide any utility?

I saw a lot of hacky implementations. But none from the framework or nio

Is recursion ever faster than looping?

I know that recursion is sometimes a lot cleaner than looping, and I'm not asking anything about when I should use recursion over iteration, I know there are lots of questions about that already.

What I'm asking is, is recursion ever faster than a loop? To me it seems like, you would always be able to refine a loop and get it to perform more quickly than a recursive function because the loop is absent constantly setting up new stack frames.

I'm specifically looking for whether recursion is faster in applications where recursion is the right way to handle the data, such as in some sorting functions, in binary trees, etc.

Implications of foldr vs. foldl (or foldl')

Firstly, Real World Haskell, which I am reading, says to never use foldl instead of foldl'. So I trust it.

But I'm hazy on when to use foldr vs. foldl'. Though I can see the structure of how they work differently laid out in front of me, I'm too stupid to understand when "which is better." I guess it seems to me like it shouldn't really matter which is used, as they both produce the same answer (don't they?). In fact, my previous experience with this construct is from Ruby's inject and Clojure's reduce, which don't seem to have "left" and "right" versions. (Side question: which version do they use?)

Any insight that can help a smarts-challenged sort like me would be much appreciated!

How exactly does tail recursion work?

I almost understand how tail recursion works and the difference between it and a normal recursion. I only don't understand why it doesn't require stack to remember its return address.

// tail recursion
int fac_times (int n, int acc) {
    if (n == 0) return acc;
    else return fac_times(n - 1, acc * n);
}

int factorial (int n) {
    return fac_times (n, 1);
}

// normal recursion
int factorial (int n) {
    if (n == 0) return 1;
    else return n * factorial(n - 1);
}

There is nothing to do after calling a function itself in a tail recursion function but it doesn't make sense for me.

Anonymous recursive PHP functions

Is it possible to have a PHP function that is both recursive and anonymous? This is my attempt to get it to work, but it doesn't pass in the function name.

$factorial = function( $n ) use ( $factorial ) {
    if( $n <= 1 ) return 1;
    return $factorial( $n - 1 ) * $n;
};
print $factorial( 5 );

I'm also aware that this is a bad way to implement factorial, it's just an example.

What exactly is a reentrant function?

Most of the times, the definition of reentrance is quoted from Wikipedia:

A computer program or routine is described as reentrant if it can be safely called again before its previous invocation has been completed (i.e it can be safely executed concurrently). To be reentrant, a computer program or routine:

1. Must hold no static (or global) non-constant data.
2. Must not return the address to static (or global) non-constant data.
3. Must work only on the data provided to it by the caller.
4. Must not rely on locks to singleton resources.
5. Must not modify its own code (unless executing in its own unique thread storage)
6. Must not call non-reentrant computer programs or routines.

How is safely defined?

If a program can be safely executed concurrently, does it always mean that it is reentrant?

What exactly is the common thread between the six points mentioned that I should keep in mind while checking my code for reentrant capabilities?

Also,

1. Are all recursive functions reentrant?
2. Are all thread-safe functions reentrant?
3. Are all recursive and thread-safe functions reentrant?

While writing this question, one thing comes to mind: Are the terms like reentrance and thread safety absolute at all i.e. do they have fixed concrete definations? For, if they are not, this question is not very meaningful.

How to search by key=>value in a multidimensional array in PHP

Is there any fast way to get all subarrays where a key value pair was found in a multidimensional array? I can't say how deep the array will be.

Simple example array:

$arr = array(0 => array(id=>1,name=>"cat 1"),
             1 => array(id=>2,name=>"cat 2"),
             2 => array(id=>3,name=>"cat 1")
);

When I search for key=name and value="cat 1" the function should return:

array(0 => array(id=>1,name=>"cat 1"),
      1 => array(id=>3,name=>"cat 1")
);

I guess the function has to be recursive to get down to the deepest level.

Recursion in Angular directives

There are a couple of popular recursive angular directive Q&A's out there, which all come down to one of the following solutions:

• manually incrementally 'compile' HTML based on runtime scope state
  • example 1 [stackoverflow]
  • example 2 [angular jsfiddles page]
• don't use a directive at all, but a <script> template which refers to itself
  • example 1 [google groups]

The first one has the problem that you can't remove previously compiled code unless you comprehensibly manage the manual compile process. The second approach has the problem of... not being a directive and missing out on its powerful capabilities, but more urgently, it can't be parameterised the same way a directive can be; it's simply bound to a new controller instance.

I've been playing with manually doing an angular.bootstrap or @compile() in the link function, but that leaves me with the problem of manually keeping track of elements to remove and add.

Is there a good way to have a parameterized recursive pattern that manages adding/removing elements to reflect runtime state? That is to say, a tree with a add/delete node button and some input field whose value is passed down a node's child nodes. Perhaps a combination of the second approach with chained scopes (but I have no idea how to do this)?

Can every recursion be converted into iteration?

A reddit thread brought up an apparently interesting question:

Tail recursive functions can trivially be converted into iterative functions. Other ones, can be transformed by using an explicit stack. Can every recursion be transformed into iteration?

The (counter?)example in the post is the pair:

(define (num-ways x y)
  (case ((= x 0) 1)
        ((= y 0) 1)
        (num-ways2 x y) ))

(define (num-ways2 x y)
  (+ (num-ways (- x 1) y)
     (num-ways x (- y 1))

Is log(n!) = Θ(n·log(n))?

This is a homework question. I'm not expecting an answer, just some guidance, possibly :) I am to show that log(n!) = Θ(n·log(n)).

A hint was given that I should show the upper bound with nⁿ and show the lower bound with (n/2)^(n/2). This does not seem all that intuitive to me. Why would that be the case? I can definitely see how to convert nⁿ to n·log(n) [log both sides of an equation], but that's kind of working backwards. What would be the correct approach to tackle this problem? Should I draw the recursion tree? There is nothing recursive about this, so that doesn't seem like a likely approach..

List files recursively in Linux CLI with path relative to the current directory

This is similar to this question, but I want to include the path relative to the current directory in unix. If can do the following:

ls -LR | grep .txt

But it doesn't include the full paths. For example, I have the follow dir structure:

test1/file.txt
test2/file1.txt
test2/file2.txt

The code above will return:

file.txt
file1.txt
file2.txt

How can I get it to include the paths relative to the current directory using standard nix commands?