Understanding Double Recursion

>>60572030
>I'm trying to figure out what the fuck is going on this function
Don't bother, there is no real use of "recursion" let alone "((((double))) recursion"

Follow the order of execution, replace each function call with the resulting value.

It prints the Fibonacci sum by calling recursively with lowered parameters until it reaches n==1
in which case it returns 1, and tell the function that called it that its value is 1
this function goes up the recursive route, sending back 2, 3, 5, ... until it reaches the original parameter you give it (8)

but seriously it's a normal recursion. Go read a book.

>>60572030
>>60572030
There isn't anything anyone can say to just magically make you understand it.
Trace through the program for low n's on paper drawing diagrams, and it's just something that you eventually get used to.

>>60572030
It looks like a fibonacci sequence where it sums the two previous values and returns the result each time it calls itself it reduces n by 1 and again reduces n by
2 in the other call. Sum those two values. You have a check for when your values of n inevitably reach 0 or 1. This example sums the first 8 fibonacci terms.

Also do what this anon suggested , >>60572076 I used to draw a map/diagram to figure oit what each call does. Stacks help a lot with this.

>>60572030
What's the difficulty? just follow the code.
x(8)
<0?
==0?
then execute x(7) +x(6)
x(7) x(6)
<0? <0?
==0? ==0?
then execute x(6)+x(5) -> then execute x(5) + x(

Draw a picture, faggot.

File: 1495648835877.gif (410KB, 221x196px) Image search: [Google]

410KB, 221x196px

Haha, it's quite simple. It prints a stack trace because maximum recursion depth exceeded for even small inputs

>>60572030
>not if( n == 1 ) return n;
>likely most uncommon case is first
fucking die

File: 0f6.jpg (22KB, 480x480px) Image search: [Google]

22KB, 480x480px

>turning an O(n) calculation into an O(2^n) just to show off some recursion that doesn't even use tail recursion

>>60572267
how could you accomplish this is a non recursive, O(n) manner?

>>60572264
Will this affect the branching in the compiled binary?

>>60572324
I'd google "closed form fibonacci"

>>60572424
but that's O(1) anon

My solution in elixir using memoization

defmodule Fib do

  def fib(1, results) do
    {1, results}
  end

  def fib(0, results) do
    {1, results}
  end

  def fib(n, results) do
    if (Map.has_key?(results, n)) do
      {results[n], results}
    else
      r1 = fib(n-1, results)
      r2 = fib(n-2, elem(r1, 1))
      m = Map.put(elem(r2, 1), n, elem(r1, 0) + elem(r2, 0))
      {m[n], m}
    end
  end

  def fib(n) do
    elem(fib(n, %{}), 0)
  end

end

>>60572030
Just follow the path for a few values of n, say n=7 and n=8. You'll notice the pattern, it breaks down x(n) into a sum of x(1), x(0), and x(-1). Think about what it means to write x(n) = x(n-1)+x(n-2)... What sequence does that remind you of?

def fib(n, a = 0, b = 1):
return a if n == 0 else fib(n - 1, b, a + b)

print(fib(8))

>>60572030
Don't worry. At some point your brain will understand how recursion works.
Try to think of it this way:
There is at least one recursion base case. In this example there are three of them. Those are the cases for which there is an immediate result. You can see this in the example. You just return -1, 0 or 1 in the base cases.
Then there's at least one recursion step case. In this example there is exactly one step case.
The step case defines how to get the value x(n) (if n isn't a base case) from arguments that are smaller than n, specifically it needs the values x(n-1) and x(n-2) and adds them together.
Some things that may help you understand it.
(1.) You can view it top down:
To get the value x(n) you need the two previous values x(n-1) and x(n-2). Each of those previous values will also need their two previous values and so on until you reach a base case.
(2.) You can view it bottom up:
If you already have two successive values x(n-2) and x(n-1), then you get the next one (x(n)), by adding them together.
You know the values for the base cases so you can start from there and get as large as you want.
(3.) Some people find (1.) more intuitive, some prefer (2.), whichever you choose, don't consider every step in the recursion.
When you want to understand what the function does, just look at the step case.
It basically says: take two previous values and add them. At that point you can just trust in the magic of recursion and assume that you already know the two correct values.

I hope that helps.

It's worth mentioning there are two important conditions to make recursion work. They might seem subtle, but they're essential.
The function needs at least one base case.
In the step case you call the function with smaller arguments. It doesn't matter how many. There two recursive calls in this example, but there can be arbitrarily many. As long as you get smaller and smaller, it's ok.
If one of those 2 conditions isn't fulfilled, your function might not work.

>>60572324

def fib(n):
 a,b = 1,1
 for i in range(n-1):
  a,b = b,a+b
 return a

File: main-qimg-464b4b6d848c0312d215c8c1049f0295.png (33KB, 529x219px) Image search: [Google]

33KB, 529x219px

>>60572030

>>60572730
And then execution is done via inorder traversal I believe

File: wew.jpg (520KB, 1632x1224px) Image search: [Google]

520KB, 1632x1224px

OP here, is there even a way to solve this on paper on reasonable time? This problem is literally a question from the Federal Police selection test for Technology Forensic Investigator.

The question is "true or false" style, and goes like this:
<shows this function>
the result for x(8) is be 21.

> pic related is me trying

see >>60572730
substitute every fib(1) and fib(2) with 1
you can see that summing those gives you fib(3), so you substitute every fib(3) with 2
you can see that summing those gives you fib(4), so you substitute every fib(4) with 3
and so on

>>60572030
x(8) -> x(7) + x(6)
x(7) -> x(6) + x(5)
x(6) -> x(5) + x(4)
x(5) -> x(4) + x(3)
x(4) -> x(3) + x(2)
x(3) -> x(2) + x(1)
x(2) -> x(1) + x(0)


x(2) -> 1 + 0 = 1
x(3) -> 1 + 1 = 2
x(4) -> 2 + 1 = 3
x(5) -> 3 + 2 = 5
x(6) -> 5 + 3 = 8
x(7) -> 8 + 5 = 13
x(8) -> 13 + 8 = 21

go as deep as you can, then all the way back up
it's easier to substitute functions as numbers when doing this, i.e. evaluate the smallest function you can (x(0) and x(1)) then see what the next largest is (x(2) = x(1) + x(0)) and the next largest (x(3) = x(2) + x(1) = [x(1) + x(0)] + x(1)) until you build up your own map of values

>>60572989
fuck off

>>60572044
Try traversing an unordered unbalanced tree, such as a file system structure, without recursion, say to search for a file.

>>60572030
Pick a small number, like 5, and try to map out how x(5) would cascade down to x(4) and x(3), then x(3) and x(2) and so on until it hits x(1) and x(0) and the function just returns 1 and 0 respectively.

Doing this manually on paper will help you understand how recursion works in this case.

>>60572543
use defp you fucking retard.

>>60573896
hard but doable. just manually handling the stack yourself.

>>60572730
This is why everyone should learn dynamic programming.

>>60572850

Using the standard form of the fibonacci sequence you always have to do fib(n) calculations, it's much easier to just do calculate the values from the bottom up and use your previously calculated values

>>60572030
I still remember having my first Scheme programming assignment where I had to write a nested list reversing function with only car, cdr, cons, and recursive calls.

That class weeded people out of CS pretty fast IIRC.

>>60572030

;;; recursive implementation
(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

;;; iterative implementation
(define (fib n) 
  (fib-iter 1 0 n))

(define (fib-iter a b count)
  (if (= count 0)
      b
      (fib-iter (+ a b) a (- count 1))))

>>60572030
lol what a shit code
>>60572587
and this
>>60575369
and this (the recursive part)

>>60572030
It is not that difficult.

Say you had this function instead

func a()
{
  return 4;
}
func b()
{
  return 3;
}
func c()
{
  return a() + b();
}

Here, it is a bit more clear.
First a is called until it returns.
Then b is called until it returns.

Put the numbers in and unroll the loop on paper or do it in a debugger.

>>60572850
Of course there is. Since you're using a piece of paper, you can "cache" the result values - write them on an other piece of paper and then just writing them back up.

if u cant understand that u should stop trying and kys

>>60572989
This is great. thanks for splaining

>>60572989
>go as deep as you can
stack overflow!!

>>60574036
The Ackermann function cannot be expressed without recursion.
https://en.wikipedia.org/wiki/Ackermann_function

>>60575785
this

btw, it's called a tree recursion.

>>60577099
1s google "ackermann function without recursion" can tell that you are wrong.

>>60572030
User debugger got to the last iteration and bt.
Its so easy.