+ 1

Recursion

Can someone explain it in simple terms? And how it is completed in Python? I am trying to create an ABACABA generator. I understand iteration, but not recursion. Thankss

15th Jul 2020, 10:51 AM
madeline
madeline - avatar
12 odpowiedzi
15th Jul 2020, 11:00 AM
The future is now thanks to science
The future is now thanks to science - avatar
+ 5
Robin such a great explanation! 👍 Recursion is wonderful, and too bad that most of the mainstream languages don't have sufficient support for it, making it very dangerous to use, as memory overflow can occur. I really started to understand and appreciate it after learning functional languages like Haskell and Clojure. Thinking about recursion can really blow the mind.. For me it usually helps to nail down the base case first: when the function doesn't need to do anything. Then build the next step from there.. And due to the nature of recursion, the rest is sort of automatic :) https://code.sololearn.com/cjwPBaUb72b5/?ref=app https://code.sololearn.com/cKu15Wn8y19d/?ref=app https://code.sololearn.com/cZ9exzN9P7jw/?ref=app
16th Jul 2020, 3:27 AM
Tibor Santa
Tibor Santa - avatar
+ 4
From concept Rekursion is, if a function call itself. Its like in RL. If you dont know the way to pizza, you could use the method function "ask for the way". If the result != "Here turn around & look, its here!", you could use this method again. I do a example in code. Read it carefuly, I hope it help. # ------- # way to the club example # requiered import from random import choice as ch # list of directions directions = [ "go right and follow the street", "go left and follow the street", "go straight and follow the street", "turn around its here!" ] # function which call itself def ask_for_way(argument1): direction = ch(directions) if argument1 == "turn around its here!": quit() else: print(direction) ask_for_way(direction) ask_for_way("no idea") # EOF
16th Jul 2020, 8:34 PM
Sven_m
Sven_m - avatar
+ 3
【1】 ► Preamble: First, I'd like to thank @Robin for such devotion for gathering his thoughts and wisdom to draft such an informative article (considering the formatting and text length limitations here) for leading a new learner and demystifying the subject. ► OP's frustration is understandable: "I hate recursion!" "Math is so crazy sometimes[...]" ► A very simple example We are asked to formulate a recursive solution for the following statement. But before that, it also needs us to prove that the summation on the left side is equal to the right side of the equation S(n) = Σ [j = 0 to n] 2ʲ = 2ⁿ⁺¹ - 1, for all n ≥ 0 It reads "the sum of the powers of 2 between 0 and n is equal to 1 less than (n+1)st power of 2". that is, 2⁰ + 2¹ + 2² + ... + 2ⁿ = 2ⁿ⁺¹ - 1 If n = 3, then 2⁰ + 2¹ + 2² + 2³ = 2³⁺¹ - 1 = 15 (Inductive part of the deal) As mentioned earlier, recursion and induction are inseparable. In fact, recursion is a technique for simulating mathematical induction in a programming language. To that end, we need to learn how mathematical induction works and what steps require for devising a successful solution to a given problem, even though all that effort is merely for showing us the correctness of the solution (you'd go for trial and error instead). (Proof) ■ Basis: Since 0 is our lower bound, we set it as the base case S(0). In other words S(0) = 2⁰ = 2¹ - 1 = 1 We just showed the n = 0 is true. ■ Inductive steps: Now we can convince ourselves that every substitution of (j) up to (n) yields true. If n=3 is true, does n=4 also true, or n = 1000? To see what happen to the next n, (n+1), let's replace n in the above statement with n+1 Σ [j = 0 to (n+1)] 2ʲ = 2ⁿ⁺² - 1 The left side of the above sum is identical to Σ [j = 0 to n] 2ʲ plus j = n+1. So, we break it up as Σ [j = 0 to (n+1)] 2ʲ = ( Σ [j = 0 to n] 2ʲ ) + 2ⁿ⁺¹ Substituting the right side, 2ⁿ⁺¹ - 1, for what is inside the parentheses we get [continue]
16th Jul 2020, 5:00 PM
Babak
Babak - avatar
+ 3
【2】 Σ [j = 0 to (n+1)] 2ʲ = ( 2ⁿ⁺¹ - 1 ) + 2ⁿ⁺¹ By simplifying the right side we have Σ [j = 0 to (n+1)] 2ʲ = 2 * 2ⁿ⁺¹ -1 ∴ Σ [j = 0 to (n+1)] 2ʲ = 2ⁿ⁺² -1 Which is the same equation we wanted to prove for (n+1) and it's valid for every nonnegative n. ► Recursive algorithm: Sum-Powers-Two ( n ) If n == 0 return 1 else return ( Nth-Power-Two ( n ) + Sum-Powers-Two ( n-1 ) ) Nth-Power-Two ( m ) if m == 1 return 2 else return ( 2 * Nth-Power-Two ( m-1 ) )
16th Jul 2020, 5:00 PM
Babak
Babak - avatar
+ 2
actually, its a little scary
15th Jul 2020, 11:19 AM
madeline
madeline - avatar
+ 1
@Robin from collections import OrderedDict a = int(input()) def abacaba(b): y = [] g = [] c = OrderedDict() q = (b * 2)-1 for x in range(1, 27): c[x] = str(chr(96+x)).upper() o = 0 for l in range(len(y), 0, -1): g.append(c[b - o]) o = o +1 print(g) abacaba(a) Sorry for being so immature, recursion is scary but it happens in nature. Anyway, this is my code. I'm still working on it. ;/
15th Jul 2020, 4:57 PM
madeline
madeline - avatar
+ 1
I had nightmares and literally dreamed in code. But I thank you. I’ll have to see what declarative & imperative means. But your posts clarified, to me, what it could but a lot I dont understand. I will come back to it. And maybe experience will help. Math is so crazy sometimes, and youd think it would be logical but at times... TOO logical for the human mind. 🤯 Thank you Robin so much
15th Jul 2020, 6:04 PM
madeline
madeline - avatar
0
Hmm... thats a recursive definition. 🤦‍♀️
15th Jul 2020, 11:08 AM
madeline
madeline - avatar
0
poor Robin, please dont let it consume you. i wish i could help 🥺
15th Jul 2020, 6:14 PM
madeline
madeline - avatar
0
I hate recursion!
15th Jul 2020, 6:19 PM
madeline
madeline - avatar
0
Just to let ya’ll know, I am taking a break from coding for a little bit to clear my mind. I like coding, but my brain needs to rest. I hope to be a better program after this mind vacay. Thanks for trying to help me understand such a strange, exciting and horrible process that is ~recursion<< Best regards, Mad 💜
16th Jul 2020, 3:18 AM
madeline
madeline - avatar